Kreise in Graphen und Zyklenerkennung

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Kantenfolgen, Kantenzüge, Pfade und Kreise

Ein Kreis oder Zyklus ist eine Route durch einen Graphen, die dorthin zurückkehrt, wo sie begonnen hat, ohne unterwegs etwas zweimal zu benutzen. Das klingt einfach, aber „Route“ kann vier verschiedene Dinge bedeuten, und die meiste Verwirrung über Kreise entsteht, wenn man sie verwechselt. Sie unterscheiden sich nur darin, was sich wiederholen darf.

• Eine Kantenfolge ist eine Folge von Knoten, in der je zwei aufeinanderfolgende Knoten durch eine Kante verbunden sind. Knoten und Kanten dürfen sich beide wiederholen. Ihre Länge ist die Anzahl der Kanten, die sie benutzt, mit Wiederholungen gezählt.
• Ein Kantenzug ist eine Kantenfolge, die keine Kante zweimal benutzt. Knoten dürfen sich weiterhin wiederholen.
• Ein Pfad ist eine Kantenfolge, die keinen Knoten zweimal besucht, und kann daher auch keine Kante wiederholen.
• Endet eine Kantenfolge dort, wo sie begann, so heißt sie geschlossen und ein solcher Kantenzug entsprechend ein geschlossener Kantenzug. Ein Kreis ist ein geschlossener Kantenzug positiver Länge, dessen einziger wiederholter Knoten derjenige ist, an dem er beginnt und endet.

Lehrbücher verwenden diese Wörter nicht alle gleich. Manche sagen „Weg“ zu dem, was hier Kantenfolge heißt, und manche sagen „Zyklus“ oder „geschlossener Kantenzug“ zu dem, was hier Kreis heißt. Die Ideen sind stabil, auch wenn die Namen es nicht sind; prüfen Sie also beim Lesen eines Satzes, welcher Begriff gemeint ist. In einem einfachen Graphen braucht ein Kreis mindestens drei Knoten. In einem Multigraphen ist eine Schleife ein Kreis der Länge 1, und zwei parallele Kanten bilden einen Kreis der Länge 2.

Ein einziger ungerichteter Graph trägt den größten Teil des Artikels. Er besteht aus acht Knoten und zehn Kanten: einem Dreieck A, B, C oben, zwei Quadraten B, C, E, D und D, E, G, F darunter sowie einem Knoten H als Blatt an G.

V = {A, B, C, D, E, F, G, H}                          8 Knoten
E = {AB, BC, CA, BD, CE, DE, DF, EG, FG, GH}          10 Kanten

Zwei Tatsachen über geschlossene Kantenfolgen werden immer wieder gebraucht. Erstens muss eine geschlossene Kantenfolge keinen Kreis enthalten: A, B, A ist geschlossen, geht aber nur entlang einer Kante hin und entlang derselben Kante zurück. Zweitens enthält ein geschlossener Kantenzug positiver Länge immer einen Kreis. Wiederholt er in der Mitte einen Knoten, schneidet man ihn dort in zwei kürzere geschlossene Kantenzüge und wiederholt das Argument mit einem von beiden; der Vorgang endet bei einem geschlossenen Kantenzug ohne wiederholten Knoten, und das ist ein Kreis. Abschnitt 8 braucht eine Variante desselben Arguments für Kantenfolgen ungerader Länge.

2. Taillenweite, Umfang und kreisfreie Graphen

Die Taillenweite eines Graphen ist die Länge seines kürzesten Kreises, der Umfang die Länge seines längsten. Das Beispiel hat insgesamt sechs Kreise der Längen 3, 4, 4, 5, 6 und 7, also ist seine Taillenweite 3 und sein Umfang 7. Der längste Kreis, A, B, D, F, G, E, C, geht durch jeden Knoten außer H, der nur eine Kante hat und daher auf überhaupt keinem Kreis liegen kann.

Ein Graph ohne Kreis heißt kreisfrei oder azyklisch. Ein kreisfreier ungerichteter Graph ist ein Wald, und ein zusammenhängender Wald ist ein Baum. Ein Wald mit n Knoten und k Komponenten hat genau n − k Kanten, also liefert das Zählen von Kanten den schnellsten Kreistest überhaupt:

Ein Graph mit n Knoten, m Kanten und k Komponenten enthält genau dann einen Kreis, wenn m > n − k gilt. Insbesondere hat jeder Graph mit mindestens so vielen Kanten wie Knoten einen Kreis.

Für das Beispiel gilt 10 > 8 − 1, also muss es einen Kreis enthalten, bevor überhaupt jemand danach sucht. Eine Gradbedingung funktioniert ebenfalls: Hat jeder Knoten mindestens Grad 2, dann hat der Graph einen Kreis, und zwar sogar einen der Länge mindestens δ + 1, wobei δ der Minimalgrad ist. Der Beweis ist ein Klassiker. Man nehme einen längsten Pfad v0, v1, …, vℓ. Jeder Nachbar von v0 liegt auf dem Pfad, da sich der Pfad sonst verlängern ließe. v0 hat mindestens δ Nachbarn darauf, also ist der am weitesten entfernte mindestens vδ, und die Kante zurück zu ihm schließt einen Kreis der Länge mindestens δ + 1, eine Beobachtung, die in Diracs Arbeit von 1952 vorkommt. Dies wurde per Brute Force an jedem Graphen mit bis zu sechs Knoten geprüft.

