Die sieben Brücken von Königsberg

4Grade

Der Grad deg(v) eines Knotens v ist die Anzahl der Kantenenden, die ihn berühren. Gleichbedeutend ist es die Anzahl der Brücken, die von diesem Landstück abgehen.

Zur Kontrolle nutzen wir das Handschlag-Lemma. Jede Kante hat genau zwei Enden, und jedes Ende erhöht den Grad eines Knotens um 1. Für jeden Graphen gilt also:

∑_{v ∈ V} deg(v) = 2 |E|,
und hier 3 + 5 + 3 + 3 = 14 = 2 × 7.

Eine Folgerung: Die Summe aller Grade ist gerade, also hat jeder Graph eine gerade Anzahl von Knoten mit ungeradem Grad.

6Warum das in der Informatik wichtig ist

Eulers Satz ersetzt eine Suche durch eine Zählung. Du musst keine Routen ausprobieren, sondern nur Grade zählen:

from collections import Counter

def euler_kind(edges):
    """Classify a connected multigraph given as a list of edges (u, v)."""
    degree = Counter()
    for u, v in edges:
        degree[u] += 1
        degree[v] += 1
    odd = sum(1 for d in degree.values() if d % 2 == 1)
    if odd == 0:
        return "Eulerian circuit"
    if odd == 2:
        return "Eulerian path"
    return "neither"

koenigsberg = [("A", "B"), ("A", "B"), ("B", "D"), ("B", "D"),
               ("A", "C"), ("B", "C"), ("C", "D")]
print(euler_kind(koenigsberg))  # neither: four odd vertices

Das läuft in O(V + E) Zeit: ein Durchlauf über die Kanten, dann einer über die Knoten. Eine vollständige Prüfung kontrolliert außerdem, dass alle Kanten zu einer einzigen Zusammenhangskomponente gehören, mit einer Breiten- oder Tiefensuche, die ebenfalls O(V + E) kostet. Eine naive Suche, die jede Reihenfolge der Kanten ausprobiert, kann bis zu E! Folgen untersuchen. Das sind 7! = 5.040 für Königsberg, aber 20! ≈ 2,4 × 10¹⁸ für einen Graphen mit nur 20 Kanten.

Dieselbe Idee taucht überall in der Informatik auf:

• Der Algorithmus von Hierholzer baut einen Eulerkreis in O(E) Zeit. Folge unbenutzten Kanten, bis du wieder am Start bist. Baue dann von einem beliebigen Knoten dieses Kreises, der noch unbenutzte Kanten hat, einen weiteren Kreis und füge ihn ein.
• Das Problem des chinesischen Briefträgers fragt nach dem kürzesten geschlossenen Kantenzug, der jede Kante mindestens einmal benutzt, etwa bei der Postzustellung, bei Schneepflügen oder Straßenkehrmaschinen. Auf ungerichteten Graphen lässt es sich in Polynomialzeit lösen. Man paart die Knoten mit ungeradem Grad über ein perfektes Matching mit minimalem Gewicht, gewichtet nach der Länge des kürzesten Weges. Dann geht man den kürzesten Weg zwischen jedem gepaarten Knotenpaar ein zweites Mal.
• De-Bruijn-Graphen bei der Genomassemblierung: DNA-Sequenzierer lesen Millionen kurzer Fragmente, die in überlappende Teilstrings der Länge k zerlegt werden. Jeder Teilstring wird zu einer gerichteten Kante von seinen ersten k − 1 Buchstaben zu seinen letzten k − 1 Buchstaben. Das Genom wieder zusammenzusetzen wird dann zur Suche nach einem Eulerweg. In gerichteten Graphen lautet die Bedingung, dass an jedem Knoten der Eingangsgrad gleich dem Ausgangsgrad ist, außer dass der Start eine ausgehende Kante mehr und das Ende eine eingehende Kante mehr hat.
• Der hamiltonsche Kontrast: Ersetze „jede Kante genau einmal“ durch „jeden Knoten genau einmal“, und kein einfacher Gradtest funktioniert mehr. Zu entscheiden, ob ein Graph einen Hamiltonweg hat, ist NP-vollständig. Es ist kein Polynomialzeit-Algorithmus bekannt, und einen zu finden würde P = NP beweisen.