Kantenfolgen, Kantenzüge, Pfade, geschlossene Kantenzüge und Kreise

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Sechs Wörter für die Bewegung durch einen Graphen

Die Graphentheorie hat eine kleine Familie von Wörtern für das Reisen entlang der Kanten eines Graphen: Kantenfolge, Kantenzug und Pfad für Routen, die irgendwo enden dürfen, und geschlossene Kantenfolge, geschlossener Kantenzug und Kreis für Routen, die dorthin zurückkehren, wo sie begonnen haben. Sie unterscheiden sich nur in drei Dingen: ob ein Knoten zweimal besucht werden darf, ob eine Kante zweimal benutzt werden darf und ob die Route an ihrem Startknoten endet.

• Eine Kantenfolge ist eine Folge von Knoten v0, v1, ..., vk derart, dass je zwei aufeinanderfolgende Knoten durch eine Kante verbunden sind. Knoten und Kanten dürfen sich wiederholen. Die Länge der Kantenfolge ist k, die Anzahl der ausgeführten Schritte, wobei wiederholte Kanten bei jeder Benutzung gezählt werden.
• Ein Kantenzug ist eine Kantenfolge, die nie dieselbe Kante zweimal benutzt. Er darf einen Knoten mehr als einmal durchlaufen.
• Ein Pfad ist eine Kantenfolge, die nie denselben Knoten zweimal besucht. Eine zweimal benutzte Kante würde ihre beiden Endknoten erneut besuchen, also wiederholt ein Pfad auch nie eine Kante.
• Eine geschlossene Kantenfolge ist eine Kantenfolge, deren letzter Knoten ihr erster ist.
• Ein geschlossener Kantenzug ist ein Kantenzug, der geschlossen ist: Er endet dort, wo er begann, und benutzt keine Kante zweimal.
• Ein Kreis ist eine geschlossene Kantenfolge der Länge mindestens 3, in der sich kein Knoten wiederholt, abgesehen davon, dass der letzte Knoten der erste ist.

Das sind die Definitionen der meisten modernen Lehrbücher der Graphentheorie, aber nicht aller, und Abschnitt 4 zeigt, wo die wichtigsten Konventionen voneinander abweichen. Das durchgehende Beispiel ist ein Streifen aus vier Dreiecken mit 6 Knoten und 9 Kanten:

edges = {AB, AC, BC, BD, CD, CE, DE, DF, EF}      6 Knoten, 9 Kanten

obere Reihe:    B     D     F
untere Reihe: A     C     E

deg:   A 2   B 3   C 4   D 4   E 3   F 2

Jede Route im Bild trägt den spezifischsten der sechs Namen, der auf sie zutrifft:

• A, B, C, A, B, D ist eine Kantenfolge der Länge 5. Sie benutzt die Kante A-B zweimal, ist also kein Kantenzug.
• A, C, B, D, C, E ist ein Kantenzug der Länge 5. Er besucht C zweimal, ist also kein Pfad, aber jede seiner fünf Kanten ist verschieden.
• A, C, D, F ist ein Pfad der Länge 3. Seine vier Knoten sind alle verschieden.
• A, B, C, D, B, A ist eine geschlossene Kantenfolge der Länge 5. Sie endet wieder in A, benutzt aber A-B zweimal.
• A, B, C, D, E, C, A ist ein geschlossener Kantenzug der Länge 6. Er endet wieder in A mit sechs verschiedenen Kanten, durchläuft aber C zweimal.
• A, B, D, F, E, C, A ist ein Kreis der Länge 6. Er läuft außen um den Streifen herum und wiederholt nichts.

Auch ein einzelner Knoten für sich, etwa A, zählt: Er ist eine Kantenfolge der Länge 0 und ein Pfad der Länge 0 und heißt triviale Kantenfolge. Er ist vor allem für Randfälle in Beweisen und Code wichtig, wo „der Pfad von einem Knoten zu sich selbst“ existieren und die Länge 0 haben sollte.

2. Wie die sechs zusammenpassen

Die Definitionen sind ineinander verschachtelt. Jeder Pfad ist ein Kantenzug, weil eine Route, die nie einen Knoten erneut besucht, keine Kante wiederverwenden kann, und jeder Kantenzug ist eine Kantenfolge. Auf der geschlossenen Seite ist jeder Kreis ein geschlossener Kantenzug und jeder geschlossene Kantenzug eine geschlossene Kantenfolge. Keine dieser Inklusionen gilt umgekehrt, wie die Beispiele in Abschnitt 1 zeigen. Drei Fragen genügen immer, um den richtigen Namen zu finden, und die Reihenfolge, in der man sie stellt, spielt keine Rolle.

