Ordnung Automorphismengruppe < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Bestimme die Ordnung der Automorphismengruppe des folgenden Graphen |
Hallo,
sei ein Graph mit zwölf Knoten (Punkten) gegeben. Wie bestimme ich davon die Automorphismengruppe, bzw die Ordnung der Automorphismengruppe? Definitionsgemäß weiß ich, dass die Automorphismengruppe alle Permutationen enthält, die angewandt auf die Knotenmenge wieder denselben Graphen, bzw. die selben Kanten ergibt.
Konkret haben wir einen Graphen gegeben und sollen davon die Ordnung der Automorphismengruppe bestimmen. Ich möchte das aber allgemein verstehen. Was muss ich dazu alles erstmal rausfinden?
Vielen Dank schonmal
|
|
| |
|
Hey,
Du weißt sicher, dass ein Graph eindeutig durch seine Adjazenzmatrix $A$ bestimmt ist, oder?
Nimm dir eine Permutation [mm] $\pi$, [/mm] die zugehörige Permutationsmatrix $P$ und gucke, was der Zusammenhang zwischen $A$ und [mm] $PAP^{-1}$ [/mm] sein muss...
Ich behaupte einfach mal: [mm] $\pi$ [/mm] ist ein Automorphismus von $G$, genau dann, wenn [mm] $PAP^{-1} [/mm] = A$ gilt.
Die Menge dieser Permutationsmatrizen zu bestimmen ist nun eine Aufgabe, die unabhängig vom Graphen ist.
Wenn du das effizient berechnen willst (von Hand oder für sehr große Graphen), kannst du dir eine ganze Menge Dinge überlegen, um nicht die ganze [mm] $S_n$ [/mm] ausprobieren zu müssen.
Ein kleines Beispiel dazu:
Weißt du, was das Gewicht eines Knotens ist?
Sei $G=(V,E)$ ein (ungerichteter) Graph mit $|V|=n [mm] \in \IN$.
[/mm]
Ist [mm] $v\in [/mm] V$ ein Knoten, so ist $w(v) := [mm] |\{v \neq x \in V \mid (v,x) \in E\}|$.
[/mm]
Nun können wir $V$ zerlegen in $V = [mm] V_0 \cup V_1 \cup V_2 \cup \ldots \cup V_n$ [/mm] wobei [mm] $V_i [/mm] = [mm] \{v \in V \mid w(v) = i\}$.
[/mm]
Dies ist eine Partition von $V$.
Sei nun [mm] $\phi [/mm] : V [mm] \to [/mm] V$ ein Automorphismus.
Überlege dir, wieso [mm] $\phi_{|V_i} [/mm] : [mm] V_i \to V_i$ [/mm] ebenfalls für alle $i$ ein Automorphismus sein muss, das heißt das Gewicht von Knoten beim Permutieren erhalten bleibt.
Dies schränkt deine Möglichkeiten der Permutationen in manchen Fällen schon ordentlich ein....
Solche Überlegungen kannst du eine ganze Menge anstellen - zB kann man sich überlegen, was mit den Zusammenhangskomponenten von $G$ passiert - es gibt halt einen Grund, warum Graphentheorie oft als eingenes Fach betrieben wird.
lg
Schadow
|
|
|
|
