Graphentheorie:vollständige Induktion?

...komplette Frage anzeigen

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

Antwort bewerten Vielen Dank für Deine Bewertung

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.

Antwort bewerten Vielen Dank für Deine Bewertung
gf20109 16.01.2016, 11:17

mhhh...ganz bekomme ich es nicht zsm :/

0

Was möchtest Du wissen?