Droga Hamiltona

[THCFalcon]

Witam, mam problem z zadaniem:

Udowodnij, że każdy skończony, zorientowany graf, w którym dowolne dwa wierzchołki są połączone dokładnie jedną krawędzią w jednym z dwóch możliwych kierunków posiada drogę Hamiltona.

Pozdrawiam

[bartek118]

Prosta indukcja po liczbie wierzchołków.

[THCFalcon]

Mało mi to mówi

Moge liczyc na rozwiazanie?:)

[bartek118]

Na gotowca? Nie licz - skorzystaj ze wskazówki.

[Majeskas]

Też jestem zainteresowany tym zadaniem. Mam problem z krokiem indukcyjnym. Bierzemy skierowany graf \(\displaystyle{ K_{n+1}}\). Wiadomo, że w każdej \(\displaystyle{ n}\)-elementowej klice istnieje droga Hamiltona. Chciałoby się teraz wyróżnić pewien wierzchołek - \(\displaystyle{ v}\), wziąć drogę Hamiltona w klice i dołączyć ten wierzchołek. Tylko trzeba by sobie jakoś zagwarantować, że pewna para wierzchołków na tej drodze Hamiltona - \(\displaystyle{ w_1,\,w_2}\) - ma tę własność, że do wyjściowego grafu należy krawędź \(\displaystyle{ w_1v}\) i \(\displaystyle{ vw_2}\). Nie widzę, jak to uzyskać.-- 18 sierpnia 2016, 17:55 --Ewentualnie można by jeszcze próbować wybrać wierzchołek \(\displaystyle{ v}\) w taki sposób, żeby po przejściu do kliki droga Hamiltona albo kończyła się wierzchołkiem, który ma wejście do \(\displaystyle{ v}\), albo zaczynała takim, do którego wchodzi \(\displaystyle{ v}\). Wtedy dałoby się przedłużyć ścieżkę na początku lub na końcu o \(\displaystyle{ v}\). Ale tutaj też nie wiem, czy na pewno takie \(\displaystyle{ v}\) istnieje.

[Mruczek]

To zadanie jest bardzo znane. Poszukaj w necie pod hasłem "turniej zawiera drogę Hamiltona".

W zasadzie już prawie masz rozwiązanie - jeżeli ta droga z założenia indukcyjnego kończy lub zaczyna się \(\displaystyle{ v}\) to koniec - przedłużyliśmy drogę. Załóżmy, że jednak tak nie jest, tzn z początku tej ścieżki krawędź wychodzi do \(\displaystyle{ v}\), a z \(\displaystyle{ v}\) wchodzi do końcowego wierzchołka ścieżki. No to rozpatrujemy kolejne wierzchołki tej ścieżki od początku do końca. Skoro na początku jakaś krawędź wchodziła do \(\displaystyle{ v}\), a na końcu wychodziła, to gdzieś w środku tej ścieżki takie dwa rodzaje krawędzi muszą się spotkać... dokończ sam.

[Majeskas]

Dziękuję za naprowadzenie mnie na odpowiedni dział teorii grafów. Ten dowód jest przeprowadzony w książce Wilsona, w rozdziale o turniejach. Rzeczywiście, byłem już blisko końca. Zabrakło mi drobnego pomysłu, jak zbudować drogę w tym najbardziej pesymistycznym przypadku.