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.^[1] Der Algorithmus basiert auf dem Havel-Hakimi Theorem.

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

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

eine Gradfolge ist.^[2]

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

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.

• 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

1. ↑ Matches for: MR=148049 Definition auf mathscinet.ams.org. Abgerufen am 10. September 2018.
2. ↑ Stefan Felsner: Graphentheorie. Technische Universität Berlin, abgerufen am 4. Februar 2021.