szukanie zaawansowane
 [ Posty: 7 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Droga Hamiltona
PostNapisane: 12 sty 2014, o 19:43 
Użytkownik

Posty: 15
Lokalizacja: POL
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
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
 Tytuł: Droga Hamiltona
PostNapisane: 12 sty 2014, o 20:14 
Gość Specjalny

Posty: 5715
Lokalizacja: Toruń
Prosta indukcja po liczbie wierzchołków.
Góra
Mężczyzna Offline
 Tytuł: Droga Hamiltona
PostNapisane: 12 sty 2014, o 20:22 
Użytkownik

Posty: 15
Lokalizacja: POL
Mało mi to mówi :)

Moge liczyc na rozwiazanie?:)
Góra
Mężczyzna Offline
 Tytuł: Droga Hamiltona
PostNapisane: 12 sty 2014, o 20:24 
Gość Specjalny

Posty: 5715
Lokalizacja: Toruń
Na gotowca? Nie licz - skorzystaj ze wskazówki.
Góra
Mężczyzna Offline
 Tytuł: Droga Hamiltona
PostNapisane: 18 sie 2016, o 17:57 
Użytkownik

Posty: 1427
Lokalizacja: Warszawa
Też jestem zainteresowany tym zadaniem. Mam problem z krokiem indukcyjnym. Bierzemy skierowany graf K_{n+1}. Wiadomo, że w każdej n-elementowej klice istnieje droga Hamiltona. Chciałoby się teraz wyróżnić pewien wierzchołek - 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 - w_1,\,w_2 - ma tę własność, że do wyjściowego grafu należy krawędź w_1v i vw_2. Nie widzę, jak to uzyskać.

-- 18 sierpnia 2016, 17:55 --

Ewentualnie można by jeszcze próbować wybrać wierzchołek 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 v, albo zaczynała takim, do którego wchodzi v. Wtedy dałoby się przedłużyć ścieżkę na początku lub na końcu o v. Ale tutaj też nie wiem, czy na pewno takie v istnieje.
Góra
Mężczyzna Offline
 Tytuł: Droga Hamiltona
PostNapisane: 18 sie 2016, o 20:55 
Użytkownik

Posty: 1074
Lokalizacja: Lublin/Warszawa
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ę 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 v, a z 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 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.
Góra
Mężczyzna Offline
 Tytuł: Droga Hamiltona
PostNapisane: 19 sie 2016, o 19:15 
Użytkownik

Posty: 1427
Lokalizacja: Warszawa
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.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 7 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ilość cykli hamiltona w grafie kostki Q4 ?  luki1423  1
 Cykl Hamiltona w grafie Petersena  Sage!  1
 Wykazać, że w grafie Petersena istnieje droga Hamiltona  stonek89  2
 [Teoria grafów] Poprawność dowodu istnienia cyklu Hamiltona  kapsl0k  0
 Najkrótsza droga w grafie  wojciech007  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl