Automorphismen und Graphen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:36 Sa 19.11.2011 | | Autor: | Sin777 |
| Aufgabe | Graph G=(E,K) mit:
E die Menge aller Teilmengen T aus [mm] \{1,2,3,4,5\} [/mm] mit |T|=2.
Zwei Ecken e1, e2 [mm] \in [/mm] E sind verbunden, wenn e1 [mm] \cap [/mm] e2 = [mm] \emptyset.
[/mm]
(a) Zeige, dass die Gruppe der Automorphismen Aut(G) zu [mm] (S_{5},\circ) [/mm] isomorph ist. |
Also ich hatte bis jetzt noch keine Graphentheorie gehört und diese Aufgabe wurde uns einfach so in einer Vorlesung (nicht Graphentheorie) aufs Übungsblatt gepackt. Ich habe nur eine kurze Definition was ein Graph ist und was ein Automorphismus ist aber sonst noch keine Erfahrungen mit diesen Begriffen und weiß nun überhaupt nichts mit dieser Aufgabe (schon mit Teil (a)) anzufangen.
Ich weiß, dass [mm] \alpha \in [/mm] Aut(G) ist, wenn [mm] \{e1,e2\} \in [/mm] E <=> [mm] \{\alpha(e1),\alpha(e2)\} \in [/mm] E ist. Ich kann mir vorstellen, dass das bedeutet, dass wenn ich die Ecken permutiert habe und ich dann wieder die gegebenen Kanten auf diese Anwende, der gleiche Graph herauskommen muss. Aber wie wende ich das jetzt auf die Aufgabe an?
Es gibt 10 solche oben beschriebenen Teilmengen und es gibt 29 solcher schnittmengen die nicht leer sind. Aber [mm] S_{5} [/mm] hat doch 5! Elemente... Da kann doch irgendetwas nicht stimmen. Und ich weiß nicht, nach welchem Schema ich hier die Automorphismengruppe überhaupt bestimmen kann, um dann die Isomorphie zu prüfen.
Ich hoffe es kann mir jemand mit dieser Aufgabe ein wenig auf die Sprünge helfen.
Vielen, vielen Dank im voraus. Ich freue mich wirklich sehr über jede Hilfestellung.
Gruß
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:11 Sa 19.11.2011 | | Autor: | felixf |
Moin!
> Graph G=(E,K) mit:
> E die Menge aller Teilmengen T aus [mm]\{1,2,3,4,5\}[/mm] mit
> |T|=2.
> Zwei Ecken e1, e2 [mm]\in[/mm] E sind verbunden, wenn e1 [mm]\cap[/mm] e2
> [mm]\not= \emptyset.[/mm]
>
> (a) Zeige, dass die Gruppe der Automorphismen Aut(G) zu
> [mm](S_{5},\circ)[/mm] isomorph ist.
> Also ich hatte bis jetzt noch keine Graphentheorie gehört
> und diese Aufgabe wurde uns einfach so in einer Vorlesung
> (nicht Graphentheorie) aufs Übungsblatt gepackt. Ich habe
> nur eine kurze Definition was ein Graph ist und was ein
> Automorphismus ist aber sonst noch keine Erfahrungen mit
> diesen Begriffen und weiß nun überhaupt nichts mit dieser
> Aufgabe (schon mit Teil (a)) anzufangen.
>
> Ich weiß, dass [mm]\alpha \in[/mm] Aut(G) ist, wenn [mm]\{e1,e2\} \in[/mm]
> E <=> [mm]\{\alpha(e1),\alpha(e2)\} \in[/mm] E ist. Ich kann mir
> vorstellen, dass das bedeutet, dass wenn ich die Ecken
> permutiert habe und ich dann wieder die gegebenen Kanten
> auf diese Anwende, der gleiche Graph herauskommen muss.
> Aber wie wende ich das jetzt auf die Aufgabe an?
Nun, du suchst eine bijektive Abbildung [mm] $\Phi [/mm] : [mm] S_5 \to [/mm] Aut(G)$. Wenn du eine Permutation [mm] $\sigma \in S_5$ [/mm] von [mm] $\{ 1, 2, 3, 4, 5 \}$ [/mm] gegeben hast, wie kannst du etwa [mm] $\Phi(\sigma)(\{ 1, 2 \})$ [/mm] definieren? [mm] $\Phi(\sigma)$ [/mm] soll ja eine bijektive Abbildung $E [mm] \to [/mm] E$ sein.
Es gibt hier im eigentlich nur eine Abbildung, die Sinn macht (sprich: die du direkt hinschreiben kannst). Diese wird es wohl auch sein  Zeige, dass sie wohldefiniert ist (sprich: [mm] $\Phi(\sigma)$ [/mm] ist fuer jedes [mm] $\sigma \in S_5$ [/mm] ein Automorphismus von $G$), dass sie ein Homomorphismus ist [mm] ($\Phi(\sigma \circ \tau) [/mm] = [mm] \Phi(\sigma) \circ \Phi(\tau)$ [/mm] - das sollte sehr einfach sein), dass sie injektiv ist (da es ein Homomorphismus ist musst du zeigen, dass aus [mm] $\sigma \in \ker \Phi$ [/mm] Folgt [mm] $\sigma [/mm] = [mm] id_{\{ 1, \dots, 5 \}}$) [/mm] und schliesslich dass sie surjektiv ist. Letzteres ist vermutlich das Schwierigste.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:23 Do 24.11.2011 | | Autor: | Sin777 |
Vorsicht:!! Ich habe mich am Anfang verschrieben, es war nicht ungleich sondern gleich der leeren Menge. Die Aufgabe wurde uns falsch gestellt und somit haben wir nochmal eine Woche Zeit. Schlauer werde ich aber trotzdem nicht.
Aut(G) ist ja die Menge der isomorphen Abbildungen von G in sich selbst. Aber was heißt das nun beim Graphen? Du sagst also, man betrachtet dabei nur die Abbildung der Knoten.
Es gibt ja 120 Abbildungen in [mm] S_{5}, [/mm] wie komme ich denn darauf, dass es genau so viele Abbildungen bei diesem Graphen gibt?
Ich sitze jetzt schon seit ewigkeiten vor der Aufgabe und habe mir das, was du geschrieben hast, x-mal durchgelesen aber ich verstehe die Aufgabe immer noch nicht.
Mit Deiner Notation von phi und sigma komme ich leider auch nicht zurecht :(
Gruß
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:24 Sa 26.11.2011 | | Autor: | felixf |
Moin!
> Vorsicht:!! Ich habe mich am Anfang verschrieben, es war
> nicht ungleich sondern gleich der leeren Menge. Die Aufgabe
> wurde uns falsch gestellt und somit haben wir nochmal eine
> Woche Zeit. Schlauer werde ich aber trotzdem nicht.
Der Ansatz, den ich vorgeschlagen hab, ist hier immer noch gueltig.
> Aut(G) ist ja die Menge der isomorphen Abbildungen von G in
> sich selbst. Aber was heißt das nun beim Graphen? Du sagst
> also, man betrachtet dabei nur die Abbildung der Knoten.
Ein Automorphismus [mm] $\varphi$ [/mm] eines Graphen ist eine bijektive Abbildungen von der Menge der Knoten in sich selber, die vertraeglich mit der Adjazenz ist, sprich zwischen zwei Knoten $x$ und $y$ ist genau dann eine Kante, wenn zwischen [mm] $\varphi(x)$ [/mm] und [mm] $\varphi(y)$ [/mm] eine ist.
> Es gibt ja 120 Abbildungen in [mm]S_{5},[/mm] wie komme ich denn
> darauf, dass es genau so viele Abbildungen bei diesem
> Graphen gibt?
Eine Moeglichkeit ist, dass du alle bijektiven Abbildungen der Knotenmenge in sich selber aufschreibst, schaust welche davon Graphenautomorphismen sind, und dann schaust wie du sie zuordnen kannst. Wenn du so vorgehst, bist du mit etwas Glueck vor Weihnachten fertig.
> Ich sitze jetzt schon seit ewigkeiten vor der Aufgabe und
> habe mir das, was du geschrieben hast, x-mal durchgelesen
> aber ich verstehe die Aufgabe immer noch nicht.
>
> Mit Deiner Notation von phi und sigma komme ich leider auch
> nicht zurecht :(
Es waere gut, wenn du etwas konkreter sein wuerdest. Was genau verstehst du nicht?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:26 Sa 26.11.2011 | | Autor: | felixf |
Moin!
> Graph G=(E,K) mit:
Um das mal etwas zu konkretisieren:
* E ist die Menge der Ecken, auch Knoten genannt
* K ist die Menge der Kanten
Ein Graphenautomorphismus ist eine bijektive Abbildung [mm] $\alpha [/mm] : E [mm] \to [/mm] E$ mit [mm] $\forall [/mm] x, y [mm] \in [/mm] E : [mm] \{ x, y \} \in [/mm] K [mm] \Leftrightarrow \{ \alpha(x), \alpha(y) \} \in [/mm] K$.
> Ich weiß, dass [mm]\alpha \in[/mm] Aut(G) ist, wenn [mm]\{e1,e2\} \in[/mm]
> E <=> [mm]\{\alpha(e1),\alpha(e2)\} \in[/mm] E ist.
Hier hast du $E$ und $K$ verwechselt.
LG Felix
|
|
|
|
