Zusammenhangskomponenten, Brücken und Artikulationspunkte

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Was „zusammenhängend“ bedeutet

Ein Graph ist zusammenhängend genau dann, wenn es zwischen je zwei seiner Knoten einen Weg gibt. Sie können irgendwo starten und, indem Sie Kanten folgen, überall hinkommen. Wenn das nicht gilt, zerfällt der Graph in Teile, die man Zusammenhangskomponenten nennt: die größten zusammenhängenden Teilgraphen, die er enthält, ohne Kante zwischen zwei verschiedenen Teilen.

Am klarsten sieht man Komponenten über die Relation „u erreicht v“. Sie ist reflexiv (jeder Knoten erreicht sich selbst über den leeren Weg), symmetrisch (in einem ungerichteten Graphen lässt sich ein Weg rückwärts gehen) und transitiv (zwei Wege lassen sich aneinanderhängen). Eine Relation mit diesen drei Eigenschaften ist eine Äquivalenzrelation, und jede Äquivalenzrelation zerlegt ihre Menge in disjunkte Klassen. Die Klassen der Erreichbarkeit sind genau die Komponenten. Deshalb gehört jeder Knoten zu genau einer Komponente, und deshalb ist ein isolierter Knoten, ganz ohne Kanten, für sich allein eine Komponente.

Ein einziger Graph trägt den ganzen Artikel. Er hat zwölf Knoten und dreizehn Kanten und ist so gebaut, dass jede der folgenden Ideen ein konkretes Beispiel hat und, wo es darauf ankommt, ein konkretes Gegenbeispiel:

V = {A, B, C, D, E, F, G, H, I, J, K, L}
E = {AB, BC, CA, CD, DE, EC, EF, FG, GH, HI, IF, IJ, KL}        13 Kanten

Komponente 1 = {A, B, C, D, E, F, G, H, I, J}     12 Kanten
Komponente 2 = {K, L}                               1 Kante

Das Vokabular stammt aus dem Leitfaden zu Knoten und Kanten, und alles hier betrifft ungerichtete Graphen bis Abschnitt 11, wo die Richtung die Lage verändert.

2. Die Komponenten finden

Weil Komponenten Erreichbarkeitsklassen sind, findet jede Graphensuche sie. Starten Sie eine Breiten- oder Tiefensuche bei irgendeinem Knoten; alles, was sie erreicht, ist die Komponente dieses Knotens. Starten Sie dann erneut bei einem noch nicht erreichten Knoten, und wiederholen Sie das, bis keiner mehr übrig ist. Jeder neue Start ist eine Komponente mehr.

from collections import deque

def connected_components(graph):
    """Versieht jeden Knoten eines ungerichteten Graphen mit dem Index seiner Komponente."""
    label, components = {}, []
    for start in graph:                      # isolierte Knoten bilden eine eigene Komponente
        if start in label:
            continue
        label[start] = len(components)
        members, queue = [start], deque([start])
        while queue:
            u = queue.popleft()
            for v in graph[u]:
                if v not in label:
                    label[v] = len(components)
                    members.append(v)
                    queue.append(v)
        components.append(sorted(members))
    return components, label

edges = ['AB', 'BC', 'CA', 'CD', 'DE', 'EC', 'EF', 'FG', 'GH', 'HI', 'IF', 'IJ', 'KL']
graph = {v: [] for v in 'ABCDEFGHIJKL'}
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)

components, label = connected_components(graph)
print(len(components), components)
# 2 [['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'], ['K', 'L']]
print(label['H'] == label['A'], label['K'] == label['A'])
# True False

Jeder Knoten wird einmal markiert und jede Kante zweimal betrachtet, einmal von jedem Ende, also braucht die ganze Arbeit O(V + E) Zeit. Die äußere Schleife über alle Knoten ist die entscheidende Zeile. Eine einzelne Suche beantwortet „was kann ich von hier aus erreichen“, nicht „wie viele Teile gibt es“, und die Schleife zu vergessen ist ein häufiger Weg, für einen Graphen mit mehreren Komponenten die Anzahl 1 zu erhalten.

