Ungerichtete Graphen/Automorphismengruppe/Einführung/Textabschnitt

Definition

Es sei ${}G=(V,E)$ ein Graph. Ein Isomorphismus ${}\varphi \colon G\rightarrow G$ heißt Automorphismus.

Definition

Zu einem Graphen ${}G$ nennt man die Gruppe aller Automorphismen

$\varphi \colon G\longrightarrow G$

die Automorphismengruppe von ${}G$. Sie wird mit ${}\operatorname {Aut} \,G$ bezeichnet.

Statt von der Automorphismengruppe spricht man auch von Symmetriegruppe des Graphen.

Beispiel

Die Automorphismengruppe eines Sterngraphen mit einem Zentrum und ${}n\geq 2$ Blättern ist die volle Permutationsgruppe ${}S_{n}$, da man die Blätter beliebig ineinander überführen kann und das Zentrum auf sich selbst abgebildet werden muss.

Beispiel

Wir wollen die Automorphismengruppe des chemischen Elementes Butan (bzw. der zugehörigen Darstellung als Graph ${}G$) bestimmen. Zunächst halten wir fest, dass die Benennung von einigen Knotenpunkten mit ${}C$ und mit ${}H$ (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 ${}4$ werden mit ${}C$ und die Punkte mit dem Grad ${}1$, also die Blätter, werden mit ${}H$ bezeichnet. In den folgenden Überlegungen werden wir zwecks Vereinfachung die chemischen Benennungen verwenden. Ein Automorphismus des Graphen führt ${}H$-Atome in ${}H$-Atome und ${}C$-Atome in ${}C$-Atome über, da der Grad bei einem Isomorphismus erhalten bleibt. Dies führt insbesondere zu einem Gruppenhomomorphismus

$\Psi \colon \operatorname {Aut} \,G\longrightarrow S_{4},$

wobei ${}S_{4}$ die Gruppe der Permutationen auf den vier ${}C$-Atomen und ${}\Psi$ die Einschränkung eines Automorphismus bezeichnet. Bei einem Automorphismus ${}\varphi$ des Moleküls wird also geschaut, was dieser mit den ${}C$-Atomen macht. Diese Gesamtzuordnung ist ein Gruppenhomomorphismus. Die vier ${}C$-Atome haben zwar alle den Grad ${}4$, 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 ${}\Psi$ die zyklische Gruppe

${}\mathbb {Z} /(2)=S_{2}\,$

(in der Tat ist die Spiegelung an der vertikalen Achse ein Automorphismus). Wir haben also einen surjektiven Gruppenhomomorphismus

$\Psi \colon \operatorname {Aut} \,G\longrightarrow S_{2}.$

Dies erleichtert die Bestimmung der Automorphismengruppe, da man diese aufspalten kann nach solchen Automorphismen, die auf den ${}C$-Atomen identisch wirken, und solchen, die die ${}C$-Atome spiegeln. Aufgrund von gruppentheoretischen Gesetzmäßigkeiten gibt es von beiden Sorten gleich viele. Deshalb betrachten wir nur noch den Kern von ${}\Psi$. Es sei also ${}\varphi$ ein Automorphismus, der auf den ${}C$-Atomen identisch wirkt. Dann wird jedes ${}H$-Atom unter ${}\varphi$ auf ein ${}H$-Atom abgebildet, das mit dem selben ${}C$-Atom verbunden ist. Was unter ${}\varphi$ mit den an einem ${}C$-Atom hängenden ${}H$-Atomen passiert, ist unabhängig voneinander. Der Kern ist deshalb gleich

$S_{3}\times S_{2}\times S_{2}\times S_{3}$

und besitzt ${}144$ Elemente, die gesamte Automorphismengruppe besitzt ${}288$ Elemente.

Definition

Ein Graph ${}G=(V,E)$ heißt homogen, wenn es zu je zwei Knotenpunkten ${}u,v\in V$ einen Automorphismus

$\varphi \colon G\longrightarrow G$

mit

${}\varphi (u)=v\,$

gibt.

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.

Definition

Ein Graph ${}G=(V,E)$ heißt starr, wenn die Automorphismengruppe von ${}G$ trivial ist.

Bei einem starren Graphen sind je zwei Knotenpunkte graphentheoretisch unterscheidbar. Statt starr sagt man auch asymmetrisch oder rigide.

Beispiel

Der abgebildete Graph ${}G$ 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 ${}\varphi$ ein Automorphismus von ${}G$. Der Graph verfügt nur über ein einziges Blatt ${}b$ (links oben), diese muss auf sich selbst abgebildet werden. Damit muss auch der an das Blatt anliegende Knotenpunkt ${}u$ auf sich selbst abgebildet werden. Die an ${}u$ anliegenden Knotenpunkte (außer ${}b$) haben die Grade ${}2,3,4$, sie müssen also jeweils auf sich selbst abgebildet werden. Dann muss auch der verbleibende Punkt auf sich selbst abgebildet werden.