In einem gerichteten Graphen muss ein Kreis den Pfeilen folgen, und ein kreisfreier gerichteter Graph heißt DAG. DAGs sind genau die gerichteten Graphen, deren Knoten sich so in eine Reihe legen lassen, dass jeder Pfeil nach vorn zeigt, und genau das liefert eine topologische Sortierung. Beachten Sie, dass ein DAG viele Kanten haben kann: Der obige Kantenzähltest gilt nur für ungerichtete Graphen.

Die Taillenweite zu finden ist schwieriger, als irgendeinen Kreis zu finden. Eine Breitensuche von jedem Knoten aus, die jede dabei angetroffene Nicht-Baumkante prüft, liefert die Taillenweite in O(nm) Zeit. Die Arbeit von Itai und Rodeh aus dem Jahr 1978 über minimale Kreise nennt diese Schranke, zusammen mit einem schnelleren Verfahren für einen Kreis, der höchstens eine Kante länger ist als der kürzeste.

3. Einen Kreis in einem ungerichteten Graphen erkennen

Wenn Sie nur ein Ja oder Nein brauchen, entscheidet die Kantenzahl: Berechnen Sie die Komponenten und vergleichen Sie m mit n − k. Meist wollen Sie mehr, nämlich einen tatsächlichen Kreis, den Sie jemandem zeigen können. Ein Kreis ist ein Zertifikat: Jeder kann ihn Kante für Kante prüfen, und er beweist die Antwort, ohne dass man Ihrem Programm vertrauen muss. Die Tiefensuche liefert einen fast umsonst.

Die entscheidende Tatsache ist, dass eine Tiefensuche in einem ungerichteten Graphen jede Kante einer von zwei Arten zuordnet. Eine Baumkante führt zu einem Knoten, der zum ersten Mal gesehen wird. Eine Rückwärtskante führt zu einem Knoten, der schon auf dem Weg nach unten liegt, einem Vorfahren des aktuellen Knotens. Andere Arten gibt es nicht, also hat der Graph genau dann einen Kreis, wenn die Suche auf eine Rückwärtskante trifft, und der Kreis besteht aus der Rückwärtskante und dem Baumpfad, den sie überspringt.

def find_cycle_undirected(vertices, edges):
    """Gibt die Knoten eines Kreises der Reihe nach zurück, oder None, wenn der Graph ein Wald ist."""
    adj = {v: [] for v in vertices}
    for i, (u, v) in enumerate(edges):
        adj[u].append((v, i))
        adj[v].append((u, i))
    parent = {}                                   # Knoten -> (Elternknoten, Kanten-ID)
    for root in vertices:                         # eine Suche pro Komponente
        if root in parent:
            continue
        parent[root] = (None, None)
        stack = [(root, iter(adj[root]))]
        while stack:
            u, it = stack[-1]
            for v, i in it:
                if i == parent[u][1]:             # die Kante, über die wir kamen, kein Kreis
                    continue
                if v in parent:                   # Rückwärtskante u-v: von u hinauf bis v gehen
                    cycle = [u]
                    while cycle[-1] != v:
                        cycle.append(parent[cycle[-1]][0])
                    return cycle[::-1]
                parent[v] = (u, i)
                stack.append((v, iter(adj[v])))
                break
            else:
                stack.pop()
    return None

V = 'ABCDEFGH'
E = ['AB', 'BC', 'CA', 'BD', 'CE', 'DE', 'DF', 'EG', 'FG', 'GH']
print(find_cycle_undirected(V, E))
# ['A', 'B', 'C']
print(find_cycle_undirected(V, ['AB', 'BC', 'CE', 'DE', 'DF', 'FG', 'GH']))
# None
print(find_cycle_undirected('xy', ['xy', 'xy']))
# ['x', 'y']

Drei Details machen dies korrekt statt nur fast korrekt. Die Suche merkt sich die Kante, über die sie gekommen ist und überspringt nur diese Kante; ohne das Überspringen sähe jede Kante wie ein Kreis der Länge 2 aus, hin und sofort wieder zurück. Das Überspringen anhand der Identität der Kante statt anhand „des Nachbarn, der mein Elternknoten ist“ hält den Code auch für Multigraphen richtig, in denen eine doppelte Kante wirklich ein Kreis der Länge 2 ist, wie der dritte Aufruf zeigt. Die äußere Schleife startet eine Suche pro Komponente, denn ein Kreis kann in jeder von ihnen liegen. Und der Stapel ist explizit, sodass ein langer Pfad Pythons Rekursionslimit nicht überschreiten kann.