Zwei Alternativen sollte man kennen. Wenn Kanten einzeln eintreffen und nur hinzugefügt werden, hält eine Union-Find-Struktur die Komponenten in nahezu konstanter amortisierter Zeit pro Kante aktuell: Jede Kante vereinigt die Klassen ihrer beiden Enden, und zwei Knoten liegen genau dann in derselben Komponente, wenn sie dieselbe Wurzel haben. Die Idee geht auf den Äquivalenzalgorithmus von Galler und Fischer aus dem Jahr 1964 zurück. Und in der Bildverarbeitung, wo der „Graph“ ein Pixelgitter ist, heißt dasselbe Problem Komponentenmarkierung (Connected-Component Labeling). Rosenfeld und Pfaltz beschrieben 1966 dafür einen sequenziellen Durchlauf. Ob diagonale Nachbarn zählen, genannt 8er-Nachbarschaft, oder nur die vier geraden Nachbarn, genannt 4er-Nachbarschaft, ändert, welche Formen eine Region sind und welche zwei.

Es gibt sogar eine algebraische Antwort. Die Laplace-Matrix eines Graphen, mit den Graden auf der Diagonalen und −1 für jede Kante, hat den Eigenwert 0 mit einer Vielfachheit, die genau der Anzahl der Komponenten entspricht. Für das durchgehende Beispiel ist diese Vielfachheit 2. Mit dem Zusammenhang zwischen Eigenwerten und Struktur befasst sich die spektrale Graphentheorie.

3. Was die Anzahl der Komponenten verrät

Schreiben Sie n für die Anzahl der Knoten, m für die Anzahl der Kanten und k für die Anzahl der Komponenten. Eine Handvoll Tatsachen verbindet die drei, und sie taugen als Plausibilitätsprüfung für jedes Programm, das Komponenten zählt.

Ein Graph mit n Knoten und k Komponenten hat mindestens n − k Kanten, mit Gleichheit genau dann, wenn er ein Wald ist.

Der Beweis ist ein Zählargument. Beginnen Sie mit n isolierten Knoten, also n Komponenten, und fügen Sie die Kanten nacheinander hinzu. Jede Kante verbindet entweder zwei verschiedene Komponenten und senkt die Anzahl um eins, oder sie landet innerhalb einer Komponente und ändert nichts. Um auf k Komponenten herunterzukommen, brauchen Sie mindestens n − k Kanten der ersten Art, und Sie haben genau so viele, wenn keine Kante zum Schließen eines Kreises verschwendet wurde. Ein Wald ist genau ein Graph ohne Kreise, und ein Baum ist ein zusammenhängender Wald, weshalb ein Baum mit n Knoten n − 1 Kanten hat, wie der Leitfaden zu Bäumen in der Graphentheorie auf mehreren anderen Wegen beweist. Das durchgehende Beispiel erfüllt 13 ≥ 12 − 2 = 10, mit drei Kanten Reserve, eine für jeden seiner drei Kreise.

Auch in die andere Richtung gibt es eine Obergrenze. Ein einfacher Graph mit k Komponenten hat höchstens C(n − k + 1, 2) Kanten, erreicht, indem man n − k + 1 Knoten in einen vollständigen Graphen legt und die übrigen k − 1 isoliert lässt. Eine Folgerung ist ein schneller Zusammenhangstest: Ein einfacher Graph mit mehr als C(n − 1, 2) Kanten kann keine zwei Komponenten haben, also muss er zusammenhängend sein.

Eine weitere Tatsache ist eine klassische Übungsaufgabe mit einem Zweizeilenbeweis: Ein Graph oder sein Komplement ist immer zusammenhängend. Ist G nicht zusammenhängend, nehmen Sie zwei beliebige Knoten. Liegen sie in verschiedenen Komponenten von G, sind sie im Komplement benachbart. Liegen sie in derselben Komponente, wählen Sie einen beliebigen Knoten aus einer anderen Komponente; er ist im Komplement zu beiden benachbart. In jedem Fall sind sie durch einen Weg der Länge höchstens zwei verbunden. Diese drei Tatsachen wurden per Brute Force an jedem einfachen Graphen mit bis zu sechs Knoten überprüft.

4. Brücken: die Kanten, auf die Sie nicht verzichten können

Beim Zusammenhang geht es nicht nur darum, ob ein Graph zusammenhält, sondern auch darum, wie fest. Eine Brücke, auch Schnittkante genannt, ist eine Kante, deren Entfernen die Anzahl der Komponenten erhöht. Löscht man sie, zerfällt ihre Komponente in genau zwei Teile, nie mehr, denn das Entfernen einer Kante kann nur ihre beiden Endknoten voneinander trennen.

