www.vorkurse.de
Ein Projekt von vorhilfe.de
Die Online-Kurse der Vorhilfe

E-Learning leicht gemacht.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Teams · Forum · Wissen · Kurse · Impressum
Forenbaum
^ Forenbaum
Status Mathe-Vorkurse
  Status Organisatorisches
  Status Schule
    Status Wiederholung Algebra
    Status Einführung Analysis
    Status Einführung Analytisc
    Status VK 21: Mathematik 6.
    Status VK 37: Kurvendiskussionen
    Status VK Abivorbereitungen
  Status Universität
    Status Lerngruppe LinAlg
    Status VK 13 Analysis I FH
    Status Algebra 2006
    Status VK 22: Algebra 2007
    Status GruMiHH 06
    Status VK 58: Algebra 1
    Status VK 59: Lineare Algebra
    Status VK 60: Analysis
    Status Wahrscheinlichkeitst

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Graphentheorie" - Automorphismen und Graphen
Automorphismen und Graphen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Automorphismen und Graphen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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ß

        
Bezug
Automorphismen und Graphen: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                
Bezug
Automorphismen und Graphen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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ß

Bezug
                        
Bezug
Automorphismen und Graphen: Antwort
Status: (Antwort) fertig Status 
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


Bezug
        
Bezug
Automorphismen und Graphen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorkurse.de
[ Startseite | Mitglieder | Teams | Forum | Wissen | Kurse | Impressum ]