Determina se un grafico è semi-connesso o no

Question

Un grafico diretto G = (V, E) si dice che sia semi-connesso se, per tutte le coppie di vertici u, v in V abbiamo u -> v o v -> u percorso. un algoritmo efficiente per determinare se G è semi-collegato

Answer 1

Trivial soluzione O(V^3) potrebbe essere quella di utilizzare floyd warshal all-to-all percorso più breve, ma questo è un eccessivo (in termini di tempo complessità).

Può essere fatto in O(V+E).

rivendicazione:

Un DAG è semi collegato in una sorta topologica, per ogni i v'è un bordo (vi,vi+1)

Prova:

Dato un DAG con ordinamento topologico v1,v2,...,vn:

Se non c'è il bordo (vi,vi+1) per alcuni i, quindi non vi è anche alcun percorso (vi+1,vi) (perché è un ordinamento topologico di un DAG) e il grafico non è semi-connesso.

Se per ogni i esiste un arco (vi,vi+1), allora per ogni i,j (ivi- > vi + 1- > ...- > vj-1- > vj, e il grafico è collegato semi.

da questo possiamo ottenere l'algoritmo:.

1. Trova massime SCC nel grafico
2. costruire il grafo SCC G '= (U, E') in modo che U è un insieme di SCC E'= {(V1,V2) | there is v1 in V1 and v2 in V2 such that (v1,v2) is in E)
3. Do ordinamento topologico su G '
4. Verificare se per ogni i, vi è il bordo Vi, Vi + 1.

Correctness prova:

Se il grafico è semi collegato, per una coppia (v1,v2), tale che vi sia un percorso v1->...->v2 - Let V1, V2 essere i loro SCC. Esiste un percorso da V1 a V2 e quindi anche da v1 a v2, poiché tutti i nodi in V1 e V2 sono fortemente collegati.

Se l'algoritmo ha restituito true, rispetto a qualsiasi dato due nodi v1, v2 - sono in SCC V1 e V2. C'è un percorso da V1 a V2 (senza perdita di generalità), e quindi anche da v1 a v2.

---

Come nota laterale, anche ogni grafico semi-collegato ha una radice (vertice r che porta a tutti i vertici):

Prova:
assumere v'è alcuna radice. Definire #(v) = |{u | there is a path from v to u}| (numero di nodi con un percorso compreso tra v).
Scegliere a tale che #(a) = max{#(v) | for all v}.
a non è una radice, quindi esiste un nodo u che non ha alcun percorso da a ad esso. Poiché il grafico è semi-connesso, significa che c'è un percorso u->...->a. Ma questo significa #(u) >= #(a) + 1 (tutti i nodi raggiungibili da a e anche u).
Contraddizione alla massima di #(a), quindi esiste una radice.

Answer 2

Il soltuin di Amit ha descritto completamente l'approccio più efficiente. Potrei semplicemente aggiungere che si può sostituire il passo 4 controllando se esiste più di un ordine topologico di G '. Se sì, allora il grafico non è semi-connesso. Altrimenti, il grafico è semi-connesso. Questo può essere facilmente incorporato in Kahn's algorithm per trovare l'ordine topologico di un grafico.

Un'altra soluzione meno efficiente che funziona in tempo quadratico è la seguente.

Innanzitutto, costruire un altro grafico G * che è il contrario del grafico originale. Quindi per ogni vertice v di G, si esegue un DFS da v in G e si considera il set di nodi raggiungibili come R_v. Se R_v! = V (G), quindi eseguire un altro DFS da v in G * e lasciare che il set di nodi raggiungibili sia R _v. Se l'unione di R_v e R _v non è V (G), il grafico non è semi-connesso.