Definition - Isomorphie von Graphen

• Typen:
  • Isomorphie von Wurzelbäumen
• Notwendige Bedingungen
  • Kardinalität der Kantenmengen muss übereinstimmen
  • Kardinalität der Knotenmengen muss übereinstimmen
  • Die Anzahl der Knoten mit gleicher Valenz muss übereinstimmen
  • Knoten mit gleicher Valenz müssen auch Nachbarknoten mit übereinstimmenden Valenzen haben
• Involvierte Definitionen:
  • Graph
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Definition: Isomorphie von Graphen

Seien und zwei Graphen.

Wir nennen isomorph, wenn es eine bijektive Abbildung gibt, sodass

Anmerkung

Die Idee

Die Idee ist, dass isomorphe Graphen unterschiedliche Darstellungen desselben Graphen sind. Einen Graphen mit Knoten und Kanten kann ich ja auf unterschiedliche Arten zeichnen.