Definition - Spaziergang in einem Graphen

• Typen:
  • Weg in einem Graphen (jeder Weg ist auch ein Spaziergang)
  • Eulertour
• Konstrukte:
  • Zusammenhang eines Graphen
  • Eulerscher Graph
• Eigenschaften:
  • Anzahl der Spaziergänge zwischen zwei Knoten durch Matrizenmultiplikation
• Involvierte Definitionen:
  • Graph
  • Teilgraph
  • Weg
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Definition: Spaziergang in einem Graphen

Sei ein Graph.

Den Teilgraphen bezeichnen wir als v-v’-Spaziergang in , wenn er

• bei dem Knoten startet,
• bei endet,
• nur vorhandene Kanten “durchschreitet”.

Die Länge des Spaziergangs ist gleich der Anzahl durchschrittener Kanten.

Anmerkung

Spaziergang und Weg in einem Graphen

Spaziergänge und Wege in einem Graphen ähneln sich stark. In einem Spaziergang dürfen Knoten jedoch mehrfach durchlaufen werden. In einem Weg ist dies nicht erlaubt.