C'è un margine che possiamo eliminare senza disconnettere il grafico?

Prima di iniziare, sì, questo è un compito. Non avrei postato qui se non avessi provato il più possibile per risolvere questo per le ultime 14 ore e non ho ottenuto nulla.C'è un margine che possiamo eliminare senza disconnettere il grafico?

Il problema è il seguente: Voglio verificare se posso eliminare un bordo da un grafico indiretto connesso senza disconnetterlo o meno in tempo O (V), non solo lineare.

Quello che ho raggiunto finora:

Un fronte ciclo può essere rimosso senza scollegare il grafico, quindi semplicemente controllare se il grafico ha un ciclo. Ho due metodi che potrebbero essere utilizzati, uno è DFS e quindi controllo se ho i bordi posteriori; l'altro è contando Vs ed Es e controllando se | E | = | V | - 1, se è vero, il grafico è un albero e non è possibile eliminare alcun nodo senza disconnetterlo.

Entrambi gli approcci precedenti risolvono il problema, ma entrambi hanno bisogno di O (| E | + | V |), e il libro dice che c'è un modo più veloce (probabilmente è un approccio avido).

Posso ottenere qualche suggerimento, per favore?

MODIFICA: In particolare, questa è la mia domanda; dato un grafico collegato G = (V, E), posso rimuovere qualche bordo e in E e il grafico risultante è ancora connesso?

fonte

2012-01-03 Fingolfin

Essere un po 'più preciso nella dichiarazione. Stai chiedendo "dato un grafico collegato G = (V, E), posso rimuovere un particolare bordo e in E e il grafico risultante essere ancora connesso?" oppure "Dato un grafico come prima, esiste un bordo e in E per cui il grafico risultante non è più connesso?" –

Domanda modificata, mi dispiace. Ho bisogno di VERIFICARE se posso rimuovere un bordo da E e avere ancora il grafico connesso. – Fingolfin

Il termine tecnico è [bridge] (http://en.wikipedia.org/wiki/Bridge_ (graph_theory)) – sdcvvc

Qualsiasi attraversamento ricorsivo del grafico, marcatura nodi come sono visitati e cortocircuito per restituire true se mai eseguire in un nodo che è già segnato farà il trucco. Ciò richiede O (| V |) per attraversare l'intero grafico se non vi è alcun margine che può essere rimosso e meno tempo se si arresta presto per restituire true.

modificare

Sì, un attraversamento recusive dell'intero grafo richiede O (| V | + | E |) tempo, ma abbiamo solo attraversare l'intero grafico se non ci sono dei cicli - nel qual caso | E | = | V | -1 e richiede solo O (| V |) tempo. Se c'è un ciclo, lo troveremo dopo aver attraversato al massimo | V | bordi (e visitando al massimo | V | +1 nodi), che prende parimenti tempo O (| V |).

Inoltre, ovviamente quando si attraversa un nodo (diverso dal primo), non si considera il bordo che si è utilizzato per raggiungere il nodo, poiché ciò provocherebbe immediatamente la visualizzazione di un nodo già visitato.

fonte

2012-01-03 02:47:07

Puoi solo spiegarmi il tuo ragionamento qui, signore? L'esecuzione della procedura ricorsiva di esplorazione su un grafico connesso normalmente richiede O (| E | + | V |) perché ho bisogno di O (V) per contrassegnare i nodi e O (2 | E |) semplicemente per controllare i bordi che collegano i nodi . Ricorsivo o no, questo non si avvicina a O (| V |), quindi come restituire true quando si neutralizza un nodo visitato si riduce a O (V)? Inoltre, se restituisco true quando si neutralizza un visitato, potrei effettivamente tornare vero durante il back-tracking da un sink, potrei dire che ho un ciclo mentre ancora non ho davvero controllato se lo faccio o meno. – Fingolfin

Wow !! Questo ora ha perfettamente senso! Grazie mille, signore! – Fingolfin

Aha. Ho pensato che ci sarebbe stato un trucco con E | = | V | -1 ma sono morto cerebralmente dopo le vacanze e non l'ho visto. –

Da quello che sto leggendo, DFS senza ripetizione è considerato O (| V |), quindi se si prende vantaggio di e, e si lasciano i due vertici che si connettono sia u che v, se si esegue DFS da u, ignorando e, si può supporre che e non sia un bridge se v viene scoperto, e dato che DFS senza ripetizione è O (| V |), allora questo sarebbe, suppongo essere considerato O (| V |).

fonte

2012-01-03 02:30:07 PlexQ

No, un DFS completo, anche senza ripetizione è ancora O (| V | + | E |) poiché tu è necessario esaminare tutti i bordi per assicurarsi che non vadano ai nodi che non hanno ancora visitato. Se si interrompe l'attraversamento non appena si trova un ciclo, tuttavia, ciò richiede solo l'esame al massimo | V | bordi. –

Immagino che avrei dovuto chiarire, sembrava un po 'ovvio che una volta trovato v, hai dimostrato che e non è un bridge e quindi hai risposto al problema, a volte dimentichi che non puoi dare nulla per scontato nelle prove: D – PlexQ

È possibile elencare tutti i bordi E e prendere un margine e contrassegnare uno ad uno i due vertici finali visitati. Se durante l'attraversamento scopriamo che i due vertici sono stati precedentemente visitati da alcuni bordi e possiamo rimuovere quel bordo.

Dobbiamo prendere i bordi al massimo | V | tempo per vedere se questa condizione soddisfa.

Il caso peggiore può andare così, ogni volta che prendiamo un vantaggio, visiteremo almeno un nuovo vertice. Poi ci sono | V | vertici e dobbiamo prendere | V | bordi per quel particolare bordo da trovare.

Il caso migliore potrebbe essere quello con | V |/2 + 1 e

fonte

2017-04-04 22:17:35 YashM

C'è un margine che possiamo eliminare senza disconnettere il grafico?

risposta

Problemi correlati