Chordaler Graph Prüfer

Pseudocode

Chordalität direkt zu prüfen, indem man nach einem langen sehnenlosen Zyklus sucht, ist teuer. Der Standardweg ist indirekt: eine Kandidatenordnung für perfekte Elimination bestimmen und sie anschließend verifizieren.

// Schritt 1: Maximum-Cardinality-Search
gewicht[v] = 0 für alle v; ordnung = []
wiederhole V mal:
    wähle das unnummerierte v mit größtem Gewicht
    ordnung.voranstellen(v)
    für jeden unnummerierten Nachbarn n von v: gewicht[n]++

// Schritt 2: prüfen, ob es eine perfekte Eliminationsordnung ist
für jedes v in ordnung an Position i:
    spätere = Nachbarn von v, die nach i erscheinen
    wenn spätere leer ist: weiter
    w = der früheste Knoten in spätere
    wenn ein u in spätere nicht zu w benachbart ist:
        gib NICHT chordal zurück
gib chordal zurück

Eine perfekte Eliminationsordnung ist eine, in der jeder Knoten zusammen mit seinen späteren Nachbarn eine Clique bildet. Ein Graph ist genau dann chordal, wenn eine solche Ordnung existiert. Maximum-Cardinality-Search liefert stets eine, sofern der Graph chordal ist, der Verifikationsschritt ist also das, was aus einer heuristischen Ordnung einen Beweis macht, und er ist zugleich das, was das Scheitern erkennt, wenn keine solche Ordnung existiert.

Durchgerechnetes Beispiel, Schritt für Schritt

Prüfe einen Vierer-Zyklus auf Chordalität, füge dann eine Sehne hinzu und prüfe erneut.

Beispielgraph: Zuerst der 4-Zyklus A-B, B-C, C-D, D-A. Dann derselbe Graph mit der zusätzlichen Sehne A-C.

1. MCS auf dem 4-Zyklus ausführen. Maximum-Cardinality-Search liefert die Ordnung D, C, B, A.
2. D verifizieren. D steht an erster Stelle. Seine in der Ordnung späteren Nachbarn sind C und A. Der früheste davon ist C, die Prüfung fragt also, ob A zu C benachbart ist. Im reinen 4-Zyklus ist es das nicht.
3. Ablehnen. Die Ordnung ist keine perfekte Eliminationsordnung, und da MCS eine gefunden hätte, wäre der Graph chordal, ist der 4-Zyklus nicht chordal. Das stimmt: A-B-C-D-A ist ein Zyklus der Länge 4 ohne jede Sehne.
4. Die Sehne A-C hinzufügen und erneut prüfen. MCS liefert wieder D, C, B, A. Bei der Verifikation von D sind die späteren Nachbarn C und A, und nun ist A zu C benachbart, die Prüfung besteht also. Bei C sind die späteren Nachbarn B und A, und der Test verlangt nur, dass die übrigen zum frühesten benachbart sind, also zu B; da A-B eine Kante ist, besteht auch das. Jeder verbleibende Knoten hat höchstens einen späteren Nachbarn und besteht trivial.

Der reine 4-Zyklus ist nicht chordal; das Hinzufügen der einen Sehne A-C macht ihn chordal. Das ist die Definition greifbar gemacht: ein Graph ist chordal, wenn jeder Zyklus aus vier oder mehr Knoten eine Kante besitzt, die zwei nicht aufeinanderfolgende Knoten dieses Zyklus verbindet. Der 4-Zyklus ist das kleinstmögliche Gegenbeispiel, weshalb er der übliche Testfall ist.

Komplexität und woher sie kommt

Zeit: O(V + E) · Speicher: O(V + E)

Maximum-Cardinality-Search läuft in O(V + E), wenn man Knoten in Eimern nach Gewicht führt, sodass sowohl die Auswahl des Maximums als auch das Erhöhen der Nachbarn amortisiert konstant sind. Der Verifikationsdurchlauf betrachtet jeden Knoten einmal und jeden seiner späteren Nachbarn einmal, was insgesamt O(V + E) ergibt, sofern Adjazenzabfragen über eine Hashmenge konstant sind. Der gesamte Test ist also linear, was ein wirklich überraschendes Ergebnis ist: der naive Ansatz, Zyklen aufzuzählen und jeden auf eine Sehne zu prüfen, ist exponentiell, und selbst eine geschicktere zyklenbasierte Methode wäre weit schlechter. Lexikographische BFS ist eine Alternative zu MCS mit derselben Schranke.