Die Anzahlen im Beispiel zeigen, wie schnell die Familien auseinanderwachsen. Von A nach F gibt es genau 13 Pfade: 3 der Länge 3, 6 der Länge 4 und 4 der Länge 5. Es gibt 23 Kantenzüge: die 13 Pfade und dazu 10 Kantenzüge, die einen Knoten zweimal durchlaufen, etwa A, C, B, D, C, E, F. Es gibt unendlich viele Kantenfolgen, weil eine Kantenfolge auf jeder Kante beliebig oft hin und her laufen darf. Erst wenn die Länge festgelegt ist, wird die Anzahl der Kantenfolgen endlich, und Abschnitt 6 zählt sie genau.

Zwei Details bringen Anfänger ins Stolpern:

• Die Länge zählt Kanten, nicht Knoten. Der Pfad A, C, D, F hat vier Knoten und die Länge 3. Ein Kreis durch k Knoten hat die Länge k, weil sein letzter Schritt zum Start zurückführt.
• Ein Kreis hat viele Schreibweisen. Der Kreis A, B, D, F, E, C, A kann mit jedem seiner 6 Knoten beginnend und in beiden Richtungen geschrieben werden, was 12 Folgen für einen einzigen Kreis ergibt. Ebenso kann ein Pfad von beiden Enden aus gelesen werden. Code, der Kreise durch Auflisten von Folgen zählt, muss durch 2k teilen, sonst zählt er jeden Kreis der Länge k so oft.

Warum braucht ein Kreis mindestens die Länge 3? In einem einfachen Graphen laufen die kürzesten geschlossenen Kantenfolgen, etwa A, B, A, eine Kante entlang und auf derselben Kante sofort zurück. Das wiederholt eine Kante, also ist das weder ein geschlossener Kantenzug noch ein Kreis. In einem Multigraphen ändert sich die Lage: Zwei parallele Kanten zwischen denselben beiden Knoten bilden einen Kreis der Länge 2, und eine Schlinge bildet einen Kreis der Länge 1. Deshalb listet die formale Definition einer Kantenfolge neben den Knoten auch die Kanten auf, v0, e1, v1, e2, ..., vk: Wenn zwei parallele Kanten dieselben Knoten verbinden, sagt die Liste der Knoten allein nicht, welche Kante benutzt wurde. In einem einfachen Graphen bestimmen die Knoten die Kanten, und es genügt, die Knoten aufzulisten.

3. Eine Route im Code prüfen

Die Definitionen lassen sich direkt in eine kurze Funktion übersetzen. Sie nimmt einen einfachen Graphen und eine Folge von Knoten, prüft, dass jeder Schritt einer Kante folgt, und stellt dann die drei Fragen aus Abschnitt 2.

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def classify(adj, seq):
    """Benennt die spezifischste Art von Kantenfolge, die die Knotenfolge seq ist."""
    steps = list(zip(seq, seq[1:]))
    if any(v not in adj[u] for u, v in steps):
        return 'not a walk'
    closed = len(seq) > 1 and seq[0] == seq[-1]
    edges = [frozenset(step) for step in steps]
    no_repeated_edge = len(set(edges)) == len(edges)
    inner = seq[:-1] if closed else seq          # eine geschlossene Kantenfolge endet, wo sie begann
    no_repeated_vertex = len(set(inner)) == len(inner)
    if not closed:
        return 'path' if no_repeated_vertex else 'trail' if no_repeated_edge else 'walk'
    if no_repeated_vertex and len(edges) >= 3:
        return 'cycle'
    return 'circuit' if no_repeated_edge else 'closed walk'

strip = graph(['AB', 'AC', 'BC', 'BD', 'CD', 'CE', 'DE', 'DF', 'EF'])
for seq in ['ABCABD', 'ACBDCE', 'ACDF', 'ABCDBA', 'ABCDECA', 'ABDFECA', 'ABA', 'ABE']:
    print(seq, classify(strip, seq))
# ABCABD walk
# ACBDCE trail
# ACDF path
# ABCDBA closed walk
# ABCDECA circuit
# ABDFECA cycle
# ABA closed walk
# ABE not a walk

Die Funktion verwirft zuerst A, B, E, weil zwischen B und E keine Kante verläuft. Bei einer geschlossenen Route vergleicht sie die Knoten ohne den letzten, da eine geschlossene Kantenfolge ihren ersten Knoten am Ende immer wiederholt. Der Test len(edges) >= 3 sorgt dafür, dass A, B, A nicht als Kreis gemeldet wird: Die Folge hat zwei verschiedene Knoten, aber ihre zwei Schritte benutzen dieselbe Kante. Die gesamte Prüfung braucht Zeit proportional zur Länge der Route.

4. Warum Lehrbücher sich widersprechen