Eine Kante ist genau dann eine Brücke, wenn sie auf keinem Kreis liegt.

Liegt eine Kante uv auf einem Kreis, ist der Rest des Kreises ein zweiter Weg von u nach v, also trennt das Entfernen der Kante nichts. Lässt umgekehrt das Entfernen von uv die Knoten u und v verbunden, so bildet der verbleibende Weg von v zurück nach u zusammen mit uv einen Kreis. Brücken sind also genau die Kanten ohne Ausweichroute. Zwei Folgerungen ergeben sich sofort: In einem Baum ist jede Kante eine Brücke, und eine Kante zwischen zwei Knoten, die durch eine zweite, parallele Kante verbunden sind, ist nie eine Brücke.

Das durchgehende Beispiel hat drei Brücken: E–F, I–J und K–L. Das Entfernen einer beliebigen von ihnen erhöht die Komponentenzahl von 2 auf 3. Jede andere Kante liegt auf einem der drei Kreise, den beiden Dreiecken und dem Quadrat.

5. Artikulationspunkte: die Knoten, auf die Sie nicht verzichten können

Ein Artikulationspunkt, auch Schnittknoten genannt, ist ein Knoten, dessen Entfernen, zusammen mit seinen Kanten, die Anzahl der Komponenten erhöht. Gleichwertig ist v ein Artikulationspunkt, wenn es zwei andere Knoten u und w in seiner Komponente gibt, für die gilt: Jeder Weg von u nach w enthält v.

Anders als eine Brücke kann ein Artikulationspunkt seine Komponente auf einmal in viele Teile zerlegen. Entfernen Sie das Zentrum eines Sterns mit fünf Blättern, und es bleiben fünf Komponenten. Im durchgehenden Beispiel hinterlässt das Entfernen von C drei Komponenten: {A, B}, alles von D bis J und {K, L}, das ohnehin schon getrennt war.

Brücken und Artikulationspunkte hängen zusammen, und dieser Zusammenhang ist eine Falle, die man sorgfältig formulieren sollte:

• Ein Endknoten einer Brücke ist ein Artikulationspunkt, außer er hat Grad 1. Entfernen Sie E und die Brücke verschwindet mit ihm, sodass die Seite von F von der Seite von D getrennt wird. Deshalb sind E, F und I Artikulationspunkte.
• Eine Brücke braucht an keinem ihrer Enden einen Artikulationspunkt. K–L ist eine Brücke, aber beide Enden haben Grad 1, und das Entfernen eines Blattes trennt nie etwas.
• Ein Artikulationspunkt muss keine Brücke berühren. C verbindet zwei Dreiecke, eine Form, die oft Schmetterlingsgraph genannt wird. Jede Kante an C liegt auf einem Dreieck, also ist keine von ihnen eine Brücke, und doch schneidet das Entfernen von C die Knoten A und B vom Rest ab.

Das durchgehende Beispiel hat also vier Artikulationspunkte, C, E, F und I, und die beiden Begriffe sind wirklich verschieden: Knotenausfälle und Verbindungsausfälle legen im selben Netz unterschiedliche Schwachstellen offen.

6. Eine Tiefensuche findet beide

Der naheliegende Algorithmus löscht nacheinander jede Kante oder jeden Knoten und zählt die Komponenten neu. Das kostet eine vollständige Suche pro Kandidat, O(E(V + E)) für Brücken. 1972 und 1973 zeigten Tarjan sowie Hopcroft und Tarjan, dass eine einzige Tiefensuche genügt, mit insgesamt O(V + E) Zeit. Die Methode beruht auf zwei Zahlen pro Knoten.

• disc[v] ist der Zeitpunkt, zu dem die Suche v zum ersten Mal erreicht: 0 für den ersten Knoten, 1 für den nächsten und so weiter.
• low[v] ist die kleinste Entdeckungszeit, die sich vom Teilbaum von v aus erreichen lässt, indem man Baumkanten abwärts geht und dann höchstens eine Rückwärtskante nimmt.