Werden die Nachbarn in alphabetischer Reihenfolge genommen, so geht die Suche von A aus den Pfad A, B, C hinab und findet bei C die Kante zurück zu A. A ist bereits besucht, und die Kante ist nicht die, über die die Suche gekommen ist, also klettert der Code die Elternzeiger von C bis A hinauf und gibt das Dreieck zurück. Hätte die Suche weitergemacht, wäre sie mit E, D, F, G, H fortgefahren, einem einzigen Pfad durch alle acht Knoten, und hätte zwei weitere Rückwärtskanten gefunden, D–B und G–E. Sieben Baumkanten plus drei Rückwärtskanten ergeben alle zehn.

Bei der Laufzeit gibt es einen angenehmen Bonus. Vor der ersten Rückwärtskante ist jeder Adjazenzeintrag, den die Suche liest, entweder eine Baumkante, von denen es höchstens n − 1 gibt, oder die Kante zurück zu einem Elternknoten, ebenfalls höchstens n − 1 an der Zahl. Die Suche selbst liest also höchstens 2n − 1 Einträge, bevor sie einen Kreis findet oder endet, egal wie viele Kanten der Graph hat. Diese Schranke wurde durch Zählen auf 4.000 zufälligen Graphen geprüft. Das Einlesen der Eingabe zum Aufbau der Adjazenzlisten kostet weiterhin O(V + E), die Suche selbst aber nicht.

4. Union-Find: Kreise Kante für Kante

Manchmal treffen die Kanten eine nach der anderen ein, und die Frage ist, welche Kante als erste einen Kreis erzeugt. Eine Datenstruktur für Union-Find beantwortet das ganz ohne Suche. Sie hält die Knoten in Gruppen, eine Gruppe pro bisher aufgebauter Komponente. Eine Kante zwischen zwei verschiedenen Gruppen verschmilzt sie. Eine Kante, deren beide Enden schon in derselben Gruppe liegen, verbindet zwei Knoten, die bereits verbunden waren, und schließt daher zusammen mit dem vorhandenen Pfad zwischen ihnen einen Kreis.

def first_cycle_edge(vertices, edges):
    """Fügt Kanten einzeln hinzu; gibt die erste Kante zurück, die einen Kreis schließt, oder None."""
    root = {v: v for v in vertices}
    def find(x):
        while root[x] != x:
            root[x] = root[root[x]]               # Pfadhalbierung
            x = root[x]
        return x
    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:                              # u und v waren bereits verbunden
            return u + v
        root[ru] = rv
    return None

print(first_cycle_edge('ABCDEFGH', ['AB', 'BD', 'DF', 'FG', 'GH', 'BC', 'CE', 'EG', 'DE', 'CA']))
# EG

In dieser Reihenfolge bilden die ersten fünf Kanten den Pfad A, B, D, F, G, H, dann hängen B–C und C–E zwei weitere Knoten daran. Wenn E–G eintrifft, haben E und G bereits dieselbe Wurzel, und der Kreis, den die Kante schließt, ist B, C, E, G, F, D, sechs Kanten lang. Genau diesen Test wendet Kruskals Algorithmus auf jede Kante an, bevor er sie einem minimalen Spannbaum hinzufügt.

Union-Find sagt Ihnen, welche Kante einen Kreis schließt, nicht wo der Kreis verläuft. Um den Kreis anzugeben, brauchen Sie noch den Pfad zwischen den beiden Enden im bisher aufgebauten Wald, den eine kurze Suche über die akzeptierten Kanten findet. Und Union-Find funktioniert nur für ungerichtete Graphen. Im gerichteten Graphen mit den Pfeilen A→B, B→C und A→C verbindet der dritte Pfeil zwei Knoten, die schon in einer Gruppe sind, und doch gibt es keinen gerichteten Kreis: Wer den Pfeilen folgt, kommt nie zurück zu A.

5. Gerichtete Graphen: drei Farben

In einem gerichteten Graphen liefert der ungerichtete Test falsche Antworten. Nehmen Sie sechs Aufgaben mit diesen Abhängigkeiten:

A → B    A → C    B → D    C → D    C → E    E → F

Eine Tiefensuche von A aus erreicht D über B. Später, beim Erkunden von C, trifft sie auf den Pfeil C→D und findet D bereits besucht vor. Eine einfache Prüfung auf „schon besucht“ hält das für einen Kreis, aber es gibt keinen: A→B→D und A→C→D sind zwei Routen zum selben Ort, keine Route, die zurückkehrt. Auf 6.000 zufälligen gerichteten Graphen meldete die einfache Prüfung in 1.320 Graphen einen Kreis, obwohl sie keinen hatten.

Die Lösung: Man merkt sich nicht nur, ob ein Knoten besucht wurde, sondern auch, ob seine Suche noch läuft. Jeder Knoten erhält eine von drei Farben:

• WEISS: noch nicht erreicht.
• GRAU: erreicht, und seine Suche ist noch nicht beendet. Die grauen Knoten sind genau der aktuelle Pfad von der Wurzel bis zum gerade erkundeten Knoten.
• SCHWARZ: beendet. Alles, was von ihm aus erreichbar ist, wurde erkundet, und dort wurde kein Kreis gefunden.