Wenn Sie diesen Wörtern schon begegnet sind, dann vielleicht mit anderen Bedeutungen. Die Graphentheorie entstand gleichzeitig in mehreren Ländern und Fachgebieten, und das Vokabular wurde nie vollständig vereinheitlicht. Die Tabelle vergleicht die englischen Wörter, die einige weit verbreitete Lehrbücher für dieselben vier Begriffe verwenden.

Seit Hararys Buch von 1969 sind sich die meisten Texte zur Graphentheorie im Kern einig: Ein walk (Kantenfolge) darf alles wiederholen, und ein path (Pfad) wiederholt nichts. Ores Theory of Graphs von 1962 zeigt den älteren Sprachgebrauch, in dem ein path eine Route ohne wiederholte Kanten war, also das, was heute trail (Kantenzug) heißt. Rosens Discrete Mathematics and Its Applications, ein Standardlehrbuch für Einführungskurse in diskreter Mathematik, bewahrt eine Variante davon: path bedeutet jede beliebige Kantenfolge, und ein simple path ist eine Route, die keine Kante wiederholt. Rosen weist selbst auf den Konflikt hin und nennt walk, closed walk und trail als die Wörter der anderen Bücher, aber wer „path“ bei Rosen lernt und dann einen Text zur Graphentheorie aufschlägt, findet dasselbe Wort mit einer strengeren Bedeutung.

Die Wörter circuit und cycle sind am wenigsten stabil. West sowie Chartrand und Zhang verwenden circuit für einen geschlossenen Kantenzug, wie dieser Artikel. Ore verwendete circuit für das, was heute ein Kreis (cycle) ist, und Ingenieure sagen oft „circuit“ zu jeder geschlossenen Schleife. Gerichtete Graphen fügen eine weitere Ebene hinzu: In Berges klassischen Büchern, die ursprünglich auf Französisch geschrieben wurden, ist eine Route in einem ungerichteten Graphen eine chaîne (Kette) und eine geschlossene ein cycle, während eine Route entlang der Pfeile ein chemin (Pfad) und eine geschlossene ein circuit.

Die sicherste Gewohnheit ist, die verwendete Definition beim ersten Auftreten eines Wortes anzugeben oder das mehrdeutige Wort durch die Eigenschaft zu ersetzen: „eine Route, die keinen Knoten wiederholt“ kann man nicht missverstehen. Suchen Sie beim Lesen die Definition im ersten Kapitel und rechnen Sie damit, dass sie von der im zuletzt gelesenen Buch abweicht.

Das bekannteste Opfer der Namensgebung ist der Eulerweg (Eulerian path). Er benutzt jede Kante eines Graphen genau einmal und durchläuft Knoten meist mehrfach, ist also im Vokabular dieses Artikels ein Kantenzug, kein Pfad. Der Name hat überlebt, weil das Problem älter ist als das Vokabular, und „Eulerzug“ (Eulerian trail) ist heute der sorgfältigere Name für dieselbe Sache. Der Hamiltonweg (Hamiltonian path), der jeden Knoten genau einmal besucht, ist wirklich ein Pfad. Abschnitt 8 kommt auf beide zurück.

5. Jede Kantenfolge enthält einen Pfad

Die nützlichste Tatsache über Kantenfolgen ist, dass Wiederholung nie nötig ist, um irgendwohin zu gelangen. Gibt es eine Kantenfolge von u nach v, so gibt es einen Pfad von u nach v, und der Pfad ist nicht länger als die Kantenfolge. Der Beweis ist eine Abkürzung. Besucht die Kantenfolge einen Knoten x zweimal, löschen Sie alles zwischen den beiden Besuchen: Die Kantenfolge läuft weiterhin von u nach v, und sie ist kürzer. Wiederholen Sie das, bis sich kein Knoten mehr wiederholt. Was übrig bleibt, ist ein Pfad.

Dieses kleine Lemma hat große Folgen:

• Zusammenhang. „Zwischen je zwei Knoten gibt es eine Kantenfolge“ und „zwischen je zwei Knoten gibt es einen Pfad“ bedeuten dasselbe, also kann man einen Graphen mit beiden Formulierungen zusammenhängend nennen. Der Leitfaden zu Zusammenhangskomponenten baut darauf auf.
• Kürzeste Routen sind Pfade. Eine kürzeste Kantenfolge zwischen zwei Knoten wiederholt nie einen Knoten, da das Herausschneiden der Wiederholung sie kürzer machen würde. Deshalb können die Breitensuche und Dijkstras Algorithmus über Kantenfolgen suchen, ohne je auf wiederholte Knoten zu prüfen, und liefern trotzdem Pfade. Der Leitfaden zu Kürzeste-Wege-Algorithmen behandelt beide.
• Negative Gewichte setzen das außer Kraft. Bei negativen Kantengewichten kann das Herausschneiden einer Schleife eine Route länger machen, weil die Schleife ein negatives Gesamtgewicht gehabt haben kann. Ist ein negativer Kreis erreichbar, lassen sich Kantenfolgen beliebig billig machen, indem man ihn erneut umrundet, und kürzeste Kantenfolgen existieren nicht mehr. Kürzeste Pfade existieren weiterhin, aber einen davon zu finden, wird im Allgemeinen NP-schwer, denn damit fände man auch die längsten Pfade aus Abschnitt 7. Der Leitfaden zum Bellman-Ford-Algorithmus zeigt, wie man solche Kreise erkennt.

