Hauptmenü öffnen

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]

NameBearbeiten

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.

LiteraturBearbeiten

  • 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

EinzelnachweiseBearbeiten

  1. Matches for: MR=148049 Definition auf mathscinet.ams.org. Abgerufen am 10. September 2018.