Automorphismus < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:42 Mo 21.02.2011 | | Autor: | hilado |
| Aufgabe | Bestimmen Sie die Ordnung der Automorphismengruppe des vollständigen bipartiten Graphen [mm] K_{3, 3}.
[/mm]
Zur Erinnerung: Automorphismen eines Graphen sind die bijektiven Funktionen auf der Eckenmenge, die Kanten in Kanten überführen. |
Ich hab hier einen Absatz, nur leider verstehe ich ihn noch nicht ganz hunderprozentig (mein Teil dazu ist blau geschrieben):
Sei A die Automorphismengruppe des vollständigen bipartiten Graphen [mm] K_{3, 3}, [/mm] d.h. die Gruppe der Bijektionen auf der Eckenmenge von [mm] K_{3,3}, [/mm] die Kanten auf Kanten abbilden. Sei x eine Ecke im [mm] K_{3,3}. [/mm] A operiert transitiv auf der Eckenmenge, also ist |Ax| = 6.
Inwiefern tranistiv? Wo gibt es hier die Transitivität?
Automorphismen, die die Ecke x festlassen, können deren Nachbarn frei permutieren, sowie wiederum deren Nachbarn (auser x!) vertauschen.
Ich nehme an, dass wenn ich in diesem Beispiel eine Bijektion festhalte, dass ich die Bijektionen der anderen vertauschen kann, also beispielsweise wir haben 1 -> 2 und 3 -> 4 dann kann ich sagen, 1 -> 4 und 3 -> 2, oder ? Oder wie kann ich das verstehen?
Damit ist [mm] |A_{x}| [/mm] = 3! * 2 = 12, und es folgt
|A| = |Ax| * |Ax| = 6 * 12 = 72
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:57 Di 22.02.2011 | | Autor: | felixf |
Moin!
> Bestimmen Sie die Ordnung der Automorphismengruppe des
> vollständigen bipartiten Graphen [mm]K_{3, 3}.[/mm]
>
> Zur Erinnerung: Automorphismen eines Graphen sind die
> bijektiven Funktionen auf der Eckenmenge, die Kanten in
> Kanten überführen.
Die Definition ist sehr schlecht gewaehlt: sobald der Graph unendlich viele Ecken oder Kanten hat, ist die Umkehrfunktion eines Automorphismus nicht umbedingt ein Graphenhomomorphismus...
Bei endlichen Graphen geht's aber.
> Ich hab hier einen Absatz, nur leider verstehe ich ihn
> noch nicht ganz hunderprozentig (mein Teil dazu ist blau
> geschrieben):
>
> Sei A die Automorphismengruppe des vollständigen
> bipartiten Graphen [mm]K_{3, 3},[/mm] d.h. die Gruppe der
> Bijektionen auf der Eckenmenge von [mm]K_{3,3},[/mm] die Kanten auf
> Kanten abbilden. Sei x eine Ecke im [mm]K_{3,3}.[/mm] A operiert
> transitiv auf der Eckenmenge, also ist |Ax| = 6.
>
>
> Inwiefern tranistiv? Wo gibt es hier die Transitivität?
>
Lies mal ![[]](/images/popup.gif) hier nach, was es bedeutet, dass eine Gruppenoperation transitiv ist.
> Automorphismen, die die Ecke x festlassen, können deren
> Nachbarn frei permutieren, sowie wiederum deren Nachbarn
> (auser x!) vertauschen.
>
>
> Ich nehme an, dass wenn ich in diesem Beispiel eine
> Bijektion festhalte, dass ich die Bijektionen der anderen
> vertauschen kann, also beispielsweise wir haben 1 -> 2 und
> 3 -> 4 dann kann ich sagen, 1 -> 4 und 3 -> 2, oder ? Oder
> wie kann ich das verstehen?
Das was du geschrieben hast ergibt keinen Sinn.
Du hast doch einmal eine Menge
1 4
2 5
3 6
wobei jeweils 1, 2, 3 mit 4, 5, 6 in allen Kombinationen verbunden sind, jedoch innerhalb der Gruppen 1, 2, 3 und 4, 5, 6 keine Kanten existieren.
Wenn du jetzt ein x fest waehlst, sagen wir $x = 1$, dann kannst du mit einem Automorphismus die Nachbarn von $x$ -- das sind $4, 5, 6$ -- beliebig permutieren. Das Ergebnis ist und bleibt ein Graphenautomorphismus.
Weiterhin kannst du die Nachbarn von $4, 5, 6$, ausser $x$, wieder permutieren: das sind 2 und 3.
Also: jede Permutation von [mm] $\{ 2, 3 \}$ [/mm] zusammen mit jeder Permutation von [mm] $\{ 4, 5, 6 \}$ [/mm] liefert genau einen Automorphmismus vom Graphen, der $x = 1$ festhaelt.
Ist es jetzt etwas klarer?
LG Felix
|
|
|
|