Geschlossene Kantenfolgen erfordern mehr Sorgfalt. Eine geschlossene Kantenfolge enthält nicht immer einen Kreis: A, B, A ist geschlossen, enthält aber keinen. Eine geschlossene Kantenfolge ungerader Länge enthält immer einen, und der enthaltene Kreis ist ebenfalls ungerade. Teilen Sie die geschlossene Kantenfolge an einem wiederholten Knoten in zwei kürzere geschlossene Kantenfolgen. Ihre Längen addieren sich zur ursprünglichen ungeraden Länge, also ist eine von ihnen ungerade. Behalten Sie die ungerade und wiederholen Sie den Schritt. Der Vorgang endet bei einer ungeraden geschlossenen Kantenfolge ohne wiederholten Knoten, und da ein einfacher Graph keine geschlossene Kantenfolge der Länge 1 hat, ist diese Kantenfolge ein Kreis der Länge mindestens 3.

Dieses Argument ist der entscheidende Schritt im Satz von Kőnig: Ein Graph ist bipartit genau dann, wenn er keinen Kreis ungerader Länge hat. Ein geschlossener Kantenzug zerfällt auf dieselbe Weise in Kreise, die keine Kante gemeinsam haben. Das folgende Programm führt alle drei Operationen aus: Es schneidet Schleifen aus einer Kantenfolge heraus, findet einen ungeraden Kreis in einer ungeraden geschlossenen Kantenfolge und zerlegt einen geschlossenen Kantenzug in Kreise.

def walk_to_path(walk):
    """Schneidet jede Schleife heraus. Das Ergebnis ist ein Pfad mit denselben beiden Enden."""
    path, where = [], {}
    for v in walk:
        if v in where:                       # wieder bei v: alles seit dem letzten Besuch verwerfen
            for u in path[where[v] + 1:]:
                del where[u]
            del path[where[v] + 1:]
        else:
            where[v] = len(path)
            path.append(v)
    return ''.join(path)

def split_closed_walk(walk):
    """Teilt eine geschlossene Kantenfolge an ihrem ersten wiederholten Knoten in zwei kürzere geschlossene Kantenfolgen."""
    seen = {}
    for i, v in enumerate(walk[:-1]):
        if v in seen:
            j = seen[v]
            return walk[j:i + 1], walk[:j] + walk[i:]
        seen[v] = i
    return None                              # nichts wiederholt sich: ein Kreis oder ein Schritt hin und zurück

def odd_cycle(walk):
    """Eine geschlossene Kantenfolge ungerader Länge enthält immer einen Kreis ungerader Länge."""
    while True:
        parts = split_closed_walk(walk)
        if parts is None:
            return walk
        walk = next(p for p in parts if (len(p) - 1) % 2 == 1)

def circuit_to_cycles(walk):
    """Zerlegt einen geschlossenen Kantenzug in Kreise ohne gemeinsame Kante."""
    parts = split_closed_walk(walk)
    if parts is None:
        return [walk]
    return circuit_to_cycles(parts[0]) + circuit_to_cycles(parts[1])

print(walk_to_path('ACBDCEF'))               # Kantenfolge der Länge 6
# ACEF
print(odd_cycle('ABCDCA'))                   # geschlossene Kantenfolge der Länge 5, Kante C-D zweimal benutzt
# ABCA
print(circuit_to_cycles('ABCDECA'))          # geschlossener Kantenzug der Länge 6, zweimal durch C
# ['CDEC', 'ABCA']

Der Kantenzug A, C, B, D, C, E, F besucht C zweimal, also fällt die Schleife C, B, D, C weg, und übrig bleibt A, C, E, F. Die geschlossene Kantenfolge A, B, C, D, C, A zerfällt bei C in C, D, C, der Länge 2, und A, B, C, A, der Länge 3, und das ist der ungerade Kreis. Der geschlossene Kantenzug A, B, C, D, E, C, A zerfällt bei C in die beiden Dreiecke C, D, E, C und A, B, C, A.

