Algorithmus - Havel-Hakimi Verfahren

• Bewiesen durch:
  • Havel-Hakimi-Theorem
• Involvierte Definitionen:
  • Graph
  • Valenzsequenz
• Veranstaltung: AlMa
• Referenz:
  • Wikipedia
  • @herzogWiSe22

⠀

Algorithmus: Havel-Hakimi Verfahren

Sei eine monoton fallende Folge.

Mithilfe des Verfahrens nach Havel-Hakimi können wir bestimmen, ob die Valenzsequenz eines einfachen Graphen ist und diesen konstruieren.

1. Wähle den höchsten Grad .
2. Ziehe für die nächsten Grade jeweils ab. Setze .
3. Wiederhole Schritt 1 solange, bis

• du entweder keine Grade mehr hast, also . ( ist eine Valenzsequenz)
• bei Schritt 2 negative Zahlen entstehen ( ist keine Valenzsequenz)

Beispiele für das Aufstellen

Beispiele für das Zeichnen