Chordale Graphen erklärt

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

Was ist ein chordaler Graph?

Ein chordaler Graph, auch triangulierter Graph genannt, ist ein Graph, in dem jeder Kreis mit vier oder mehr Knoten eine Sehne hat. Eine Sehne ist eine Kante, die zwei entlang des Kreises nicht benachbarte Knoten verbindet. Anders gesagt: ein chordaler Graph enthält keinen induzierten Kreis der Länge vier oder mehr; jeder lange Kreis wird durch kürzere Kanten in Dreiecke zerlegt.

Die Definition klingt eng, aber viele Graphen, die Sie bereits kennen, sind chordal: Bäume, vollständige Graphen und Intervallgraphen sind alle chordal. Die Abbildung unten zeigt den kleinsten interessanten Fall, einen Kreis mit vier Knoten, in seiner nicht-chordalen und seiner chordalen Form.

Sehnen und induzierte Kreise

Das entscheidende Wort ist induziert. Ein Kreis ist induziert, wenn die einzigen Kanten zwischen seinen Knoten die Kreiskanten selbst sind. Sobald eine Sehne auftaucht, ist der lange Kreis nicht mehr induziert: er wurde trianguliert.

Die beiden Definitionen sind also dieselbe Aussage aus zwei Blickwinkeln:

• Jeder Kreis der Länge ≥ 4 hat eine Sehne, oder äquivalent
• Der Graph hat keinen induzierten Kreis der Länge ≥ 4 (kein induziertes C₄, C₅ und so weiter).

Dreiecke, als Kreise der Länge 3, sind stets erlaubt und brauchen nie eine Sehne. Deshalb wirken chordale Graphen, als wären sie "aus Dreiecken gebaut".

Simpliziale Knoten und Eliminationsordnungen

Die eigentliche Stärke chordaler Graphen kommt von einem Struktursatz. Zunächst zwei Definitionen.

• Ein Knoten ist simplizial, wenn seine Nachbarn eine Clique bilden, also alle paarweise benachbart sind.
• Eine perfekte Eliminationsordnung (PEO) ist eine Ordnung v₁, v₂, …, vₙ der Knoten, sodass jedes vₚ in dem Graphen simplizial ist, der nach dem Entfernen von v₁ bis vₚ₋₁ übrig bleibt.

Der Satz von Fulkerson-Gross fügt alles zusammen:

Ein Graph ist genau dann chordal, wenn er eine perfekte Eliminationsordnung besitzt. Außerdem hat jeder chordale Graph mindestens einen simplizialen Knoten, sodass Sie stets damit beginnen können, einen abzuschälen.

Das ist der Motor hinter jedem effizienten Algorithmus auf chordalen Graphen. Sobald Sie eine PEO haben, können Sie die Knoten in dieser Reihenfolge verarbeiten und Probleme gierig lösen, denn in jedem Schritt bilden die verbleibenden Nachbarn des Knotens eine Clique ohne Überraschungen.

Einen chordalen Graphen erkennen

Wie erkennt man bei einem gegebenen Graphen, ob er chordal ist? Man könnte nach induzierten Kreisen suchen, aber das ist langsam. Der elegante Weg nutzt die PEO-Charakterisierung und läuft in linearer Zeit, O(V + E).

1. Führen Sie eine lexikografische Breitensuche (Lex-BFS) oder eine Maximum-Cardinality-Suche aus. Beide erzeugen eine Knotenordnung, indem sie stets als Nächstes den Knoten mit den meisten bereits besuchten Nachbarn besuchen.
2. Kehren Sie diese Ordnung um. Ist der Graph chordal, ist die Umkehrung garantiert eine perfekte Eliminationsordnung.
3. Prüfen Sie, ob der Kandidat wirklich eine PEO ist. Wenn ja, ist der Graph chordal; scheitert die Prüfung, ist er es nicht.

Die Suche beruht auf der Breitensuche, angepasst so, dass Gleichstände durch lexikografische Labels aufgelöst werden. Der Prüfschritt ist der Teil, den man im Code sehen sollte.

Eine Ordnung in Python prüfen

Hier ist die Kernprüfung: Entscheiden Sie bei einem Graphen als Adjazenzmenge und einer Kandidatenordnung, ob sie eine perfekte Eliminationsordnung ist. Für jeden Knoten müssen alle seine späteren Nachbarn zum frühesten von ihnen benachbart sein.

def is_perfect_elimination_order(graph, order):
    pos = {v: i for i, v in enumerate(order)}

    for v in order:
        # Nachbarn von v, die in der Ordnung später kommen.
        later = [u for u in graph[v] if pos[u] > pos[v]]
        if len(later) <= 1:
            continue

        # v ist hier genau dann simplizial, wenn diese späteren Nachbarn eine Clique bilden.
        # Es genügt zu prüfen, dass sie alle zum frühesten, w, benachbart sind.
        w = min(later, key=lambda u: pos[u])
        for u in later:
            if u != w and u not in graph[w]:
                return False   # w und u folgen v, sind aber nicht benachbart

    return True

Gibt dies für die umgekehrte Lex-BFS-Ordnung True zurück, ist der Graph chordal. Dieselbe PEO wird dann wiederverwendet, um die schweren Probleme unten zu lösen.

Warum chordale Graphen wichtig sind

Chordale Graphen sind perfekte Graphen, eine Klasse, in der die chromatische Zahl stets der Größe der größten Clique entspricht. Diese Struktur macht mehrere berüchtigt schwere Probleme leicht. Bei gegebener perfekter Eliminationsordnung läuft jedes davon in linearer Zeit.

Es gibt noch ein Juwel. Ein Graph ist genau dann chordal, wenn er einen Cliquenbaum hat, eine Baumzerlegung, deren Beutel die maximalen Cliquen sind. Das verbindet chordale Graphen mit der Baumweite: die Baumweite eines Graphen ist die kleinstmögliche maximale Cliquengröße minus eins über alle seine chordalen Vervollständigungen. Wo diese Klasse in die weitere Landschaft passt, sehen Sie in Anwendungen der Graphentheorie und im Lernpfad.

Anwendungen in der Praxis

• Löser für dünn besetzte Matrizen: die gaußsche Elimination füllt beim Ablauf Nullen auf, und dieses Fill-in zu minimieren ist genau das Problem, Sehnen hinzuzufügen, um einen Graphen chordal zu machen, eine chordale Vervollständigung.
• Compiler: die Registerzuteilung auf modernem SSA-Code wird zur Färbung chordaler Graphen, weshalb sie optimal und schnell gelöst werden kann.
• Probabilistische Modelle: der Junction-Tree-Algorithmus für bayessche Netze trianguliert den Graphen, macht ihn also chordal, und arbeitet dann auf seinem Cliquenbaum.
• Bioinformatik und Ablaufplanung: Intervallgraphen, eine chordale Unterklasse, modellieren überlappende Intervalle wie Gensegmente oder Zeitfenster.