Dowód twierdzenia - cykl Hamiltona

[angelene]

Cześć! Byłabym wdzięczna za pomoc przy dowodzie tego twierdzenia:

Niech B będzie zbalansowanym grafem dwudzielnym rzędu \(\displaystyle{ 2n}\).
\(\displaystyle{ B=(X \cup Y,E)}\), \(\displaystyle{ V=X \cup Y, |X|=|Y|, \\
X=\left\{ x_1,...,x_n\right\}, \\
Y=\left\{ y_1,...,y_n\right\} . }\)
Niech \(\displaystyle{ D_i=\left\{ x_jy_k: i \equiv j-k\pmod n \right\} }\) .
Wtedy \(\displaystyle{ D_s \cup D_t}\) tworzą cykl Hamiltona w \(\displaystyle{ B}\) jeżeli \(\displaystyle{ gcd(|t-s|,n)=1}\), gdzie \(\displaystyle{ s,t \in [0,n-1]}\).

[arek1357]

Pokaże Ci to w ten sposób, tak w skrócie , że jeśli masz wierzchołki z np lewej sekcji:

\(\displaystyle{ x_{1}, x_{1(t-s)+1},x_{2(t-s)+1},x_{3(t-s)+1},...}\)

To zauważ, że dzięki temu, że:

\(\displaystyle{ (|t-s|,n)=1}\)

to ta sekwencja wygeneruje Ci wszystkie wierzchołki tworząc cykl Hamiltona, właśnie ze względu na względną pierwszość...

Porysuj sobie dla.:\(\displaystyle{ n=3,4,5...}\)

To dojdziesz do podobnych spostrzeżeń...