Definition - Multigraph

• Typen:
  • Graph
  • Eulerscher Graph
• Konstrukte:
  • Parallele Kanten
  • Schleife
  • Eulertour
• Involvierte Definitionen:
  • Graph
  • Knoten
  • Kanten
  • Adjazenz
• Veranstaltung: AlMa
• Referenz: @hochstaettlerWiSe22

⠀

Definition: Multigraph

Als Multigraph bezeichnen wir, genauso wie Graphen, Strukturen aus Knoten und Kanten.

Anders als in normale Graphen, können zwei Knoten in einem Multigraphen mit mehr als einer Kante verbunden werden. Wir sprechen hier auch von parallelen Kanten.

Außerdem sind reflexive Schleifen erlaubt, also Kanten nach dem Schema , wobei .

Wir schreiben Multigraphen als Tripel

Wobei die Menge der Knoten, die Menge der Kanten und die Adjazenzfunktion ist.

Anmerkung

Beispiel für , und

Hier ein paar Beispielbelegungen für , und :

• ,
• und