In einer ungerichteten Tiefensuche ist jede Nicht-Baumkante eine Rückwärtskante: Sie verbindet einen Knoten mit einem seiner Vorfahren. Eine Rückwärtskante ist ein Fluchtweg, ein Weg aus einem Teilbaum heraus, der nicht die Baumkante über ihm benutzt. Beide Tests fragen, ob es einen solchen Weg gibt. Für eine Baumkante vom Elternknoten u zum Kind v:

Brücke              u–v ist eine Brücke             wenn  low[v] > disc[u]    nichts unterhalb von v erreicht u oder höher
Artikulationspunkt  u ist ein Artikulationspunkt    wenn  low[v] ≥ disc[u]    nichts unterhalb von v reicht über u hinaus
Wurzel              die Wurzel ist ein Artikulationspunkt, wenn sie im DFS-Baum 2 oder mehr Kinder hat

Die Wurzel braucht eine eigene Regel, weil nichts über ihr liegt: Sie trennt den Graphen genau dann, wenn die Suche sie zweimal verlassen musste, was bedeutet, dass ihre Teilbäume keine Kante untereinander haben. Hier ist die ganze Methode, iterativ geschrieben, damit ein langer Weg den Aufrufstapel von Python nicht zum Überlaufen bringt:

def bridges_and_cut_vertices(vertices, edges):
    """Tarjans Low-Link-Methode, iterativ. Kanten sind Paare (u, v); parallele Kanten sind erlaubt."""
    adj = {v: [] for v in vertices}
    for i, (u, v) in enumerate(edges):       # Kanten-IDs merken, nicht nur Nachbarn
        adj[u].append((v, i))
        adj[v].append((u, i))
    disc, low, bridges, cuts, clock = {}, {}, [], set(), 0
    for root in vertices:
        if root in disc:
            continue
        disc[root] = low[root] = clock; clock += 1
        children = 0
        stack = [(root, -1, iter(adj[root]))]  # (Knoten, ID der Kante, über die wir kamen, Nachbarn)
        while stack:
            u, in_edge, it = stack[-1]
            for v, i in it:
                if i == in_edge:             # genau diese eine Kante überspringen, nicht jede Kante zum Elternknoten
                    continue
                if v in disc:                # Rückwärtskante: ein Fluchtweg nach oben im Baum
                    low[u] = min(low[u], disc[v])
                else:                        # Baumkante: absteigen
                    disc[v] = low[v] = clock; clock += 1
                    stack.append((v, i, iter(adj[v])))
                    break
            else:                            # u ist fertig: an den Elternknoten p melden
                stack.pop()
                if stack:
                    p = stack[-1][0]
                    low[p] = min(low[p], low[u])
                    if low[u] > disc[p]:
                        bridges.append(edges[in_edge])
                    if low[u] >= disc[p] and p != root:
                        cuts.add(p)
                    if p == root:
                        children += 1
        if children >= 2:                    # die Wurzel ist nur mit 2+ DFS-Kindern ein Artikulationspunkt
            cuts.add(root)
    return bridges, sorted(cuts), disc, low

edges = ['AB', 'BC', 'CA', 'CD', 'DE', 'EC', 'EF', 'FG', 'GH', 'HI', 'IF', 'IJ', 'KL']
bridges, cuts, disc, low = bridges_and_cut_vertices('ABCDEFGHIJKL', edges)
print(bridges)
# ['IJ', 'EF', 'KL']
print(cuts)
# ['C', 'E', 'F', 'I']

print(bridges_and_cut_vertices('xy', ['xy', 'xy'])[0])   # eine doppelte Kante ist keine Brücke
# []

Im durchgehenden Beispiel läuft die Suche ab A zufällig geradewegs einen Weg hinunter, A, B, C, …, J, und die drei Nicht-Baumkanten C–A, E–C und I–F werden zu Rückwärtskanten. Die Abbildung zeigt die resultierenden Zahlen.

Liest man die Tabelle anhand der Regeln, ergeben sich alle Antworten. low[F] = 5 ist größer als disc[E] = 4, also klettert nichts unterhalb von F zurück zu E, und E–F ist eine Brücke; I–J ist aus demselben Grund eine Brücke, mit 9 > 8. low[D] = 2 ist gleich disc[C] = 2: Der Teilbaum unterhalb von C kann zurück bis zu C selbst klettern, aber nicht höher, also ist C ein Artikulationspunkt, obwohl ihn keine Brücke berührt. Und A, die Wurzel, hat nur ein einziges Kind, ist also keiner.