Eine gerichtete Tiefensuche teilt die Kanten in vier Arten ein: Baumkanten zu weißen Knoten, Rückwärtskanten zu grauen Vorfahren, Vorwärtskanten zu schwarzen Nachfahren und Querkanten zu schwarzen Knoten in einem anderen Zweig oder aus einer früheren Suche. Nur eine Rückwärtskante schließt einen Kreis, denn nur bei einem grauen Knoten ist garantiert, dass er den aktuellen erreicht. Das ergibt den klassischen Satz: Ein gerichteter Graph hat genau dann einen Kreis, wenn eine Tiefensuche eine Rückwärtskante findet, was dasselbe ist, wie einen Pfeil in einen grauen Knoten zu finden. Der graue Pfad selbst ist das Zertifikat.

WHITE, GRAY, BLACK = 0, 1, 2

def find_cycle_directed(graph):
    """Gibt einen gerichteten Kreis als Liste von Knoten zurück, oder None, wenn der Graph ein DAG ist."""
    color = {v: WHITE for v in graph}
    for root in graph:
        if color[root] != WHITE:
            continue
        color[root] = GRAY
        path = [root]                             # die grauen (GRAY) Knoten, der Reihe nach
        stack = [iter(graph[root])]
        while stack:
            for v in stack[-1]:
                if color[v] == GRAY:              # Rückwärtskante: v liegt auf dem aktuellen Pfad
                    return path[path.index(v):]
                if color[v] == WHITE:
                    color[v] = GRAY
                    path.append(v)
                    stack.append(iter(graph[v]))
                    break
            else:                                 # alle ausgehenden Kanten erledigt: Knoten abschließen
                color[path.pop()] = BLACK
                stack.pop()
    return None

dag = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D', 'E'], 'D': [], 'E': ['F'], 'F': []}
print(find_cycle_directed(dag))
# None
dag['F'].append('C')                              # eine Kante mehr: F -> C
print(find_cycle_directed(dag))
# ['C', 'E', 'F']

Bei den sechs Aufgaben wird D schwarz, bevor C erkundet wird, also ist C→D eine Querkante und wird zu Recht ignoriert. Fügt man einen Pfeil hinzu, F→C, ändert sich das Bild: Die Suche geht C, E, F, alle grau, und der neue Pfeil zeigt zurück auf C, der noch grau ist. Der graue Pfad von C bis F wird als Kreis zurückgegeben. Eine Schleife v→v wird ebenfalls behandelt: v ist grau, wenn sein eigener Pfeil gelesen wird, und der zurückgegebene Kreis ist einfach [v].

6. Kahns Algorithmus: Kreise als festgefahrene topologische Sortierung

Die zweite Standardmethode braucht weder Rekursion noch Farben. Ein Knoten mit Eingangsgrad 0 hängt von nichts ab und kann daher gefahrlos zuerst kommen. Kahns Algorithmus, veröffentlicht 1962, entfernt wiederholt einen solchen Knoten und verringert die Eingangsgrade seiner Nachfolger. Wird jeder Knoten entfernt, ist die Entfernungsreihenfolge eine topologische Ordnung und der Graph ein DAG. Bricht der Vorgang vorzeitig ab, hat der Graph einen Kreis.

from collections import deque

def kahn(graph):
    """Topologische Ordnung, wenn der Graph ein DAG ist, sonst (None, ein Kreis)."""
    indeg = {v: 0 for v in graph}
    for u in graph:
        for v in graph[u]:
            indeg[v] += 1
    ready = deque(v for v in graph if indeg[v] == 0)
    order = []
    while ready:
        u = ready.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                ready.append(v)
    if len(order) == len(graph):
        return order, None
    left = {v for v in graph if indeg[v] > 0}     # jeder von ihnen hat einen Vorgänger in left
    pred = {v: u for u in left for v in graph[u] if v in left}
    v, seen = next(iter(sorted(left))), []
    while v not in seen:                          # rückwärts gehen, bis sich ein Knoten wiederholt
        seen.append(v)
        v = pred[v]
    return None, seen[seen.index(v):][::-1]

graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D', 'E'], 'D': [], 'E': ['F'], 'F': ['C']}
print(kahn(graph))
# (None, ['E', 'F', 'C'])
graph['F'] = []
print(kahn(graph))
# (['A', 'B', 'C', 'D', 'E', 'F'], None)

Warum beweist das Steckenbleiben einen Kreis? Jeder übrig gebliebene Knoten hat noch mindestens einen eingehenden Pfeil, und dieser Pfeil kommt von einem übrig gebliebenen Knoten, denn jeder entfernte Knoten hat seine Pfeile bereits von den Zählern abgezogen. Von jedem übrig gebliebenen Knoten aus kann man also entlang eines Pfeils rückwärts zu einem übrig gebliebenen Knoten gehen, immer weiter. Bei endlich vielen Knoten muss diese Rückwärtswanderung einen Knoten wiederholen, und das Stück zwischen den beiden Besuchen ist ein Kreis. Der Code führt genau diese Wanderung aus und meldet E, F, C, denselben Kreis wie zuvor, nur von einem anderen Startpunkt aus gelesen.

