Trova se un albero spanning minimo contiene un bordo in tempo lineare?

Question

Ho il seguente problema sul mio lavoro:

dare una O (n + m) algoritmo per trovare che sia un vantaggio e sarebbe una parte del MST di un grafico

(Ci è permesso di ottenere aiuto dagli altri in questo incarico, quindi non è un imbroglio.)

Penso che potrei fare un BFS e scoprire se questo margine è uno spigolo tra due strati e in tal caso se questo margine fosse il più piccolo tra questi livelli. Ma cosa potrei dire quando questo spigolo non è un bordo dell'albero dell'albero BFS?

Answer 1

Come suggerimento, se un bordo non è il bordo più pesante in qualsiasi ciclo che lo contiene, c'è qualche MST che contiene quel bordo. Per vedere questo, considera qualsiasi MST. Se il MST contiene già il bordo, ottimo! Sono state fatte. In caso contrario, aggiungere il bordo nell'MST. Questo crea un ciclo nel grafico. Ora trova il bordo più pesante in quel ciclo e rimuovilo dal grafico. Ora tutto è ancora connesso (perché se due nodi erano collegati da un percorso che attraversava quel confine, ora possono essere collegati semplicemente girando intorno al ciclo nella direzione opposta). Inoltre, poiché il costo del bordo è stato cancellato non era più piccolo del costo del bordo in questione (perché il bordo non è il bordo più pesante del ciclo), il costo di questo albero non può essere maggiore di prima. Da quando abbiamo iniziato con un MST, dobbiamo quindi terminare con un MST.

Utilizzando questa proprietà, vedere se è possibile scoprire se il bordo è il bordo più pesante su qualsiasi ciclo in tempo lineare.

Answer 2

Trova se ci sono percorsi più economici di quello corrente (u, v) che crea un ciclo per te v. Se sì, allora (u, v) non è sul primo. Altrimenti lo è. Questo può essere dimostrato dalla proprietà cut e dalla proprietà cycle.

Answer 3

Risolveremo questo utilizzando MST cycle property, che dice che, "Per qualsiasi ciclo C nel grafico, se il peso di un bordo e di C è maggiore dei pesi di tutti gli altri bordi di C, questo bordo non può appartenere a un MST. "

Ora, eseguire il seguente algoritmo O(E+V) per verificare se il bordo E che collega i vertici te v sarà parte di un MST o meno.

Fase 1

Run DFS da uno dei punti finali (sia u o v) del bordo E i soli bordi che hanno un peso inferiore a quello di E.

Fase 2

caso 1 Se alla fine di questo DFS, i vertici uev Connessione, quindi bordo e non può essere una parte di un MST. Questo perché in questo caso esiste sicuramente un ciclo nel grafico con il bordo E che ha il peso massimo e non può essere una parte dell'MST (dalla proprietà del ciclo).

Caso 2 Ma se alla fine DFS uev rimanere scollegati, quindi bordo E deve essere parte di alcuni MST come in questo caso E non è sempre il bordo massimo peso di tutti i cicli che è una parte di