Definition - Eulertour

• Generalisierungen:
  • Eulerpfad
• Hinreichende Aussagen:
  • Eulertouren lassen sich mit dem Hierholzer-Algorithmus bestimmen.
• Charakterisierungen:
  • ist zusammenhängend und alle Knoten haben einen geraden Knotengrad
  • ist zusammenhängend und ist eine kantendisjunkte Vereinigung von Kreisen.
  • Charakterisierung eulerscher Digraphen
• Involvierte Definitionen:
  • Graph
  • Multigraph
  • Spaziergang
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Definition: Eulertour

Sei ein (Multi)graph ohne isolierte Knoten, also

Falls gilt:

es existiert ein --Spaziergang durch , der

• in beginnt,
• in endet und
• jede Kante in genau einmal durchläuft

so bezeichnen wir diese Spaziergänge als Eulertouren und den Graph als eulersch.