Ein Detail wird leicht falsch gemacht. Im Beispiel entfernt Kahns Algorithmus A und B und bleibt dann stecken, während C, D, E und F noch vorhanden sind. D liegt auf keinem Kreis; er steckt nur fest, denn er wartet auf C. Die übrig gebliebenen Knoten sind die Kreise plus alles, was ihnen nachgelagert ist, also ist es ein Fehler, die übrig gebliebene Menge als „den Kreis“ zu melden. Ohne den Pfeil F→C gibt derselbe Code die Reihenfolge A, B, C, D, E, F zurück, eine von neun gültigen Reihenfolgen dieses DAG.

Beide Methoden laufen in O(V + E) Zeit. Die Version mit Tiefensuche liefert Ihnen direkt einen Kreis, während Kahns Version Ihnen eine topologische Ordnung liefert, wann immer eine existiert, und das ist meist das, was ein Scheduler oder Build-Tool ohnehin wollte.

7. Wie viele Kreise? Der Zyklenraum

Kreise einzeln zu zählen, gerät schnell außer Kontrolle. Der vollständige Graph K4 hat 7 Kreise, K5 hat 37, K6 hat 197 und K10 hat 556.014. Sie alle aufzulisten ist möglich, und Johnsons Algorithmus von 1975 tut das für gerichtete Graphen in O((n + e)(c + 1)) Zeit für c Kreise, aber schon die Ausgabe allein kann exponentiell in der Größe des Graphen sein.

Es gibt eine viel bessere Zählung. Betrachten Sie einen Kreis als Menge von Kanten und verknüpfen Sie zwei Kantenmengen durch die symmetrische Differenz: Behalten Sie die Kanten, die in genau einer der beiden liegen. Mit dieser Operation bilden die Teilgraphen, in denen jeder Knoten geraden Grad hat, einen Vektorraum über dem Körper mit zwei Elementen, den sogenannten Zyklenraum. Jeder Kreis liegt darin, und die Dimension des Zyklenraums ist

die zyklomatische Zahl oder der Kreisrang: m − n + k.

Eine Basis ist leicht zu konstruieren. Nehmen Sie einen beliebigen aufspannenden Wald, der n − k Kanten hat. Jede der übrigen m − n + k Kanten schließt mit dem Wald genau einen Kreis, ihren Fundamentalkreis, und diese Kreise sind unabhängig, weil jeder eine Kante enthält, die kein anderer enthält. Die Idee geht auf Kirchhoff zurück, der sie 1847 nutzte, um die unabhängigen Maschengleichungen eines elektrischen Netzwerks zu zählen; der Name zyklomatische Zahl kam später. Eine Tiefensuche liefert die Basis direkt: Ändern Sie den Kreisfinder so, dass er jede Rückwärtskante festhält, statt bei der ersten anzuhalten.

def cycle_basis(vertices, edges):
    """Ein Kreis pro Nicht-Baumkante eines DFS-Waldes: insgesamt m - n + k Kreise."""
    adj = {v: [] for v in vertices}
    for i, (u, v) in enumerate(edges):
        adj[u].append((v, i))
        adj[v].append((u, i))
    parent, used, basis = {}, set(), []
    for root in vertices:
        if root in parent:
            continue
        parent[root] = None
        stack = [(root, iter(adj[root]))]
        while stack:
            u, it = stack[-1]
            for v, i in it:
                if i in used:                     # Baumkante oder bereits gezählte Rückwärtskante
                    continue
                used.add(i)
                if v in parent:                   # Rückwärtskante: ihren Kreis festhalten, weitermachen
                    cycle = [u]
                    while cycle[-1] != v:
                        cycle.append(parent[cycle[-1]])
                    basis.append(cycle[::-1])
                    continue
                parent[v] = u
                stack.append((v, iter(adj[v])))
                break
            else:
                stack.pop()
    return basis

V = 'ABCDEFGH'
E = ['AB', 'BC', 'CA', 'BD', 'CE', 'DE', 'DF', 'EG', 'FG', 'GH']
basis = cycle_basis(V, E)
print(len(basis), len(E) - len(V) + 1, basis)
# 3 3 [['A', 'B', 'C'], ['B', 'C', 'E', 'D'], ['E', 'D', 'F', 'G']]

def edges_of(cycle):
    return {''.join(sorted(p)) for p in zip(cycle, cycle[1:] + cycle[:1])}
total = edges_of(basis[0]) ^ edges_of(basis[1]) ^ edges_of(basis[2])
print(sorted(total))
# ['AB', 'AC', 'BD', 'CE', 'DF', 'EG', 'FG']

Das Beispiel hat 10 − 8 + 1 = 3 unabhängige Kreise, und der Suchbaum aus Abschnitt 3 liefert die drei natürlichsten: das Dreieck und die beiden Quadrate. Ihre symmetrische Differenz hebt die gemeinsamen Kanten B–C und D–E auf und lässt den äußeren Kreis der Länge 7 übrig.

