Ungerichtete Graphen/Automorphismengruppe/Einführung/Textabschnitt
Es sei ein Graph. Ein Isomorphismus heißt Automorphismus.
Zu einem Graphen nennt man die Gruppe aller Automorphismen
die Automorphismengruppe von . Sie wird mit bezeichnet.
Statt von der Automorphismengruppe spricht man auch von Symmetriegruppe des Graphen.
Die Automorphismengruppe eines Sterngraphen mit einem Zentrum und Blättern ist die volle Permutationsgruppe , da man die Blätter beliebig ineinander überführen kann und das Zentrum auf sich selbst abgebildet werden muss.
Wir wollen die Automorphismengruppe des chemischen Elementes Butan (bzw. der zugehörigen Darstellung als Graph ) bestimmen. Zunächst halten wir fest, dass die Benennung von einigen Knotenpunkten mit und mit (was natürlich eine chemische Bedeutung hat) keine eigenständige graphentheoretische Information dartellt, da sie ja aus dem Graphen direkt rekonstruierbar ist: Die Punkte mit dem Grad werden mit und die Punkte mit dem Grad , also die Blätter, werden mit bezeichnet. In den folgenden Überlegungen werden wir zwecks Vereinfachung die chemischen Benennungen verwenden. Ein Automorphismus des Graphen führt -Atome in -Atome und -Atome in -Atome über, da der Grad bei einem Isomorphismus erhalten bleibt. Dies führt insbesondere zu einem Gruppenhomomorphismus
wobei die Gruppe der Permutationen auf den vier -Atomen und die Einschränkung eines Automorphismus bezeichnet. Bei einem Automorphismus des Moleküls wird also geschaut, was dieser mit den -Atomen macht. Diese Gesamtzuordnung ist ein Gruppenhomomorphismus. Die vier -Atome haben zwar alle den Grad , sie sind aber nicht gleichberechtigt, die beiden äußeren sind mit drei Blättern und die beiden inneren sind mit zwei Blättern verbunden. Wenn man die beiden inneren vertauscht, so muss man auch die beiden äußeren vertauschen, da ja bei einem Automorphismus Kanten erhalten bleiben. Deshalb ist das Bild von die zyklische Gruppe
(in der Tat ist die Spiegelung an der vertikalen Achse ein Automorphismus). Wir haben also einen surjektiven Gruppenhomomorphismus
Dies erleichtert die Bestimmung der Automorphismengruppe, da man diese aufspalten kann nach solchen Automorphismen, die auf den -Atomen identisch wirken, und solchen, die die -Atome spiegeln. Aufgrund von gruppentheoretischen Gesetzmäßigkeiten gibt es von beiden Sorten gleich viele. Deshalb betrachten wir nur noch den Kern von . Es sei also ein Automorphismus, der auf den -Atomen identisch wirkt. Dann wird jedes -Atom unter auf ein -Atom abgebildet, das mit dem selben -Atom verbunden ist. Was unter mit den an einem -Atom hängenden -Atomen passiert, ist unabhängig voneinander. Der Kern ist deshalb gleich
und besitzt Elemente, die gesamte Automorphismengruppe besitzt Elemente.
Ein homogener Graph sieht in jedem Punkt gleich aus, keine zwei Punkte sind durch graphentheoretische Eigenschaften unterscheidbar. Ein vollständiger Graph und ein leerer Graph sind homogen.
Ein Graph heißt starr, wenn die Automorphismengruppe von trivial ist.
Bei einem starren Graphen sind je zwei Knotenpunkte graphentheoretisch unterscheidbar. Statt starr sagt man auch asymmetrisch oder rigide.
Der abgebildete Graph ist starr. Bei einem solchen Nachweis geht man am besten sukzessive vor, man zeigt für einen Automorphismus unter Bezug auf graphentheoretische Eigenschaften, dass er alle Knoten auf sich selbst abbildet, wobei man mit besonders einfachen Knotenpunkten anfängt und dann weitere Knotenpunkte betrachtet und dabei verwendet, dass andere Knotenpunkte auf sich selbst abgebildet werden. Es sei also ein Automorphismus von . Der Graph verfügt nur über ein einziges Blatt (links oben), diese muss auf sich selbst abgebildet werden. Damit muss auch der an das Blatt anliegende Knotenpunkt auf sich selbst abgebildet werden. Die an anliegenden Knotenpunkte (außer ) haben die Grade , sie müssen also jeweils auf sich selbst abgebildet werden. Dann muss auch der verbleibende Punkt auf sich selbst abgebildet werden.
