szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 30 sty 2017, o 17:05 
Użytkownik

Posty: 1
Lokalizacja: Polska
Próbowałam własnymi siłami przetłumaczyć dowód poniższego twierdzenia (zgodnie z artykułem V. Chvatal: \textit{On Hamilton's Ideals}, Journal of Combinatorial Theory, Series B Volume 12, 1972, Pages 163-168). Jednak zdaję sobie sprawę, że zapewne sporo trzeba w nim poprawić. Co powinnam zmienić? W jaki sposób?
Bardzo proszę o pomoc.

Twierdzenie:
Niech G będzie grafem o n wierzchołkach o ciągu stopni d_1 \le d_2 \le \ldots \le d_n takim, że jeżeli:
d_k \le k < \frac{n}{2} to d_{n-k} \geq n-k
Wtedy G jest hamiltonowski.

Dowód:
Niech G będzie grafem niehamiltonowskim, którego ciąg stopni spełnia powyższy warunek. Wtedy G zawiera się w maksymalnym niehamiltonowskim grafie G^{*} (tj. takim, że dodanie każdej nowej krawędzi spowoduje powstanie cyklu Hamiltona). Ciąg stopni grafu G^{*} również spełnia powyższy warunek. Niech u i v będą niesąsiadującymi wierzchołkami grafu G^{*} takimi, że d(u)+d(v) jest tak duża jak to możliwe oraz d(u) \le d(v). Jeśli G^{*} jest maksymalnie niehamiltonowski, to istnieje ścieżka Hamiltona złożona z wierzchołków u= u_1, u_2, \ldots, u_n= v. Definiujemy zbiory S oraz T następująco:
S=\{i: \{u, u_{i+1}\} \textnormal{ jest krawędzią } G^{*} \}
T=\{i: \{u_i, v\} \textnormal{ jest krawędzią } G^{*} \}
Nie jest prawdą, że j \in S \cap T, bo wtedy
u_j, u_{j-1}, \ldots, u_1, u_{j+1}, u_{j+2}, \ldots, u_n
wierzchołków G^* dałoby cykl Hamiltona. Tak więc dostajemy, że S \cap T = \emptyset i również S \cup T \subset \{1,2,...,n-1\}. W związku z tym d(u) + d(v) = |S| + |T| < n i d(u) < \frac{n}{2}. Skoro S \cap T = \emptyset, to u_j gdzie j \in S nie sąsiaduje z v, a maksymalność d(u) + d(v) implikuje d(u_j) \le d(u). A zatem, istnieje co najmniej |S| = d(u) wierzchołków, których stopnie nie przekraczają d(u). Podstawiając k = d(u), dostajemy d_k \le k < \frac{n}{2} i dlatego na podstawie warunku z powyższego twierdzenia otrzymujemy, że d_{n-k} \geq n-k. Ostatnia nierówność oznacza, że istnieje co najmniej k+1 wierzchołków, których stopnie są równe co najmniej n-k. Wierzchołek u o stopniu równym k nie sąsiaduje z żadnym z nich. Tak więc, istnieje wierzchołek w taki, że d(w) \geq n-k, który nie sąsiaduje z u. Ale wtedy d(u) + d(w) \geq n > d(u) + d(v), co jest sprzeczne z maksymalnością d(u) + d(v). To kończy pierwszą część dowodu.\\
Aby dokończyć dowód, zauważmy, że każdy ciąg stopni wierzchołków, który nie spełnia warunku z powyższego twierdzenia jest zmajoryzowany przez ciąg
k, k, \ldots, k, n-k-1, n-k-1, \ldots, n-k-1, n-1, n-1, \ldots, n-1
gdzie k jest na tych samych warunkach co k, n-2k tak samo jak n-k-1, a k jak n-1. Ostatni ciąg jest ciągiem stopni wierzchołków grafu G(k, k, n-2k), którego wierzchołki tworzą zbiór X \cup Y \cup Z, gdzie X, Y, Z są parami rozłączne z |X| = k, |Y| = k, |Z| = n-2k, a x jest krawędzią C wtedy i tylko wtedy, gdy co najmniej jeden z wierzchołków należy do Y lub oba należą do Z. Tak więc G(k, k, n-2k) jest niehamiltonowski, co kończy dowód.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Dowód kombinatoryczny - zadanie 8  pg2464  2
 Dowód - wskazówka  tomek1172  4
 izomorfizm grafów - zadanie 4  tukanik  9
 matematyka dyskretna - graf eulerowski dowod  tomasini  7
 Dowód słuszności wzoru  lukasz93a  7
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl