Zum Inhalt springen

Graph/Kantengraph/Automorphismengruppe/Aufgabe/Lösung

Aus Wikiversity


  1. Wir definieren

    Einem Automorphismus des Graphen wird also die Abbildung auf der Kantenmenge zugeordet, die eine Kante auf die Bildkante (!) unter abbildet. Die Gesamtabbildung ist wegen

    ein Homomorphismus in das Monoid der Abbildungen auf der Kantenmenge. Wegen

    gehört das Bild von zur Permutationsgruppe der Kantenmenge. Es ist noch zu zeigen, dass ein Automorphismus des Kantengraphen ist. Es sei also ein Graphautomorphismus und seien Kanten, die im Kantengraph adjazent sind. Das bedeutet, dass sie im Graphen koinzident sind und daher ist und . Dann sind auch und koinzident und somit adjazent im Kantengraphen.

  2. Wir betrachten den linearen Graphen mit zwei Punkten. Seine Automorphismengruppe ist neben der Identität durch die Vertauschung der beiden Punkte gegeben. Der Kantengraph ist einpunktig und hat triviale Automorphismengruppe.

  3. Es sei der vollständige Graph zu vier Punkten mit dem zugehörigen Kantengraphen (siehe Skizzen). Wir betrachten den Automorphismus des Kantengraphen, der und vertauscht und auf sich selbst abbildet. Da sowohl als auch im Kantengraphen mit verbunden sind, liegt ein Automorphismus vor. Wir behaupten, dass man diesen nicht durch einen Graphautomorphismus von realisieren kann. Es sei ein solcher Homomorphismus. Da die Kanten und auf sich selbst abgebildet werden, muss auf sich abgebildet werden. Deshalb müssen auch und auf sich selbst abgebildet werden und muss die Identität sein. Dann ist aber auch die Identität.