Graph/Nachbarschaftsvergleich/Homomorphismus/Aufgabe/Lösung


  1. Die Äquivalenz von (1) und (2) ist klar. Es sei (2) erfüllt und sei die angegebene Abbildung. Wenn sind, so werden sie auf sich selbst abgebildet und daher bleiben Kanten erhalten. Sei . Es wird auf sich selbst und auf abgebildet. Wenn es eine Kante zwischen und gibt, dann nach (2) auch zwischen und . Es sei umgekehrt (3) erfüllt und sei . Dann ist und ist eine Kante. Da ein Graphhomomorphismus vorliegt, folgt, dass auch

    eine Kante ist, also auch .

  2. Wir argumentieren mit (1). Damit ist unmittelbar klar, dass diese Relation transitiv und reflexiv ist. Sie ist im Allgemeinen aber nicht antisymmetrisch. Betrachten wir den Graphen mit drei Punkten , wobei und Kanten seien und keine Kante. Dann ist

    und und stehen in Relation zueinander, sie sind aber nicht gleich.