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: 5781
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: 5781
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: 1086
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 
 Sprawdzanie obecności cyklu Eulera i Hamiltona w grafie  AlAmilar  3
 Teoria grafów. Obwód i droga Eulera  marcin00412  0
 Cykl hamiltona  gardner  5
 Łączenie punktów + najkrótsza droga  Dasio11  48
 Droga - definicja  sandra-91  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl