Proposition - Für Isomorphie muss die Anzahl der Knoten mit gleicher Valenz übereinstimmen

• Involvierte Definitionen:
  • Graph
  • Isomorphie von Graphen
  • Valenz
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Proposition: Für Isomorphie muss die Anzahl der Knoten mit gleicher Valenz übereinstimmen

Seien und zwei Graphen.

Damit und isomorph sein können, muss die Anzahl der Knoten mit gleicher Valenz übereinstimmen. Es muss also gelten, dass

Anmerkung

Tipp zum Vorgehen

Wollen wir zwei Graphen vergleichen, so ist es hilfreich, die Notation zu verwenden, wobei einen Knoten und seine Valenz beschreibt.

Für zwei Graphen würden wir bspw. erhalten:

Nun können wir die Valenzen einfach miteinander matchen.