Der Raum hat 23 = 8 Elemente, und es lohnt sich, sie alle zu prüfen. Eines ist leer. Sechs sind die sechs Kreise des Graphen. Das letzte ist das Dreieck zusammen mit dem Quadrat D, E, G, F: Jeder Knoten hat geraden Grad, aber die beiden Kreise haben keinen gemeinsamen Knoten, also ist die Menge kein einzelner Kreis. Elemente des Zyklenraums sind kantendisjunkte Vereinigungen von Kreisen, nicht immer Kreise. Für K10 ist der Abstand zwischen den beiden Zahlen dramatisch: ein Rang von 45 − 10 + 1 = 36 gegenüber 556.014 tatsächlichen Kreisen.

Dieselbe Zahl taucht in der Softwaretechnik auf. McCabes zyklomatische Komplexität von 1976 misst ein Programm am Kreisrang seines Kontrollflussgraphen, als E − N + 2P für E Kanten, N Knoten und P zusammenhängende Teile. Das zusätzliche P rührt daher, dass man sich eine weitere Kante von jedem Ausgang zurück zu seinem Eingang denkt, die jeden Pfad durch das Programm in einen Kreis verwandelt.

8. Ungerade Kreise und bipartite Graphen

Die Länge eines Kreises ist so wichtig wie seine Existenz. Ein Graph ist bipartit, das heißt, seine Knoten zerfallen in zwei Seiten, sodass jede Kante zwischen ihnen verläuft, genau dann, wenn er keinen ungeraden Kreis hat. Eine Richtung ist sofort klar: Ein Kreis wechselt die Seiten ab, also kehrt er nach einer geraden Anzahl von Schritten heim. Die andere Richtung, 1916 von Kőnig bewiesen, beruht auf diesem Lemma:

Jede geschlossene Kantenfolge ungerader Länge enthält einen Kreis ungerader Länge.

Nehmen Sie eine kürzeste geschlossene Kantenfolge ungerader Länge. Wiederholt sie in der Mitte einen Knoten, schneiden Sie sie dort in zwei kürzere geschlossene Kantenfolgen. Ihre Längen ergeben zusammen eine ungerade Zahl, also ist eine von ihnen ungerade, im Widerspruch zur Wahl der kürzesten. Die kürzeste ungerade geschlossene Kantenfolge wiederholt also nichts, und sie ist ein ungerader Kreis. (Ihre Länge ist mindestens 3, denn eine geschlossene Kantenfolge der Länge 1 bräuchte eine Schleife.)

In der Praxis ist der Test eine Zweifärbung per Breitensuche: Färben Sie den Startknoten, geben Sie jedem Nachbarn die entgegengesetzte Farbe und suchen Sie nach einer Kante, deren beide Enden dieselbe Farbe erhalten. Findet man eine, so bilden die beiden Baumpfade von ihren Enden hinauf zu ihrem nächsten gemeinsamen Vorfahren zusammen mit der Kante selbst einen ungeraden Kreis, und das ist das Zertifikat dafür, dass keine Zweifärbung existiert. Das Beispiel ist nicht bipartit: Drei seiner sechs Kreise, mit den Längen 3, 5 und 7, sind ungerade, und schon das Dreieck allein genügt, um das zu sehen.

9. Eulerkreise und Hamiltonkreise

Zwei berühmte Probleme verlangen besondere geschlossene Routen, und sie liegen auf entgegengesetzten Seiten einer tiefen Kluft.

• Ein Eulerkreis benutzt jede Kante genau einmal. Er ist trotz seines Namens ein geschlossener Kantenzug und meist kein Kreis, da er einen Knoten viele Male durchlaufen kann. Eulers Arbeit von 1736 über die Brücken von Königsberg zeigte, dass dann jeder Knoten geraden Grad haben muss, und Hierholzers Arbeit von 1873 bewies die Umkehrung: Ein zusammenhängender Graph, isolierte Knoten nicht mitgezählt, hat genau dann einen Eulerkreis, wenn alle seine Grade gerade sind. Die ganze Geschichte steht im Leitfaden zu Eulerwegen und Eulerkreisen.
• Ein Hamiltonkreis besucht jeden Knoten genau einmal. Ein vergleichbarer Test ist nicht bekannt. Zu entscheiden, ob einer existiert, ist NP-vollständig, eines der 21 Probleme auf Karps Liste von 1972. Hinreichende Bedingungen gibt es, die bekannteste ist der Satz von Dirac aus dem Jahr 1952: Ein einfacher Graph mit n ≥ 3 Knoten, in dem jeder Knoten mindestens Grad n/2 hat, besitzt einen Hamiltonkreis.

