Signum, Zykelzerlegung < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich hab lange daran rumgerätselt. abe rich brauch jetzt anhand einer Beispielsaufgabe dringend Hilfe dinge wie Zykelzerlegung und Signum zu verstehen.
[mm] \pmat{ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 10 & 3 & 4 & 5 & 6 & 9 & 8 & 7 & 1 & 2}
[/mm]
würd einer so lieb sein und mir anhand dieser aufgabe mal nachvollziehbar erklären wie er zur Zykelzerlegung kommt? Wenn dabei auch die Fehlständekurz erklärt werden könnten wär das wunderbar.
wir hatten irgendwo zu den fehlständen ne Formel.
sgm [mm] \sigma [/mm] = [mm] \produkt_{i
ich weiß aber nicht wie das hilft. bitte helft mir
|
|
| |
|
Halli Hallo!
> Hallo,
> ich hab lange daran rumgerätselt. abe rich brauch jetzt
> anhand einer Beispielsaufgabe dringend Hilfe dinge wie
> Zykelzerlegung und Signum zu verstehen.
>
> [mm]\pmat{ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 10 & 3 & 4 & 5 & 6 & 9 & 8 & 7 & 1 & 2}
[/mm]
>
>
> würd einer so lieb sein und mir anhand dieser aufgabe mal
> nachvollziehbar erklären wie er zur Zykelzerlegung kommt?
> Wenn dabei auch die Fehlständekurz erklärt werden könnten
> wär das wunderbar.
>
> wir hatten irgendwo zu den fehlständen ne Formel.
>
> sgm [mm]\sigma[/mm] = [mm]\produkt_{i
>
>
> ich weiß aber nicht wie das hilft. bitte helft mir
Die Formel in meinem Skript hab ich auch erst nicht verstanden, es ist aber wirklich sehr einfach, und wenn man ersteinmal das Prinzip verstanden hat, so versteht man auf einmal auch die Formel 
Aber zuerst zur Zykelzerlegung!
Du beginnst ersteinmal mit der 1!
Nun schaust du nachm auf welche Zahl die 1 abgebildet wird, und du siehst, die 10 (direkt unter der 1)
Nun gehen wir zur 10 und sehen dass diese auf die 2 abgebildet wird.
Die 2 wiederum wird abgebildet auf die 3.
die 3 auf die 4.
die 4 auf die 5.
die 5 auf die 6.
die 6 auf die 9.
und die 9 nun wieder auf die 1.
Nun sind wir an dem Punkt angelangt, an dem es sich wiederholt! Also ist der erste Zykel abgeschlossen!
Jetzt schauen wir, welche Zahlen wir noch nicht benutzt haben!
Wir haben die 1,2,3,4,5,6 aber die 7 nicht!
Also:
die 7 wird abgebildet auf die 8:
die 8 auf die 7.
Auch dieser zykel ist somit abgeschlossen!
9 und 10 waren schon im ersten Zykel, also haben wir alle Elemente in Zykel untergebracht!
Man kann nun also schreiben:
[mm] \pmat{ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 10 & 3 & 4 & 5 & 6 & 9 & 8 & 7 & 1 & 2}=(1,10,2,3,4,5,6,9)(7,8)
[/mm]
Nun zu den Fehlständen!
Hier schaust du dir die Wertepaare an, und schaust ob du sagen kannst, dass weiter vorne stehende Paar kleiner als das nachstehende ist.
Also bei uns beginnen wir mit dem Paar [mm] \vektor{1 \\ 10} [/mm] und vergleichen ihn mit den nachstehenden:
Also [mm] \vektor{1\\10} [/mm] und [mm] \vektor{2\\3} [/mm] : erster Fehlstand, da 1<2, aber 10>3
[mm] \vektor{1\\10} und\vektor{3\\4}: [/mm] nächster Fehlstand
[mm] \vektor{1\\10} und\vektor{4\\5}: [/mm] nächster Fehlstand
[mm] \vektor{1\\10} und\vektor{5\\6}: [/mm] nächster Fehlstand
[mm] \vektor{1\\10} und\vektor{6\\9}: [/mm] nächster Fehlstand
[mm] \vektor{1\\10} und\vektor{7\\8}: [/mm] nächster Fehlstand
[mm] \vektor{1\\10} und\vektor{8\\7}: [/mm] nächster Fehlstand
[mm] \vektor{1\\10} und\vektor{9\\1}: [/mm] nächster Fehlstand
[mm] \vektor{1\\10} und\vektor{10\\2}: [/mm] nächster Fehlstand
jetzt nimmst du dir das zweite Paar vor und vergleichst sie mit den nachfolgenden, also
[mm] \vektor{2\\3} [/mm] und [mm] \vektor{3\\4}: [/mm] kein Fehlstand, da 2<3 und 3<4
[mm] \vektor{2\\3} [/mm] und [mm] \vektor{4\\5}: [/mm] kein Fehlstand, da 2<4 und 3<5
[mm] \vektor{2\\3} [/mm] und [mm] \vektor{5\\6}: [/mm] kein Fehlstand, da 2<5 und 3<6
[mm] \vektor{2\\3} [/mm] und [mm] \vektor{6\\9}: [/mm] kein Fehlstand, da 2<6 und 3<9
[mm] \vektor{2\\3} [/mm] und [mm] \vektor{7\\8}: [/mm] kein Fehlstand, da 2<7 und 3<8
[mm] \vektor{2\\3} [/mm] und [mm] \vektor{8\\7}: [/mm] kein Fehlstand, da 2<8 und 3<7
[mm] \vektor{2\\3} [/mm] und [mm] \vektor{9\\1}: [/mm] nächster Fehlstand
[mm] \vektor{2\\3} [/mm] und [mm] \vektor{10\\2}: [/mm] nächster Fehlstand
und so weiter (das schaffst du nun sicher allein!)
Am Ende schaust du, ob die Anzahl deiner Fehlstände gerade (dann ist [mm] \sigma=1) [/mm] oder ungerade ist (dann ist [mm] \sigma=-1), [/mm] und bist fertig!
ich hoffe ich kkonnte dir ein wenig weiterhelfen!
Liebe Grüße
Ulrike
|
|
|
| |
|
Hallo,
die Zykelzerlegung wurde dir ja bereits recht ausführlich erklärt, das Ermitteln der Fehlstände auch, aber ... ich würde hier auf gar keinen Fall die Fehlstände ermitteln.
Wenn du einen Zykel der Länge k hast, dann ist das Signum davon einfach [mm] $(-1)^{k-1}$. [/mm] So ist zum Beispiel das Signum von $(1, 4, 9, 7) = [mm] (-1)^3 [/mm] = -1$. Wenn du eine Permutation in mehrere Zykel zerlegst, ist ihr Signum gleich dem Produkt der Signa/Signums(?!) der einzelnen Zykel. Ist deutlich weniger fehleranfällig, als erst die einzelnen Fehlstände zu finden...
- Marcel
|
|
|
|
