Produkt disjunkter Zyklen < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 04:53 Mi 02.11.2011 | | Autor: | Mathegirl |
| Aufgabe | [mm] \sigma:= [/mm]
(A B C D E F G H I J K L M N O P
F M O K H I C E B J D P A L G N )
Das soll alles in eienr großen Klammer stehen, ich weiß leider nicht wie das geht)
Wir betrachten die Permutation der Menge X:={A,B,...,P}
[mm] (\sigma: X\to [/mm] X ist die bijektive Abbildung mit [mm] \sigma [/mm] (A)=F, [mm] \sigma [/mm] (B):=M usw)
Schreiben sie [mm] \sigma [/mm] als produkt von von disjunkten Zyklen.
Erstellen sie zunächst ein Bild, indem sie für jedes Element von X einen Punkt zeichnen und dann für jedes [mm] x\in [/mm] X den Punkt x durch den Pfeil mit [mm] \sigma [/mm] (x) verbinden. |
Kann mir einer Tipps zum zeichnen geben? Das verwirrt mich sehr!!!!
MfG
mathegirl
|
|
| |
|
Wie mache ich das? A wird z.B. aug F abgebildet, B auf M. Das ist ja klar, Aber was ist damit gemeint, ich soll ein Bild erstellen?
MfG
Mathegirl
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:06 Mi 02.11.2011 | | Autor: | Lippel |
Das ist in der Tat eine komische Aufgabe, daher würde ich mir aber auch nicht so den Kopf zerbrechen. Male 16 Punkte auf einen Kreis und nummeriere sie durch mit A bis P und mache dann jeweils einen Pfeil von x nach [mm] $\sigma(x)$ [/mm] für alle Buchstaben x. So wird das vielleicht zumindest noch einigermaßen übersichtlich.
Da nicht näher spezifiziert ist, was genau du veranschaulichen sollst, denke ich das würde ausreichen.
LG Lippel
|
|
|
| |
|
okay, weil ich habe keine andere Idee bei dieser Aufgabe. Das heißt, ich müsste z.B. A mit F verbinden, B mit M?
Aber was bedeutet: schreibe [mm] \sigma [/mm] als Produkt von disjunkten Zyklen?
MfG
Mathegirl
|
|
|
| |
|
moin Mathegirl,
Kennst du die Zykelschreibweise für Permutationen?
Nehmen wir mal als Beispiel:
[mm] $\phi [/mm] = [mm] \pmat{1 & 2 & 3 & 4 & 5 \\
2 & 4 & 3 & 5 & 1}$
[/mm]
Diese Permutation sieht in der Zykelschreibweise so aus:
[mm] $\phi [/mm] = (1,2,4,5)(3) = (1,2,4,5)$
Dies liest sich folgendermaßen:
1 -> 2
2 -> 4
4 -> 5
5 -> 1
3 -> 3
Also ein solcher Block, ein "Zykel" entspricht praktisch einem Kreis oder einer Reihe, wo jedes Element auf das, das jeweils da hinter steht abgebildet wird (das letzte geht dabei auf das erste).
Wenn ein Zykel nur ein Element beinhaltet heißt das dieses Element wird auf sich selbst abgebildet (in diesem Fall die 3).
Solche sogenannten "trivialen Zykel" werden auch gern mal weggelassen, da in ihnen keine nennenswerten Informationen stecken.
Nun sollst du deine Permutation von oben mit solchen Zykeln schreiben.
Das ganze geht bei dir so los:
$ [mm] \sigma [/mm] = [mm] (A,F,I,B,M)\cdots [/mm] $
Nun nimmst du dir das erste Element, das bisher noch nicht auftaucht ist, also das C, und beginnst damit den nächsten Zykel.
Zum Schluss lässt du die trivialen wenn du möchtest weg.
Hierzu ist vielleicht noch zu sagen, dass du theoretisch deine Zykel in beliebiger Reihenfolge schreiben könntest.
Dass man immer mit dem "kleinsten" Element das noch nicht vorkam den nächsten beginnt ist nur eine Konvention damit es leichter zu lesen und zu vergleichen ist, aber aus mathematischer Sicht kein Muss.
Mit meinem Beispiel von oben wäre also:
[mm] $\phi [/mm] = (1,2,4,5)(3) = (3)(1,2,4,5) = (1,2,4,5) = (2,4,5,1) = (5,1,2,4)(3) = [mm] \cdots$
[/mm]
Es ist halt für jemanden, der deine Bearbeitung liest, viel leichter zu verstehen, wenn dort [mm] $\phi [/mm] = (1,2,4,5)$ steht; aber falsch sind die anderen Arten auch nicht.
Wenn du deine Zykel hast dürfte auch klar sein was mit dem Bild gemeint ist.
lg
Schadow
|
|
|
| |
|
danke für die erklärung....dann müsste ja für mein Beispiel mit Zyklenschreibweise ja gelten:
[mm] \phi [/mm] = (ABCDEFGHIJKLMNOP)(J)
[mm] \sigma= [/mm] (AFIBM)(COG)(DK)(EH)
Das ist nun das Produkt disjunkter Zyklen?
Und wie geht es jetzt weiter? Was mit Bild gemeint ist hab ich immer noch nicht verstanden :( bzw was ich für ein Bild wie erstellen muss.
MfG
Mathegirl
|
|
|
| |
|
> danke für die erklärung....dann müsste ja für mein
> Beispiel mit Zyklenschreibweise ja gelten:
>
> [mm]\phi[/mm] = (ABCDEFGHIJKLMNOP)(J)
>
> [mm]\sigma=[/mm] (AFIBM)(COG)(DK)(EH)
>
> Das ist nun das Produkt disjunkter Zyklen?
Da fehlen noch ein paar.^^
Da dort nur 12 Stück stehen heißt das, dass 4 Stück auf sich selbst abgebildet werden müssen.
Es wird aber nur eines (das J) auf sich selbst abgebildet, somit fehlt noch ein wenig was.
> Und wie geht es jetzt weiter? Was mit Bild gemeint ist hab
> ich immer noch nicht verstanden :( bzw was ich für ein
> Bild wie erstellen muss.
Du hast da ja jetzt die Zykel.
Mal sie dir einfach hin, also etwas in der Form:
A -> F -> I -> ...
Und wenn du es hübsch haben willst mach einen schönen Kreis draus.
In deinem Fall oben hättest du also vier solche Kreise; und du wirst noch ein paar mehr haben wenn du ganz fertig bist.
> Mathegirl
lg
Schadow
|
|
|
| |
|
(AFIBM)(COG)(DK)(EH)(JJ)(LPN) ich weiß nun nicht mit welchem Buchstaben ich weiter machen muss! das ist wohl ehr das Problem!
Ich bin wohl etwas begriffsstutzig was dieses Thema betrifft ;)
MfG
Mathegirl
|
|
|
| |
|
> (AFIBM)(COG)(DK)(EH)(JJ)(LPN) ich weiß nun nicht mit
> welchem Buchstaben ich weiter machen muss! das ist wohl ehr
> das Problem!
>
> Ich bin wohl etwas begriffsstutzig was dieses Thema
> betrifft ;)
Hmm, das J hast du doppelt, da kann eines von weg.
Wenn du das wegnimmst dann hast du hier genau 16 Elemente in deinen Zykeln stehen.
So lange da nicht noch eins doppelt drinn steht bist du somit fertig, denn du hast ja genau 16 Elemente für die Permutation.
lg
Schadow
|
|
|
| |
|
Die 1ten 2 Zyklen sind (AFIBM)(COG); die Schreibweise bedeutet
A->F->I->B->M->und wieder A - daher Zyklus, und es sind weitere 4 Zyklen.
|
|
|
|