Die Zerlegung des geschlossenen Kantenzugs ist ein Spezialfall eines Satzes, den Oswald Veblen 1912 veröffentlichte: Die Kanten eines Graphen lassen sich genau dann in Kreise ohne gemeinsame Kante aufteilen, wenn jeder Knoten geraden Grad hat. Ein Kreis benutzt an jedem Knoten, den er durchläuft, zwei Kanten, also müssen die Grade gerade sein; die Umkehrung folgt, indem man wiederholt einen Kreis entfernt, wodurch jeder Grad gerade bleibt.

6. Kantenfolgen zählen mit Matrixpotenzen

Kantenfolgen sind schwer aufzulisten, aber leicht zu zählen. Schreiben Sie den Graphen als seine Adjazenzmatrix A, mit einer 1 in Zeile u, Spalte v immer dann, wenn u und v benachbart sind, und sonst einer 0. Der Leitfaden zur Darstellung von Graphen erklärt die Matrix selbst. Dann gilt eine klassische Tatsache: Der Eintrag in Zeile u, Spalte v der Potenz Ak ist die Anzahl der Kantenfolgen der Länge k von u nach v.

Der Grund ist die Regel für die Matrixmultiplikation. Eine Kantenfolge der Länge k von u nach v ist eine Kantenfolge der Länge k - 1 von u zu einem Knoten w, gefolgt von einem Schritt von w nach v. Die Anzahl solcher Kantenfolgen ist also die Summe über alle w von (Kantenfolgen der Länge k - 1 von u nach w) mal A[w][v], und das ist genau der Eintrag von Ak-1 mal A. Induktion über k erledigt den Rest.

Am Streifen zeigen sich mehrere Folgerungen auf einmal:

• Die Diagonale von A2 ist die Liste der Grade. Eine geschlossene Kantenfolge der Länge 2 läuft eine Kante entlang und zurück, und es gibt eine für jede Kante am Knoten: 2, 3, 4, 4, 3, 2 für A bis F.
• A2[A][D] = 2, für die Kantenfolgen A, B, D und A, C, D.
• Die erste Potenz mit einem Eintrag ungleich null liefert den Abstand. A1 und A2 sind 0 in Zeile A, Spalte F, und A3 ist dort 3. Also ist der Abstand von A nach F gleich 3, und die drei Kantenfolgen dieser Länge sind die drei kürzesten Pfade A, B, D, F, A, C, D, F und A, C, E, F. Nach Abschnitt 5 sind kürzeste Kantenfolgen immer Pfade.
• Dreiecke ergeben sich aus der Diagonale von A3. Eine geschlossene Kantenfolge der Länge 3 in einem einfachen Graphen läuft um ein Dreieck. Jedes Dreieck wird einmal von jedem seiner 3 Knoten aus in jeder der 2 Richtungen gezählt, also ist die Anzahl der Dreiecke die Summe der Diagonale geteilt durch 6: hier 24 / 6 = 4, die Dreiecke ABC, BCD, CDE und DEF.

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def matmul(X, Y):
    return [[sum(x * y for x, y in zip(row, col)) for col in zip(*Y)] for row in X]

def walk_counts(adj, order, k):
    """Eintrag [i][j] der k-ten Potenz der Adjazenzmatrix zählt die Kantenfolgen der Länge k."""
    A = [[int(v in adj[u]) for v in order] for u in order]
    M = A
    for _ in range(k - 1):
        M = matmul(M, A)
    return M

strip = graph(['AB', 'AC', 'BC', 'BD', 'CD', 'CE', 'DE', 'DF', 'EF'])
order = 'ABCDEF'
for k in range(1, 7):
    M = walk_counts(strip, order, k)
    print(f'length {k}:  A to F {M[0][5]:3}   A back to A {M[0][0]:3}')
