Isomorphie von Graphen

Ein Graph G₁=(V₁,E₁) heißt isomorph zu einem Graphen wenn es je eine bijektive Abbildung von V₁ auf V₂ und von E₁ auf E₂ gibt, die verträglich mit der Inzidenzfunktion ist, d.h., sind u,v die Endpunkte einer Kante bzw. u Startpunkt eines Bogens und v 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.