3. Isomorphe Graphen

Wir untersuchen nun die Frage nach der strukturellen Gleichheit zweier Graphen, ihrer sogenannten Isomorphie. Anschaulich bedeutet die Isomorphie zweier Graphen, dass sich die Graphen lediglich in den Namen ihrer Ecken unterscheiden. Präzisieren können wir diese Anschauung mit Hilfe von Funktionen, die die Ecken des einen Graphen bijektiv auf die Ecken des anderen Graphen abbilden und dabei in beiden Richtungen Kanten in Kanten übersetzen. Die Idee der Begriffsbildung ist für die Mathematik von großer Bedeutung, alle mathematischen Strukturen lassen sich aus der Perspektive der Isomorphie betrachten. Die Graphen bilden ein instruktives Beispiel mit überraschend schwierigen Fragestellungen.