# length 1:  A to F   0   A back to A   0
# length 2:  A to F   0   A back to A   2
# length 3:  A to F   3   A back to A   2
# length 4:  A to F   6   A back to A  11
# length 5:  A to F  29   A back to A  24
# length 6:  A to F  78   A back to A  92
A3 = walk_counts(strip, order, 3)
print('triangles:', sum(A3[i][i] for i in range(len(order))) // 6)
# triangles: 4

Die Anzahl der Kantenfolgen von A nach F wächst schnell mit der Länge, in drei Schritten von 3 auf 78, und doch bleibt die Berechnung billig. Jede Multiplikation zweier n mal n großer Matrizen braucht etwa n3 Operationen, und wiederholtes Quadrieren erreicht Ak in etwa log2 k Multiplikationen, sodass sich selbst Kantenfolgen der Länge eine Million mit einigen Dutzend Matrixprodukten exakt zählen lassen. Die Summe der Diagonale von Ak ist zugleich die Summe der k-ten Potenzen der Eigenwerte der Matrix, und hier treffen Kantenfolgen auf die spektrale Graphentheorie: Der größte Eigenwert bestimmt die Wachstumsrate der Anzahl langer Kantenfolgen.

7. Kantenfolgen sind leicht, Pfade sind schwer

Der Matrixtrick hat für Pfade kein Gegenstück. Die Anzahl der Pfade zwischen zwei Knoten ist im Allgemeinen schwer zu berechnen. Leslie Valiant bewies 1979: Das Zählen der Pfade zwischen zwei gegebenen Knoten ist #P-vollständig, das Zählanalogon zu NP-vollständig. Es ist kein Verfahren bekannt, das wesentlich besser ist, als die Routen eine nach der anderen auszuprobieren, und man erwartet auch keines. Das folgende Programm zählt Pfade durch genau diese Art von Suche und zählt Kantenzüge auf dieselbe Weise, mit Kanten anstelle von Knoten.

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def count_paths(adj, s, t, seen=None):
    """Anzahl der Pfade von s nach t: jeden unbesuchten Nachbarn ausprobieren, dann rückgängig machen."""
    if s == t:
        return 1
    seen = seen or {s}
    total = 0
    for w in adj[s] - seen:
        seen.add(w)
        total += count_paths(adj, w, t, seen)
        seen.remove(w)
    return total

def count_trails(adj, s, t, used=None):
    """Anzahl der Kantenzüge von s nach t. Ein Kantenzug darf t durchlaufen und später dorthin zurückkehren."""
    used = used or set()
    total = 1 if s == t else 0
    for w in adj[s]:
        e = frozenset((s, w))
        if e not in used:
            used.add(e)
            total += count_trails(adj, w, t, used)
            used.remove(e)
    return total

strip = graph(['AB', 'AC', 'BC', 'BD', 'CD', 'CE', 'DE', 'DF', 'EF'])
print(count_paths(strip, 'A', 'F'), count_trails(strip, 'A', 'F'))
# 13 23

def grid(n):
    """Das n-mal-n-Straßengitter: Knoten (Zeile, Spalte), Kanten nach rechts und nach unten."""
    return graph([((r, c), (r, c + 1)) for r in range(n) for c in range(n - 1)] +
                 [((r, c), (r + 1, c)) for r in range(n - 1) for c in range(n)])

for n in range(2, 6):
    print(n, count_paths(grid(n), (0, 0), (n - 1, n - 1)))
# 2 2
# 3 12
# 4 184
# 5 8512

Auf dem Streifen bestätigt die Suche die Anzahlen aus Abschnitt 2: 13 Pfade und 23 Kantenzüge von A nach F. Das Gitter zeigt, wie schnell die Zahlen explodieren. Zwischen gegenüberliegenden Ecken eines Straßengitters mit 2, 3, 4 und 5 Knoten pro Seite gibt es 2, 12, 184 und 8.512 Pfade, und eine weitere Zeile und Spalte ergibt 1.262.816. Physiker und Chemiker nennen Pfade in einem Gitter selbstvermeidende Irrfahrten (self-avoiding walks) und verwenden sie als Modelle für Polymerketten, also Moleküle, die sich nicht selbst durchdringen können.

Dieselbe Kluft trennt die leichten und die schweren Fragen über einzelne Routen:

• Kürzester Pfad: leicht. Die Breitensuche findet einen in linearer Zeit, wenn die Kanten keine Gewichte haben, und Dijkstras Algorithmus, wenn die Gewichte nichtnegativ sind, dank des Abkürzungslemmas aus Abschnitt 5.
• Längster Pfad: schwer. Zu entscheiden, ob ein Graph einen Pfad mindestens einer gegebenen Länge hat, ist NP-vollständig. Ein Pfad durch alle n Knoten hat die Länge n - 1, also enthält die Frage das Problem des Hamiltonwegs als Spezialfall. Im Streifen hat der längste Pfad von A nach F die Länge 5 und durchläuft alle sechs Knoten; der Zickzackpfad A, B, C, D, E, F ist einer davon.
• Längste Kantenfolge: sinnlos. Kantenfolgen dürfen Kanten wiederholen, also hat jeder Graph mit einer Kante Kantenfolgen jeder Länge.

8. Kantenzüge, geschlossene Kantenzüge und Euler

Kantenzüge gehören zu Euler. Seine Lösung des Königsberger Brückenproblems von 1736 fragte nach einer Kantenfolge, die jede Brücke genau einmal überquert: einem Kantenzug durch jede Kante eines Multigraphen. Ein solcher Kantenzug ist ein Eulerzug, und ein geschlossener heißt Eulerkreis. Eulers Bedingung, die Carl Hierholzer in einer 1873 veröffentlichten Arbeit vollständig bewies, betrifft die Grade. Ein zusammenhängender Graph hat genau dann einen Eulerkreis, wenn jeder Knoten geraden Grad hat, und genau dann einen nicht geschlossenen Eulerzug, wenn genau zwei Knoten ungeraden Grad haben; in diesem Fall muss der Kantenzug an einem von ihnen beginnen und am anderen enden.

Im Streifen haben B und E den Grad 3, und jeder andere Knoten hat geraden Grad, also verläuft ein Eulerzug von B nach E:

B, A, C, B, D, C, E, D, F, E        9 Kanten, jede einmal benutzt

Er durchläuft B, C, D und E jeweils zweimal, weshalb „Eulerweg“ (Eulerian path) streng genommen eine Fehlbezeichnung ist. Der Leitfaden zu Eulerwegen und Eulerkreisen behandelt Hierholzers Algorithmus ausführlich. Hat ein Graph mehr als zwei ungerade Knoten, müssen einige Kanten zweimal abgelaufen werden, und die günstigste geschlossene Kantenfolge durch jede Kante zu finden, ist das Briefträgerproblem (chinesisches Postbotenproblem).

Veblens Satz aus Abschnitt 5 ist die andere Seite derselben Medaille. Ein Eulerkreis ist ein geschlossener Kantenzug durch jede Kante, und wenn man ihn an wiederholten Knoten aufteilt, zerfallen die Kanten in Kreise ohne gemeinsame Kante. Umgekehrt hat ein zusammenhängender Graph, dessen Kanten sich in solche Kreise zerlegen lassen, lauter gerade Grade, und die Kreise lassen sich an gemeinsamen Knoten zu einem einzigen Eulerkreis zusammenfügen.

9. Kreise, Taillenweite und Umfang

Der Streifen hat genau 10 Kreise: die vier Dreiecke, drei Kreise der Länge 4, zwei der Länge 5 und einen der Länge 6.

Länge 3:   ABC, BCD, CDE, DEF
Länge 4:   ABDC, BDEC, CDFE
Länge 5:   ABDEC, BDFEC
Länge 6:   ABDFEC

Zwei Zahlen fassen die Kreise eines Graphen zusammen. Die Taillenweite ist die Länge eines kürzesten Kreises, hier 3, und der Umfang ist die Länge eines längsten Kreises, hier 6. Ein Kreis durch jeden Knoten, wie A, B, D, F, E, C, A, ist ein Hamiltonkreis, also ist der Streifen hamiltonsch. Ein Graph ganz ohne Kreis ist ein Wald, und ein zusammenhängender ist ein Baum, in dem es zwischen je zwei Knoten genau einen Pfad gibt; der Leitfaden zu Bäumen entwickelt diese Idee weiter. Der Leitfaden zu Kreisen in Graphen erklärt, wie man einen Kreis mit Tiefensuche erkennt und wie viele unabhängige Kreise ein Graph hat.

10. Gerichtete Kantenfolgen und Pfade

In einem gerichteten Graphen muss jeder Schritt einem Pfeil von seinem Anfang zu seiner Spitze folgen. Mit dieser einen Änderung übertragen sich alle sechs Definitionen: Es gibt gerichtete Kantenfolgen, gerichtete Kantenzüge, gerichtete Pfade, geschlossene gerichtete Kantenfolgen, gerichtete geschlossene Kantenzüge und gerichtete Kreise. Einiges verhält sich anders:

• Es gibt Kreise der Länge 2. Zwei Pfeile u → v und v → u sind verschiedene Kanten, also ist u, v, u auch in einem Graphen ohne parallele Kanten ein gerichteter Kreis.
• Erreichbarkeit gilt nur in eine Richtung. Ein gerichteter Pfad von u nach v sagt nichts über einen Pfad zurück. Knoten, die einander in beiden Richtungen erreichen können, bilden eine starke Zusammenhangskomponente, und der Leitfaden zu stark zusammenhängenden Komponenten zeigt, wie man sie findet.
• Kein gerichteter Kreis bedeutet, dass eine Ordnung existiert. Ein gerichteter Graph ohne gerichtete Kreise, ein DAG, lässt sich immer so auflisten, dass jeder Pfeil nach vorn zeigt. Diese Auflistung ist eine topologische Sortierung, und in einem DAG lässt sich sogar der längste Pfad in linearer Zeit finden.
• Ignoriert man die Pfeile, so erhält man eine Semi-Kantenfolge oder einen Semi-Pfad, also Routen, die auch entgegen einem Pfeil laufen dürfen. Ein gerichteter Graph ist schwach zusammenhängend, wenn seine Knoten durch Semi-Pfade verbunden sind.

Der Matrixtrick aus Abschnitt 6 funktioniert für gerichtete Graphen unverändert: Der Eintrag in Zeile u, Spalte v von Ak zählt die gerichteten Kantenfolgen der Länge k von u nach v.

11. Wo welche Art von Route eingesetzt wird

Jedes der sechs Wörter benennt das richtige Modell für eine andere Art realer Probleme:

• Pfade sind Routen für alles, was keine Schleifen drehen soll: Wegbeschreibungen für Autofahrer, Datenpakete in einem Netzwerk, eine Kette von Bekanntschaften zwischen zwei Personen. Nach dem Abkürzungslemma ist jedes Problem der kürzesten Route ein Pfadproblem.
• Kantenzüge und geschlossene Kantenzüge beschreiben das einmalige Abdecken jeder Straße, jedes Rohrs oder jeder Leitung: Schneepflüge, Kehrmaschinen und Postrunden. Müssen einige Kanten wiederholt werden, wird daraus das Briefträgerproblem aus Abschnitt 8.
• Kantenfolgen treten überall auf, wo Bewegung zufällig ist. Eine Irrfahrt (Zufallsweg) zieht in jedem Schritt zu einem zufälligen Nachbarn. George Pólya bewies 1921, dass eine Irrfahrt auf dem Gitter der ganzzahligen Punkte in einer oder zwei Dimensionen mit Sicherheit zu ihrem Start zurückkehrt, in drei Dimensionen aber nicht. Googles ursprünglicher PageRank, 1998 von Sergey Brin und Lawrence Page beschrieben, ordnet Webseiten danach, wie oft ein zufälliger Surfer, der Links folgt, sie besucht, und Verfahren zur Grapheinbettung wie DeepWalk lernen aus vielen kurzen Irrfahrten.
• Kreise sind meist das, was man finden oder verbieten will: Ein Deadlock ist ein Kreis von Prozessen, von denen jeder auf den nächsten wartet, ein zirkulärer Import oder eine Tabellenformel, die sich auf sich selbst bezieht, ist ein Kreis von Abhängigkeiten, und die Kirchhoffsche Maschenregel besagt, dass sich die Spannungen entlang jedes Kreises eines elektrischen Netzwerks zu null addieren.
• Geschlossene Kantenfolgen zählen Struktur: Die Diagonale von A3 zählt Dreiecke, womit die Analyse sozialer Netzwerke misst, wie oft sich die Freunde einer Person untereinander kennen.

12. Häufige Fehler

13. Glossar

15. 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. Vorgelegt 1736.
2. Hierholzer, C. (1873). "Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren." Mathematische Annalen 6, 30 bis 32.
3. Veblen, O. (1912). "An Application of Modular Equations in Analysis Situs." Annals of Mathematics, 2. Serie, 14, 86 bis 94.
4. Kőnig, D. (1916). "Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre." Mathematische Annalen 77, 453 bis 465.
5. Pólya, G. (1921). "Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Straßennetz." Mathematische Annalen 84, 149 bis 160.
6. Berge, C. (1958). Théorie des graphes et ses applications. Paris: Dunod.
7. Ore, O. (1962). Theory of Graphs. American Mathematical Society Colloquium Publications 38. Providence, RI: American Mathematical Society.
8. Harary, F. (1969). Graph Theory. Reading, MA: Addison-Wesley.
9. Garey, M. R. und Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman.
10. Valiant, L. G. (1979). "The Complexity of Enumeration and Reliability Problems." SIAM Journal on Computing 8(3), 410 bis 421.
11. Biggs, N. (1993). Algebraic Graph Theory, 2. Auflage. Cambridge: Cambridge University Press.
12. Brin, S. und Page, L. (1998). "The Anatomy of a Large-Scale Hypertextual Web Search Engine." Computer Networks and ISDN Systems 30(1 bis 7), 107 bis 117.
13. West, D. B. (2001). Introduction to Graph Theory, 2. Auflage. Upper Saddle River, NJ: Prentice Hall.
14. Bondy, J. A. und Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. London: Springer.
15. Chartrand, G. und Zhang, P. (2012). A First Course in Graph Theory. Mineola, NY: Dover.
16. Rosen, K. H. (2012). Discrete Mathematics and Its Applications, 7. Auflage. New York: McGraw-Hill.
17. Perozzi, B., Al-Rfou, R. und Skiena, S. (2014). "DeepWalk: Online Learning of Social Representations." Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 701 bis 710.
18. Diestel, R. (2017). Graph Theory, 5. Auflage. Graduate Texts in Mathematics 173. Berlin: Springer.