Isomorphie von Graphen
Ein Graph
heißt isomorph zu einem Graphen
wenn es je eine bijektive Abbildung
von
auf
und
von
auf
gibt, die verträglich mit der Inzidenzfunktion ist, d.h.,
sind
die Endpunkte einer Kante bzw.
Startpunkt eines Bogens und
Zielpunkt
dieses Bogens, dann sind
und
Endpunkte einer Kante bzw.
Startpunkt und
Zielpunkt eines Bogens.
Die folgenden Abbildungen zeigen zwei zueinander isomorphe Graphen.
Die Abbildung
mit
ist
ein Isomorphismus.
Es ist sogar jede bijektive Abbildung von {1,2,3,4} auf {a,b,c,d} ein Isomorphismus,
weil die Graphen vollständige Graphen mit gleicher
Knotenzahl sind.