Ermitteln, ob ein Graph semi-verbunden ist oder nicht

Question

Ein gerichteter Graph G = (V, E) wird als semi-verbunden bezeichnet, wenn für alle Eckenpaare u, v in V u -> v oder v gilt -> Pfad. Geben Sie einen effizienten Algorithmus, um zu bestimmen, ob oder ob nicht G halb verbunden

Answer 1

Trivial O(V^3) Lösung floyd warshal verwenden könnte all-to-all kürzesten Weg ist, aber das ist zuviel des Guten (in Bezug auf die Zeitkomplexität).

Es kann in O(V+E) getan werden.

Claim:

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

Beweis:

a DAG mit topologische Sortierung Gegeben v1,v2,...,vn:

Wenn keine Kante vorhanden ist (vi,vi+1) für einige i, dann gibt es auch keinen Pfad (vi+1,vi) (weil es eine topologische Art einer DAG ist), und das Diagramm ist nicht halb verbunden.

wenn für jede i eine Kante ist (vi,vi+1), dann für jeden i,j (ivi- > vi + 1- > ...- > vj vj >-1- und der Graph halb verbunden.

daraus können wir den Algorithmus erhalten.

1. Finden SVB Maximal in der Grafik
2. den SCC graph Bauen G '= (U, E'), so dass U ein Satz von SVB ist E'= {(V1,V2) | there is v1 in V1 and v2 in V2 such that (v1,v2) is in E)
3. Do topologische Sortierung auf G '
4. Überprüfen Sie, ob für jedes i, gibt es Kante Vi, Vi + 1.

Korrektheitsbeweis:

Wenn der Graph halb verbunden ist, für ein Paar (v1,v2), so dass es einen Weg v1->...->v2 ist - lassen Sie V1, V2 ihre SVB sein. Es gibt einen Pfad von V1 nach V2 und somit auch von v1 nach v2, da alle Knoten in V1 und V2 stark verbunden sind.

Wenn der Algorithmus wahr ergab, als für zwei gegebenen Knoten v1, v2 - sind in SCC V1 und V2. Es gibt einen Pfad von V1 nach V2 (ohne Verlust der Allgemeinheit) und somit auch von v1 nach v2.

---

Als Randbemerkung, auch jede halb zusammenhängenden Graphen haben eine Wurzel (Vertex r, die alle Ecken führen):

Beweis:
Angenommen, es gibt keine Wurzel. Definieren Sie #(v) = |{u | there is a path from v to u}| (Anzahl der Knoten mit einem Pfad von v zu ihnen).
Wählen Sie a so, dass #(a) = max{#(v) | for all v}.
a ist kein Root, also gibt es einen Knoten u, der keinen Pfad von a zu ihm hat. Da der Graph halb verbunden ist, bedeutet dies, dass es einen Pfad gibt u->...->a. Aber das bedeutet #(u) >= #(a) + 1 (alle Knoten erreichbar von a und auch u).
Widerspruch zur Maximierung von #(a), daher gibt es eine Wurzel.

Answer 2

Amit Soltuin beschrieben vollständig den effizientesten Ansatz. Ich könnte nur hinzufügen, dass man Schritt 4 ersetzen kann, indem man überprüft, ob es mehr als eine topologische Ordnung von G 'gibt. Wenn ja, dann ist der Graph nicht halb verbunden. Ansonsten ist das Diagramm halb verbunden. Dies kann leicht in Kahn's algorithm zum Auffinden der topologischen Ordnung eines Graphen eingebaut werden.

Eine andere weniger effiziente Lösung, die in quadratischer Zeit arbeitet, ist die folgende.

Konstruieren Sie zuerst einen anderen Graphen G *, der die Umkehrung des ursprünglichen Graphen ist. Dann führen Sie für jeden Vertex v von G ein DFS von v in G aus und betrachten die Gruppe erreichbarer Knoten als R_v. Wenn R_v! = V (G), dann führe ein anderes DFS von v in G * aus und lass die Menge erreichbarer Knoten R _v sein. Wenn die Vereinigung von R_v und R _v nicht V (G) ist, dann ist der Graph nicht halb verbunden.