7. Zwei Fehler, die die einfachen Tests bestehen

Low-Link-Code ist kurz, und zwei seiner klassischen Fehler liefern auf den meisten kleinen Beispielen korrekte Antworten. Beide wurden gegen Brute Force geprüft: Die obige Version stimmt auf 5.000 zufälligen Multigraphen mit „löschen und neu zählen“ überein.

Den Elternknoten statt der Elternkante überspringen. Wenn die Suche die Nachbarn von v betrachtet, darf sie die Baumkante, über die sie gekommen ist, nicht als Rückwärtskante behandeln, sonst könnte jeder Knoten über seinen eigenen Elternknoten entkommen. Viele Implementierungen überspringen „den Nachbarn, der mein Elternknoten ist“. In einem einfachen Graphen ist das in Ordnung, aber bei zwei parallelen Kanten zwischen x und y überspringt es beide, und die doppelte Kante wird als Brücke gemeldet, obwohl das Löschen einer Kopie nichts trennt. Die eine Kante anhand ihrer Identität zu überspringen, wie es der Code mit in_edge tut, ist auch für Multigraphen korrekt.

Verwenden von low[w] statt disc[w] bei einer Rückwärtskante. Die Aktualisierung entlang einer Rückwärtskante zu w sollte disc[w] verwenden. Wer low[w] schreibt, lässt den Fluchtweg über w hinaus weiterlaufen, durch Kanten, die zu einem anderen Block gehören. Für Brücken ist das zufällig harmlos: Auf 20.000 zufälligen Graphen lag die Variante bei keiner Brücke falsch. Für Artikulationspunkte nicht: Derselbe Test ertappte sie bei 35 der Graphen, und der kleinste Fehlschlag, den diese Suche fand, ist das Paar von Dreiecken mit dem gemeinsamen Knoten C. Mit low[w] importiert die Rückwärtskante E–C den Wert low[C] = 0, also wird low[D] zu 0, der Test bei C schlägt fehl, und der Artikulationspunkt verschwindet aus der Ausgabe.

8. Blöcke und der Block-Schnittknoten-Baum

Artikulationspunkte zerlegen einen zusammenhängenden Graphen in natürliche Teile. Ein Block ist ein maximaler zusammenhängender Teilgraph ohne eigenen Artikulationspunkt: entweder ein 2-zusammenhängendes Teilstück, das nach dem Löschen eines beliebigen Knotens zusammenhängend bleibt, oder eine einzelne Brücke oder ein isolierter Knoten. Jede Kante gehört zu genau einem Block, und zwei Blöcke haben höchstens einen Knoten gemeinsam, der dann ein Artikulationspunkt ist. Blöcke heißen auch zweifach zusammenhängende Komponenten, und der Algorithmus von Hopcroft und Tarjan aus dem Jahr 1973 findet sie in derselben einzigen Suche, indem er einen Stapel von Kanten führt und jedes Mal einen Block abnimmt, wenn der Artikulationspunkt-Test anschlägt.

Das durchgehende Beispiel hat sechs Blöcke: die Dreiecke {A, B, C} und {C, D, E}, das Quadrat {F, G, H, I} und die drei Brücken {E, F}, {I, J} und {K, L}.

Der Block-Schnittknoten-Baum, 1966 von Harary und Prins eingeführt, hat einen Knoten für jeden Block und einen für jeden Artikulationspunkt, mit einer Kante, wann immer der Artikulationspunkt im Block liegt. Für einen zusammenhängenden Graphen ist er immer ein Baum. Für Komponente 1 hat er 5 Blockknoten und 4 Artikulationspunkt-Knoten, also 9 Knoten, verbunden durch 8 Kanten. Der Baum ist das grobe Skelett des Graphen: Er beantwortet „welche Ausfälle trennen welche Teile“, ohne in einen Block hineinzuschauen.

Brücken liefern eine parallele Zerlegung. Löschen Sie jede Brücke, und der Rest zerfällt in 2-kantenzusammenhängende Komponenten, Teile, die den Verlust jeder einzelnen Kante überstehen. Das Beispiel hat fünf: {A, B, C, D, E}, {F, G, H, I} und die einzelnen Knoten {J}, {K} und {L}. Beachten Sie, dass die erste davon eine einzige 2-kantenzusammenhängende Komponente, aber zwei Blöcke ist. Der Schmetterlingsgraph übersteht jeden einzelnen Kantenausfall, aber nicht den Ausfall von C.