Das Beispiel erfüllt beides nicht, aus einfachen Gründen. Sechs seiner Knoten, B, C, D, E, G und H, haben ungeraden Grad, also hat es keinen Eulerkreis, und da mehr als zwei Grade ungerade sind, nicht einmal einen offenen Eulerzug. Und H hat Grad 1, also kann kein Kreis durch ihn gehen; das Bestmögliche ist der 7-Kreis, der nur H auslässt. Das Hamiltonproblem mit Entfernungen ist das Problem des Handlungsreisenden.

10. Kreise mit Gewichten: negative Kreise

Sobald Kanten Gewichte tragen, hat ein Kreis ein Gesamtgewicht, und ein negativer Kreis, also einer, dessen Gewichte sich zu weniger als null summieren, hebelt kürzeste Pfade aus. Ihn ein weiteres Mal zu durchlaufen senkt die Kosten immer, sodass Kantenfolgen zu jedem vom Kreis aus erreichbaren Knoten überhaupt keine kürzeste Länge haben. Der Bellman-Ford-Algorithmus erkennt das. Ein kürzester Pfad ohne negativen Kreis hat höchstens n − 1 Kanten, also sind nach n − 1 Runden, in denen jede Kante relaxiert wird, alle Abstände endgültig. Verbessert eine n-te Runde noch etwas, existiert ein negativer Kreis, und wenn man den Vorgängerzeigern von einem verbesserten Knoten aus rückwärts folgt, gelangt man in ihn hinein.

Eine hübsche Anwendung ist Währungsarbitrage. Geben Sie der Kante von Währung a zu Währung b das Gewicht −log r, wobei r der Wechselkurs ist. Eine Runde von Tauschgeschäften multipliziert das Geld mit dem Produkt der Kurse, und das Produkt übersteigt 1 genau dann, wenn die Summe der Gewichte negativ ist. Eine profitable Schleife ist ein negativer Kreis. Geht es um den Kreis mit dem kleinsten durchschnittlichen Gewicht pro Kante, so löst Karps Charakterisierung des minimalen mittleren Kreisgewichts von 1978 diese Frage in O(nm) Zeit.

11. Kreise in einer Folge: Schildkröte und Hase

Eine andere Art der Zyklenerkennung arbeitet auf Graphen, in denen jeder Knoten genau eine ausgehende Kante hat. Wer den next-Zeigern einer verketteten Liste folgt oder eine Funktion f immer wieder auf einen Wert anwendet, durchläuft einen solchen Graphen. Auf einer endlichen Menge muss der Durchlauf irgendwann einen Wert wiederholen, und von da an wiederholt er sich für immer. Die Folge sieht aus wie der griechische Buchstabe Rho, ρ: ein Schwanz der Länge μ mit anschließendem Kreis der Länge λ.

Jeden gesehenen Wert zu speichern würde die Wiederholung finden, kostet aber Speicher proportional zu μ + λ. Die Methode von Schildkröte und Hase verwendet zwei Zeiger und sonst nichts. Die Schildkröte bewegt sich einen Schritt auf einmal, der Hase zwei. Sobald beide auf dem Kreis sind, holt der Hase pro Zug einen Schritt auf, also erreicht er die Schildkröte innerhalb einer Runde. Knuth schrieb die Idee 1969 Robert W. Floyd zu, obwohl keine Arbeit von Floyd bekannt ist, die sie beschreibt.

def floyd(f, x0):
    """Schwanzlänge mu und Kreislänge lam von x0, f(x0), f(f(x0)), ... mit O(1) Speicher."""
    tortoise, hare = f(x0), f(f(x0))
    while tortoise != hare:                       # 1. sich irgendwo auf dem Kreis treffen
        tortoise, hare = f(tortoise), f(f(hare))
    mu, tortoise = 0, x0
    while tortoise != hare:                       # 2. im Gleichschritt bis zum Eingang des Kreises gehen
        tortoise, hare = f(tortoise), f(hare)
        mu += 1
    lam, hare = 1, f(tortoise)
    while tortoise != hare:                       # 3. einmal um den Kreis herumgehen
        hare = f(hare)
        lam += 1
    return mu, lam

f = lambda x: (x * x + 1) % 55
print(floyd(f, 0))
# (4, 6)
seq = [0]
for _ in range(11):
    seq.append(f(seq[-1]))
print(seq)
# [0, 1, 2, 5, 26, 17, 15, 6, 37, 50, 26, 17]

Für f(x) = x2 + 1 mod 55 mit Startwert 0 durchlaufen die Werte 0, 1, 2, 5 und treten dann in die Schleife 26, 17, 15, 6, 37, 50 ein, also gilt μ = 4 und λ = 6. Die beiden Zeiger treffen sich zum ersten Mal nach sechs Zügen der Schildkröte. Die zweite Phase funktioniert, weil am Treffpunkt die Schildkröte eine gewisse Anzahl t von Schritten gemacht hat und der Hase 2t, also ist t ein Vielfaches von λ. Ein Zeiger, der bei x0 neu startet, und einer, der am Treffpunkt bleibt, beide jeweils einen Schritt auf einmal, erreichen daher nach genau μ Schritten gemeinsam den Anfang des Kreises.

