Havel-Hakimi-Algorithmus

Algorithmus in der Graphentheorie

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.

Havel-Hakimi-Theorem

Bearbeiten

Sei   eine herabsteigende Folge, das heißt, es gilt  . Es gilt,   ist genau dann eine Gradfolge, wenn die Folge

 

eine Gradfolge ist.[2]

Algorithmus

Bearbeiten
  1. Wähle den höchsten Grad   und verbinde einen Knoten  -Mal.
  2. Ziehe für die nächsten   Grade jeweils   ab und setze  .
  3. Wiederhole Schritt 1 so lange, bis du entweder keine Grade mehr hast, also   nur aus  en besteht (dann ist   eine Gradfolge) oder du keine Knoten mehr verbinden kannst, weil bei Schritt 2 entweder negative Zahlen in   entstehen würden oder du zu wenig Knoten in   hast. (  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.

Literatur

Bearbeiten
  • 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

Einzelnachweise

Bearbeiten
  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.