Zwei klassische Sätze erklären, was „kein Artikulationspunkt“ wirklich bringt. Whitney zeigte 1932, dass ein Graph mit mindestens drei Knoten genau dann 2-zusammenhängend ist, wenn je zwei Knoten durch zwei Wege verbunden sind, die keinen inneren Knoten gemeinsam haben, was dasselbe ist wie die Aussage, dass je zwei Knoten auf einem gemeinsamen Kreis liegen. Und Robbins bewies 1939, dass sich die Kanten eines zusammenhängenden Graphen genau dann so orientieren lassen, dass jeder Knoten jeden anderen erreicht, wenn der Graph keine Brücke hat, der Satz im Zentrum des Leitfadens zu gerichteten und ungerichteten Graphen.

9. Wie stark ein Graph zusammenhängt

Brücken und Artikulationspunkte sind die erste Sprosse einer Leiter. Der Knotenzusammenhang κ(G) ist die kleinste Anzahl von Knoten, deren Entfernen den Graphen trennt oder einen einzelnen Knoten übrig lässt. Der Kantenzusammenhang λ(G) ist die kleinste Anzahl von Kanten, deren Entfernen ihn trennt. Ein zusammenhängender Graph mit mindestens drei Knoten hat genau dann einen Artikulationspunkt, wenn κ = 1 gilt, und ein zusammenhängender Graph mit mindestens zwei Knoten hat genau dann eine Brücke, wenn λ = 1 gilt. Whitneys Ungleichung von 1932 verknüpft beide mit dem Minimalgrad δ(G):

κ(G)  ≤  λ(G)  ≤  δ(G)

zwei Dreiecke mit gemeinsamem C    κ = 1   λ = 2   δ = 2      ein Artikulationspunkt, aber keine Brücke
Komponente 1 des Beispiels         κ = 1   λ = 1   δ = 1      J hängt an einer einzigen Kante
jeder Kreis                        κ = 2   λ = 2   δ = 2

Die rechte Ungleichung ist leicht: Löscht man die Kanten an einem Knoten minimalen Grades, wird er isoliert. Die linke besagt, dass Knotenausfälle immer mindestens so gefährlich sind wie Kantenausfälle, und der Schmetterlingsgraph zeigt, dass die Lücke echt sein kann.

Der Satz von Menger aus dem Jahr 1927 verwandelt diese Minima in Maxima. Die kleinste Anzahl von Kanten, deren Entfernen zwei Knoten u und v trennt, ist gleich der größten Anzahl von Wegen von u nach v, die keine Kante gemeinsam haben. Die Knotenversion ist dieselbe Aussage mit intern disjunkten Wegen, und sie verlangt, dass u und v nicht benachbart sind, da keine Menge anderer Knoten zwei Nachbarn trennt. Der Satz von Menger ist ein Spezialfall von maximaler Fluss gleich minimaler Schnitt, und so wird der Zusammenhang in der Praxis auch berechnet.

10. Wo das wichtig ist

Komponenten, Brücken und Artikulationspunkte sind das Vokabular der Ausfallanalyse. Wann immer sich ein System als Dinge und Verbindungen modellieren lässt, benennen diese Begriffe seine Schwachstellen.

Komponenten erklären auch eines der berühmtesten Ergebnisse über Zufallsgraphen. Erdős und Rényi zeigten 1960: Fügt man zu n isolierten Knoten zufällige Kanten hinzu, bleiben die Komponenten klein, bis der Durchschnittsgrad 1 überschreitet, und dann erscheint ziemlich plötzlich eine einzige Riesenkomponente mit einem konstanten Anteil aller Knoten. Dieser Phasenübergang, behandelt in der Geschichte der Graphentheorie, ist der Grund, warum große reale Netzwerke fast immer eine dominierende Komponente mit einigen verstreuten kleinen darum herum haben.

Wenn sich der Graph ständig ändert, wird Zusammenhang zu einem Datenstrukturproblem. Reine Einfügungen sind mit Union-Find leicht. Löschungen sind viel schwerer, weil das Entfernen einer Kante eine Komponente teilen kann oder auch nicht, und um das herauszufinden, scheint man eine Suche zu brauchen. Holm, de Lichtenberg und Thorup zeigten 2001, dass sich Zusammenhang, 2-Kantenzusammenhang und zweifacher Zusammenhang unter Einfügungen und Löschungen in polylogarithmischer amortisierter Zeit pro Aktualisierung aufrechterhalten lassen.

