Havel-Hakimi-Algorithmus

Der Havel-Hakimi-Algorithmus (oder auch Verfahren nach Havel-Hakimi) ist ein Verfahren aus der Graphentheorie, mit dem die Existenz eines einfachen Graphen zu einer gegebenen Valenzsequenz bestimmt und konstruiert werden kann. Der Algorithmus basiert auf dem Havel-Hakimi Theorem.

Havel-Hakimi-Theorem

Sei $D=(d_{1},d_{2},...,d_{n})$ eine herabsteigende Folge, das heißt, es gilt $d_{i}\geq d_{i+1}$. Es gilt, $D$ ist genau dann eine Gradfolge, wenn die Folge

$D'=(d_{2}-1,d_{3}-1,\dots ,d_{d_{1}+1}-1,d_{d_{1}+2},d_{d_{1}+3},\dots ,d_{n})$

eine Gradfolge ist.

Algorithmus

1. Wähle den höchsten Grad $d_{1}=\max(D)$ und verbinde einen Knoten $d_{1}$-Mal.
2. Ziehe für die nächsten $d_{1}$ Grade jeweils $1$ ab und setze $D:=D\setminus \{d_{1}\}$.
3. Wiederhole Schritt 1 so lange, bis du entweder keine Grade mehr hast, also $D$ nur aus $0$en besteht (dann ist $D$ eine Gradfolge) oder du keine Knoten mehr verbinden kannst, weil bei Schritt 2 entweder negative Zahlen in $D$ entstehen würden oder du zu wenig Knoten in $D$ hast. ($D$ ist keine Gradfolge)

Name

Das Havel-Hakimi-Theorem wurde 1955 von dem tschechischen Mathematiker Václav J. Havel veröffentlicht. Weil das Theorem zunächst nur in tschechischer Sprache mit einer deutschen und russischen Zusammenfassung publiziert wurde, wurde es zunächst in der Wissenschaft kaum wahrgenommen. Ein weiterer Beweis wurde 1962 unabhängig von Seifollah Louis Hakimi (1932–2005) im SIAM Journal on Applied Mathematics publiziert.

Literatur

• Václav Havel: Poznámka o existenci konečných grafů. In: Časopis pro pěstování matematiky (Band 80, Nr. 4). ISSN=0528-2195, (online), (tschechisch, Zusammenfassung auf Russisch und Deutsch).
• Antal Iványi u. a.: On Erdös-Gallai and Havel-Hakimi algorithms. In: Acta Universitatis Sapientiae. Informatica. Bd. 3, 2. 2011. S. 230–268