Das Verfahren braucht O(μ + λ) Zeit und konstanten Speicher. Brents Variante von 1980, die die Schildkröte bei Zweierpotenzen zum Hasen teleportiert, kommt meist mit weniger Auswertungen von f aus. Beide werden in Pollards Rho-Methode zur Faktorisierung ganzer Zahlen verwendet, wobei f eine Polynomabbildung wie x2 + c modulo der zu faktorisierenden Zahl ist.

12. Wo Zyklenerkennung wichtig ist

Wann immer Pfeile „wartet auf“, „hängt ab von“ oder „verweist auf“ bedeuten, heißt ein Kreis, dass etwas nicht fertig werden, nicht gebaut oder nicht freigegeben werden kann.

Deadlocks sind das Lehrbuchbeispiel. Coffman, Elphick und Shoshani nannten 1971 vier Bedingungen, die alle gelten müssen, damit ein Deadlock (eine Verklemmung) auftritt, und die letzte davon, zirkuläres Warten, ist in der Sprache der Graphen ein Kreis unter den wartenden Aufgaben. Ein System kann Deadlocks verhindern, indem es eine der Bedingungen ausschließt, etwa indem es Sperren immer in einer festen globalen Reihenfolge anfordert, was den Wartegraphen zu einem DAG macht. Oder es lässt Deadlocks zu, sucht von Zeit zu Zeit nach einem Kreis und löst ihn auf, indem es ein Mitglied abbricht.

Speicherverwaltung ist dieselbe Geschichte in anderer Form. Ein Referenzzähler fällt auf null, wenn der letzte Zeiger auf ein Objekt verschwindet, aber zwei Objekte, die aufeinander zeigen, halten die Zähler des jeweils anderen auf 1, selbst wenn nichts anderes sie erreichen kann. Deshalb ergänzt CPython die Referenzzählung um einen separaten Garbage Collector, dessen Aufgabe es ist, solche unerreichbaren Kreise zu finden.

13. Häufige Fehler

14. Glossar

16. Quellen

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

1. Euler, L. (1741). "Solutio problematis ad geometriam situs pertinentis." Commentarii academiae scientiarum Petropolitanae 8, 128 bis 140. Band datiert auf 1736. Die Brücken von Königsberg und die Gradbedingung für Eulerkreise.
2. Kirchhoff, G. (1847). "Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird." Annalen der Physik und Chemie 72(12), 497 bis 508. Spannbäume und ein unabhängiger Kreis pro verbleibender Kante.
3. Hierholzer, C. (1873). "Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren." Mathematische Annalen 6(1), 30 bis 32. Nach dem Tod des Autors veröffentlicht.
4. Kőnig, D. (1916). "Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre." Mathematische Annalen 77(4), 453 bis 465. Ein Graph ist genau dann bipartit, wenn er keinen ungeraden Kreis hat.
5. Dirac, G. A. (1952). "Some Theorems on Abstract Graphs." Proceedings of the London Mathematical Society s3-2(1), 69 bis 81.
6. Bellman, R. (1958). "On a Routing Problem." Quarterly of Applied Mathematics 16(1), 87 bis 90.
7. Kahn, A. B. (1962). "Topological Sorting of Large Networks." Communications of the ACM 5(11), 558 bis 562.
8. Knuth, D. E. (1969). The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Reading, MA: Addison-Wesley. Abschnitt 3.1, Aufgabe 6, mit dem Floyd zugeschriebenen Verfahren zur Kreisfindung.
9. Coffman, E. G., Elphick, M. J. und Shoshani, A. (1971). "System Deadlocks." Computing Surveys 3(2), 67 bis 78.
10. Tarjan, R. E. (1972). "Depth-First Search and Linear Graph Algorithms." SIAM Journal on Computing 1(2), 146 bis 160.
11. Karp, R. M. (1972). "Reducibility Among Combinatorial Problems." In Complexity of Computer Computations, 85 bis 103. New York: Plenum. Gerichteter und ungerichteter Hamiltonkreis unter den 21 NP-vollständigen Problemen.
12. Pollard, J. M. (1975). "A Monte Carlo Method for Factorization." BIT 15(3), 331 bis 334.
13. Johnson, D. B. (1975). "Finding All the Elementary Circuits of a Directed Graph." SIAM Journal on Computing 4(1), 77 bis 84.
14. McCabe, T. J. (1976). "A Complexity Measure." IEEE Transactions on Software Engineering SE-2(4), 308 bis 320.
15. Itai, A. und Rodeh, M. (1978). "Finding a Minimum Circuit in a Graph." SIAM Journal on Computing 7(4), 413 bis 423.
16. Karp, R. M. (1978). "A Characterization of the Minimum Cycle Mean in a Digraph." Discrete Mathematics 23(3), 309 bis 311.
17. Brent, R. P. (1980). "An Improved Monte Carlo Factorization Algorithm." BIT 20(2), 176 bis 184. Ein schnelleres Verfahren zur Kreisfindung.
18. Diestel, R. (2017). Graph Theory, 5. Auflage. Graduate Texts in Mathematics 173. Berlin: Springer.