11. Gerichtete Graphen: schwacher und starker Zusammenhang

In einem gerichteten Graphen ist „u erreicht v“ nicht mehr symmetrisch, also keine Äquivalenzrelation, und „die Komponente von v“ erfordert eine Entscheidung. Es gibt zwei übliche.

• Schwach zusammenhängende Komponenten ignorieren die Richtung: Sie sind die Komponenten des zugrunde liegenden ungerichteten Graphen, und alles in diesem Artikel gilt für sie unverändert.
• Stark zusammenhängende Komponenten verlangen Erreichbarkeit in beide Richtungen. „u erreicht v und v erreicht u“ ist wieder eine Äquivalenzrelation, und ihre Klassen sind die starken Komponenten, die sich in linearer Zeit mit dem Algorithmus von Tarjan oder Kosaraju finden lassen, wie der Leitfaden zu stark zusammenhängenden Komponenten erklärt.

Wendet man den ungerichteten Komponentencode auf eine gerichtete Adjazenzliste an, erhält man keine der beiden Antworten. Er folgt Kanten nur vorwärts, also hängen die „Komponenten“, die er meldet, davon ab, wo jede Suche zufällig gestartet ist. Symmetrisieren Sie entweder zuerst die Listen, um schwache Komponenten zu erhalten, oder verwenden Sie einen Algorithmus für starke Komponenten.

12. Häufige Fehler

13. Glossar

15. Quellen

Die Definitionen, Sätze und Zuschreibungen oben stammen aus diesen Quellen, in chronologischer Reihenfolge.

1. Menger, K. (1927). "Zur allgemeinen Kurventheorie." Fundamenta Mathematicae 10, 96 bis 115. Disjunkte Wege und trennende Mengen.
2. Whitney, H. (1932). "Congruent Graphs and the Connectivity of Graphs." American Journal of Mathematics 54(1), 150 bis 168.
3. Whitney, H. (1932). "Non-separable and Planar Graphs." Transactions of the American Mathematical Society 34(2), 339 bis 362. Zusammen mit der obigen Arbeit: die Ungleichung zwischen Knotenzusammenhang, Kantenzusammenhang und Minimalgrad sowie die Charakterisierung 2-zusammenhängender Graphen durch disjunkte Wege.
4. Robbins, H. E. (1939). "A Theorem on Graphs, with an Application to a Problem of Traffic Control." American Mathematical Monthly 46(5), 281 bis 283.
5. Erdős, P. und Rényi, A. (1960). "On the Evolution of Random Graphs." Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5, 17 bis 61. Die Riesenkomponente.
6. Galler, B. A. und Fischer, M. J. (1964). "An Improved Equivalence Algorithm." Communications of the ACM 7(5), 301 bis 303. Die Union-Find-Idee zum Vereinigen von Klassen.
7. Harary, F. und Prins, G. (1966). "The Block-Cutpoint-Tree of a Graph." Publicationes Mathematicae Debrecen 13, 103 bis 107.
8. Rosenfeld, A. und Pfaltz, J. L. (1966). "Sequential Operations in Digital Picture Processing." Journal of the ACM 13(4), 471 bis 494. Komponentenmarkierung in Bildern.
9. Tarjan, R. E. (1972). "Depth-First Search and Linear Graph Algorithms." SIAM Journal on Computing 1(2), 146 bis 160.
10. Hopcroft, J. E. und Tarjan, R. E. (1973). "Algorithm 447: Efficient Algorithms for Graph Manipulation." Communications of the ACM 16(6), 372 bis 378. Zweifach zusammenhängende Komponenten und Artikulationspunkte in linearer Zeit.
11. Tarjan, R. E. (1974). "A Note on Finding the Bridges of a Graph." Information Processing Letters 2(6), 160 bis 161.
12. Holm, J., de Lichtenberg, K. und Thorup, M. (2001). "Poly-logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity." Journal of the ACM 48(4), 723 bis 760.
13. Diestel, R. (2017). Graph Theory, 5. Auflage. Graduate Texts in Mathematics 173. Berlin: Springer.