Bestimmen, ob ein graph ist semi-verbunden oder nicht

Trivial O(V^3) Lösung könnte sein, die Nutzung floyd warshal all-to-all kürzeste Weg, aber das ist übertrieben (in Bezug auf die Zeit-Komplexität).

Kann man das in O(V+E).

Anspruch:

Einer DAG ist halb verbunden in einer topologischen Sortierung für jede i es gibt eine Kante (vi,vi+1)

Beweis:

Gegeben ein DAG mit der topologischen Sortierung v1,v2,...,vn:

Wenn es keine Kante (vi,vi+1) für einige i, dann gibt es auch keinen Weg (vi+1,vi) (weil es eine topologische Sortierung eines DAG), und der graph ist nicht semi verbunden.

Wenn man für jeden i gibt eine Kante (vi,vi+1), dann für jede i,j (i < j) es gibt einen Pfad vi->vi+1->...->vj-1->vj, und der graph ist halb verbunden.

Aus diesem können wir den Algorithmus:

1. Finden Maximal SCCs in der Grafik
2. Bauen die SCC graph G'=(U,E'), so dass U ist ein Satz von SCCs. E'= {(V1,V2) | there is v1 in V1 and v2 in V2 such that (v1,v2) is in E)
3. Tun topologische Sortierung für G'
4. Prüfen Sie, ob für alle i, dort ist die Kante Vi Vi+1.

Korrektheit Beweis:

Wenn der graph ist halb verbunden, für ein paar (v1,v2), so dass es einen Pfad v1->...->v2 - Let V1, V2 werden Ihre SCCs. Es gibt einen Pfad von V1 nach V2, und damit auch von v1 auf v2, da alle Knoten in V1 und V2 fest verbunden sind.

Wenn der Algorithmus ergab true", dann für jeden zwei beliebigen Knoten v1, v2 - wir wissen, Sie sind in der SCC-V1 und V2. Es gibt einen Pfad von V1 nach V2 (ohne Verlust der Allgemeinheit), und damit auch von v1 nach v2.

Als seitliche Anmerkung, die auch alle semi-connected-graph besitzt eine Wurzel (vertex r führt, dass alle vertices):

Beweis:

Angenommen, es gibt keine Wurzel. Definieren #(v) = |{u | there is a path from v to u}| (Anzahl der Knoten, die einen Pfad von v zu Ihnen).

Wählen Sie a so dass #(a) = max{#(v) | for all v}.

a ist nicht eine Wurzel, so gibt es einige Knoten u hat, dass kein Pfad von a zu. Da der graph ist halb verbunden, es bedeutet, dass es einen Pfad u->...->a. Aber das bedeutet, dass #(u) >= #(a) + 1 (alle Knoten aus erreichbar a und auch u).

Widerspruch zu maximality von #(a), so gibt es eine Wurzel.