Wann Chordalitätsprüfung passt und wann nicht

Chordalität ist meist ein Türöffner: sobald ein Graph als chordal bekannt ist, werden mehrere NP-schwere Probleme auf ihm linear.

Häufige Fehler

• Den Verifikationsschritt überspringen. MCS liefert für jeden Graphen eine Ordnung, ob chordal oder nicht. Erst der Verifikationsdurchlauf unterscheidet die beiden Fälle. Die MCS-Ausgabe als Beleg für Chordalität zu nehmen akzeptiert jeden Graphen.
• Die Definition als "jeder Zyklus hat eine Sehne" missverstehen. Die Bedingung gilt nur für Zyklen der Länge 4 oder mehr. Dreiecke haben keine nicht aufeinanderfolgenden Knotenpaare und erfüllen sie daher trivial. Jeder nur aus Dreiecken bestehende Graph ist chordal.
• Alle Paare späterer Nachbarn prüfen. Die Verifikation muss jeden späteren Nachbarn nur gegen den frühesten von ihnen vergleichen, nicht gegen jeden anderen. Alle Paare zu prüfen ist korrekt, macht aus einem linearen Algorithmus jedoch einen quadratischen.
• Annehmen, chordal bedeute dicht oder baumartig. Bäume sind chordal, weil sie überhaupt keine Zyklen haben, und vollständige Graphen sind chordal, weil jede mögliche Sehne bereits vorhanden ist. Chordalität ist kein Dichtemaß und verläuft quer dazu.
• Vergessen, jede Zusammenhangskomponente zu prüfen. Ein Graph ist nur chordal, wenn alle seine Komponenten es sind. MCS erfasst Komponenten von selbst, wenn es über alle Knoten läuft, doch eine komponentenweise Implementierung muss über alle iterieren.

Häufig gestellte Fragen

Was ist ein chordaler Graph?

Ein chordaler Graph ist einer, in dem jeder Zyklus aus vier oder mehr Knoten eine Sehne besitzt, also eine Kante zwischen zwei auf diesem Zyklus nicht aufeinanderfolgenden Knoten. Gleichbedeutend hat er keinen induzierten Zyklus länger als ein Dreieck. Bäume, vollständige Graphen und Intervallgraphen sind alle chordal; der reine 4-Zyklus ist der kleinste Graph, der es nicht ist.

Wie prüft man, ob ein Graph chordal ist?

Führe eine Maximum-Cardinality-Search aus, um eine Kandidatenordnung für perfekte Elimination zu erhalten, und verifiziere sie dann: für jeden Knoten müssen seine in der Ordnung späteren Nachbarn alle zum frühesten unter ihnen benachbart sein. Besteht die Verifikation, ist der Graph chordal; scheitert sie, existiert keine perfekte Eliminationsordnung und er ist es nicht. Der gesamte Test ist O(V + E).

Was ist eine perfekte Eliminationsordnung?

Eine Knotenordnung, in der jeder Knoten zusammen mit seinen später erscheinenden Nachbarn eine Clique bildet. Ein Graph besitzt genau dann eine solche Ordnung, wenn er chordal ist, weshalb das Finden und Verifizieren einer solchen der Standardtest auf Chordalität ist.

Warum sind chordale Graphen wichtig?

Weil mehrere allgemein NP-schwere Probleme auf ihnen linear werden. Maximum-Clique, Graphfärbung, maximale unabhängige Menge und minimale Cliquenüberdeckung sind auf einem chordalen Graphen alle in O(V + E) lösbar, indem man die Eliminationsordnung nutzt. Chordale Graphen sind zudem genau jene, die eine Baumzerlegung in Cliquen zulassen, worauf baumweitenbasierte Algorithmen aufbauen.

Sind alle Bäume chordal?

Ja, trivialerweise. Chordalität schränkt nur Zyklen der Länge 4 oder mehr ein, und ein Baum hat überhaupt keine Zyklen, die Bedingung ist also leer erfüllt. Am anderen Ende sind auch vollständige Graphen chordal, da bereits jede mögliche Sehne vorhanden ist.