Graphentheorie:vollständige Induktion?
Hallo! Ich habe paar Probleme bei einer Aufgabe! Ich glaube ich habe die Grundidee verstanden..aber dennoch kann ich mit der Aufgabe nicht so recht umgehen. Sie lautet:
Sei G n der Graph, dessen Knoten die Permutationen der Menge {1, . . . , n} sind, wobei zwei Knoten genau dann adjazent sind, wenn die zwei entsprechenden Permutationen durch den Austausch zweier benachbarter Elemente ineinander überführt werden können. Zeigen Sie mit vollständiger Induktion, dass G n zusammen- hängend ist.
also meine verständnisidee wäre...sei zb 123 die permutation,dann müssen sich die benachbarten 2 zahlen umdrehen. also zb 213 oder 321... diese ,,gedrehten permutationen) sind sozusagen die knoten und zw denen entstehen kannten,wo es zutrifft. die induktion bezieht sich dann auf die länge der permutation... und der schwerpunkt liegt dann wohl beim ,,tauschen" der zahlen.
ich hoffe ich habe es richtig verstanden. nur weiß ich nicht,wie ich die aufgabe lösen soll.
danke im vorraus! gf20109
2 Antworten
Erstmal eine kleine Notation: (a,b) ist eine Funktion, die a und b vertauscht.
Die Aussage ist also, dass zwei Permutationen x und y genau dann eine Kante zueinander haben, wenn eine Permutation (k, k+1) existiert, sodass (k,k+1)(x) = y.
Induktionsanfang: n = 2, es gibt nur die beiden Knoten id und (1,2), also der erste Knoten ist die Permutation die nichts macht, 1;2, und (1,2) ist die Permutation, die 1 und 2 vertauscht, also 2;1.
Zwischen denen gibt es die Kante (1,2), da (1,2)(1,2) = id. Du musst zwischen dem Knoten (1,2) und der Kante (1,2) unterscheiden, ich habe einfach nur die Notation aus der symmetrischen Gruppe übernommen, besser ist wahrscheinlich die Semikolon-Notation, also (1,2)(2;1) = 1;2. Jetzt sollte es klar sein.
Seien alle Knoten für n + 1 gegeben.
Die Menge aller Permutationen, die n+1 festlässt, ist laut Induktionsannahme bereits ein zusammenhängender Graph. Wenn also o eine Permutation ist, dann sind alle Permutationen der Form o(1);o(2);...;o(n);n+1 ein zusammenhängender Graph, mit den Kanten, die aus dem Fall für n bereits bekannt sind.
Sei also o.B.d.A o' eine Permutation, die n+1 nicht festlässt.
z.z: Es gibt einen Weg von o' in einen Knoten, deren Permutation n+1 festlässt.
Laut Annahme ist o' von der Form o'(1);...,o'(n+1), wobei o'(n+1) = k ≤ n.
Man muss also einen Weg finden von o' nach (k,n+1)(o'), da dies die Permutation ist, die k und n+1 vertauscht, damit also n+1 festlässt.
Wir haben aber eine Kante von o' nach (n,n+1)(o'). Von dort aus eine Kante nach (n-1,n)(n,n+1)(o'). Von dort aus eine Kante nach (n,n+1)(n-1,n)(n,n+1)(o'). Wenn wir uns die Vertauschung (n,n+1)(n-1,n)(n,n+1) anschauen und Elemente rumschicken, dann ist das einfach nur (n-1,n+1), das nennt sich Konjugation [Beweis durch langes Anstarren der Gleichung]. Mit demselben Verfahren finden wir einen Weg nach (n-2,n+1)(o'), (n-3,n+1)(o'),...(k,n+1)(o'). Diese letzte Permutation lässt aber nach Definition von k gerade n+1 fest, ist also in der bereits festgestellten Zusammenhangskomponente von n.
Also ist der Graph für n+1 zusammenhängend.
LG
Induktionsanfang: dürfte trivial sein.
Induktionsschluss: Wenn du das neue Element am Ende anfügst, bleibt der Teilgraph zusammenhängend, bei dem das neue Element am Ende bleibt.
Du kannst das neue Element aber an einer beliebigen Stelle einfügen.
Jetzt fehlt noch, diese Permutationen an den obigen Graphen anzuhängen.
