Proposition - Für Isomorphie müssen Knoten mit gleicher Valenz auch Nachbarknoten mit übereinstimmenden Valenzen haben

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

⠀

Proposition: Für Isomorphie müssen Knoten mit gleicher Valenz auch Nachbarknoten mit übereinstimmenden Valenzen haben

Seien und zwei Graphen.

Damit und isomorph sein können, müssen Knoten mit gleicher Valenz auch Nachbarknoten mit übereinstimmenden Valenzen haben.

Gibt es in den jeweiligen Graphen mehrere Knoten mit gleicher Valenz, so müssen diese zwischen entsprechend zueinander gematcht werden können.

Anmerkung

Komplizierte mathematische Erläuterung

Sei mit .

Bezeichne die Valenzen der Nachbarn von .

Dann muss es auch in einen Knoten geben, dessen Nachbarn Valenzen haben, sodass

Wobei die Indexmenge von bis ist.