Automorphismen und Graphen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:16 Di 17.01.2006 | | Autor: | Becks |
| Aufgabe | Zu zeigen:
a) Für jeden Graphen (V,E) ist die Menge aller Automorphismen von (V,E) eine Untergruppe der symmetrischen Gruppe Sym V.
b) Die Automorphismengruppe des Baumes ({1,2,3,4},{{1,2},{1,3}{1,4}}) ist isomorph zur symmetrischen Gruppe [mm] S_{3} [/mm] |
Hallo zusammen!
Also bei der a) habe ich mir gedacht:
Ein Automorphismus ist ja beim Graphen eine Permutation der Knoten. Aber die symmetrische Gruppe ist ja auch die Menge aller Permutationen einer Menge M. Also das ist ja die Knotenmenge. Dann muss ich ja nur zeigen, dass es ne Untergruppe ist oder? Hmm, stimmt das bis jetzt und gehe ich das richtig an?
bei der b)
da weiß ich nicht wie ich das angehen soll. also ich habe wieder nen Graphen. Mit 1 in der Wurzel und 3 Ästen. Aber die symmetrische Gruppe S3 ist doch {1,2}{1,3}{2,3} oder?
Ich hoffe ihr könnt mir da helfen.
Viele liebe Grüße
Becks
|
|
| |
|
Hallo,
zu (a): Dein erster Ansatz ist vollkommen richtig. Du musst also nur Abgeschl. unter Mult. und Inversenbildung zeigen. Dass die Identitaet ein Autom. ist, ist klar, oder ?
Zu (b): Ueberleg Dir doch allgemein, dass fuer einen Automorphismus [mm] f\colon V\to [/mm] V
fuer jeden Knoten [mm] v\in [/mm] V die Knotengrade von v und f(v) gleich sein muessen
(beweise das ruhig mal formal). Dann folgt doch aber in dem konkreten Beispiel, dass die
Wurzel nur auf sich selbst abgebildet werden kann. Und die restlichen drei Knoten ???
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:06 Mi 18.01.2006 | | Autor: | Becks |
Morgen :)
zu a)
Hmm, und wie mache ich das? Ich glaube ich stehe etwas auf dem Schlauch.
zu b)
Die Symmetrische Gruppe S3 hat doch nur 3 Elemente. Mein Baum hat aber 4 Knoten. Ich komme da irgendwie nicht weiter.
Könnt ihr mir vielleicht noch nen Tipp geben?
MFG Becks
|
|
|
| |
|
Hallo nochmal,
zu (a): Ein Autom f von G ist ja eine Bij. [mm] f\colon V\to [/mm] V, so dass fuer alle
[mm] u,v\in [/mm] V gilt : [mm] \{u,v\}\in E\:\Leftrightarrow\: \{f(u),f(v)\}\in [/mm] E
Zeig also doch mal zunaechst, dass, wenn f und g solche Autom. sind, dann auch die
Verknuepfung [mm] f\circ [/mm] g diese Eigenschaft hat.
Zu (b): Richtig, Dein Baum hat 4 Knoten, aber einer wird stets auf sich selbst abgeb. (von jedem Automorphismus !!!), und die anderen drei .......
... koennen frei permutiert werden oder ??? 
Viele Gruesse,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:27 Mi 18.01.2006 | | Autor: | Becks |
zu a)
da muss ich erstmal überlegen :)
zu b)
Ach so, und der Knoten, der durch jeden Automorphismus auf sich selber abgebildet wird, ist die Wurzel!
Aber in der symmetrischen Gruppe S3 habe ich doch auch {1,2,3} und solche Kombinationen. Die existieren doch in meinem Baum nicht. Da habe ich nur {1,2} usw.
|
|
|
| |
|
Hallo nochmal,
also um es noch mal zu verdeutlichen: Automorphismen sind ja Abbildungen
[mm] f\colon V\to [/mm] V der Knotenmenge V auf sich. [mm] S_3 [/mm] ist die Menge aller Permutationen
einer dreielementigen Menge. Wie Du ja jetzt selber nochmal richtig geschrieben hast,
bleibt die Wurzel fix, und die anderen drei Knoten koennen frei permutiert werden.
Alles klar ?
Gruss,
Mathias
|
|
|
|
