Wersja z 20:55, 11 lip 2014 edytuj Tufor (dyskusja \| edycje) Redaktorzy 27 471 edycji m Wycofano edycje użytkownika 193.19.165.91 (dyskusja). Autor przywróconej wersji to Addbot. ← poprzednia edycja		Wersja z 02:32, 24 lut 2015 edytuj anuluj edycję Chrumps (dyskusja \| edycje) Redaktorzy, Administratorzy 50 057 edycji poprawa linków do przek., WP:SK, drobne redakcyjne i techniczne następna edycja →
Linia 1: {{Teoria grafów}} '''Graf hamiltonowski''' to [[graf (matematyka)\|graf]] rozważany w teorii grafów zawierający [[droga (teoria grafów)\|ścieżkę]] (drogę) przechodzącą przez każdy [[~~Wierzchołek~~graf ~~grafu~~(matematyka)\|wierzchołek]] '''dokładnie jeden raz''' zwaną [[Ścieżka Hamiltona\|ścieżką Hamiltona]]. W szczególności grafem hamiltonowskim jest graf zawierający [[cykl Hamiltona]], tj. zamkniętą ścieżkę Hamiltona. W niektórych źródłach graf zawierający tylko ścieżkę Hamiltona nazywany jest grafem ''półhamiltonowskim''.▼ [[~~Grafika~~Plik:Hamilton path.svg\|thumb\|left\|[[Graf skierowany]] posiadający [[Ścieżka Hamiltona\|ścieżkę Hamiltona]]. Niebieskie kropki to [[~~Wierzchołek~~graf ~~grafu~~(matematyka)\|wierzchołki]] grafu, strzałki to krawędzie grafu, a ścieżkę hamiltona oznaczono kolorem czerwonym.]]▼ ▲'''Graf hamiltonowski''' to [[graf (matematyka)\|graf]] rozważany w teorii grafów zawierający [[droga (teoria grafów)\|ścieżkę]] (drogę) przechodzącą przez każdy [[Wierzchołek grafu\|wierzchołek]] '''dokładnie jeden raz''' zwaną [[Ścieżka Hamiltona\|ścieżką Hamiltona]]. W szczególności grafem hamiltonowskim jest graf zawierający [[cykl Hamiltona]], tj. zamkniętą ścieżkę Hamiltona. W niektórych źródłach graf zawierający tylko ścieżkę Hamiltona nazywany jest grafem ''półhamiltonowskim''. Aby lepiej zrozumieć właściwości grafu hamiltonowskiego można się posłużyć przykładem komiwojażera, który chce odwiedzić wszystkich swoich klientów, ale tylko raz ([[problem komiwojażera]]). Klienci, to wierzchołki grafu, a drogi między nimi są jego [[krawędź grafu\|krawędziami]]. Jeżeli graf jest hamiltonowski, to znaczy, że komiwojażer może obejść wszystkich klientów, bez mijania drugi raz żadnego z nich i wrócić do punktu wyjścia. ▼ == Przykłady grafów ~~Hamiltonowskich~~hamiltonowskich ==▼ ▲[[Grafika:Hamilton path.svg\|thumb\|left\|[[Graf skierowany]] posiadający [[Ścieżka Hamiltona\|ścieżkę Hamiltona]]. Niebieskie kropki to [[Wierzchołek grafu\|wierzchołki]] grafu, strzałki to krawędzie grafu, a ścieżkę hamiltona oznaczono kolorem czerwonym.]] [[~~Grafika~~Plik:Hamiltonian graph example.svg\|thumb\|left\|Przykładowy cykl Hamiltona w grafie [[dwunastościan foremny\|dwunastościanu foremnego]].]]▼ ▲Aby lepiej zrozumieć właściwości grafu hamiltonowskiego można się posłużyć przykładem komiwojażera, który chce odwiedzić wszystkich swoich klientów, ale tylko raz ([[problem komiwojażera]]). Klienci, to wierzchołki grafu, a drogi między nimi są jego [[krawędź grafu\|krawędziami]]. Jeżeli graf jest hamiltonowski, to znaczy, że komiwojażer może obejść wszystkich klientów, bez mijania drugi raz żadnego z nich i wrócić do punktu wyjścia. ▲== Przykłady grafów Hamiltonowskich == ▲[[Grafika:Hamiltonian graph example.svg\|thumb\|left\|Przykładowy cykl Hamiltona w grafie [[dwunastościan foremny\|dwunastościanu foremnego]].]] Grafem hamiltonowskim w szczególności jest każdy graf: * [[Graf pełny\|pełny]], posiadający przynajmniej ''3'' wierzchołki, * opisujący [[wielościan foremny]]. == Złożoność czasowa == Nie są znane [[algorytm]]y umożliwiające jednoznaczne rozwiązanie problemu znajdowania najkrótszej możliwej ścieżki Hamiltona w [[Złożoność obliczeniowa\|czasie wielomianowym]] i działające dla wszystkich możliwych grafów (problem ścieżki Hamiltona jest [[Problem NP-zupełny\|NP zupełny]]). W praktyce najczęściej stosowane są [[algorytm genetyczny\|algorytmy genetyczne]], często wykorzystywane w połączeniu z [[heurystyka (informatyka)\|heurystycznymi]] (np. heurystyka najbliższego sąsiada). Są to jednak metody dające w większości jedynie rozwiązania bliskie optymalnemu. Znalezienie najlepszego, możliwego rozwiązania, zależy głównie od ~~ilości~~liczby punktów oraz czasem ''szczęścia'' na skutek generacji populacji początkowej, krzyżowania oraz [[mutacja\|mutacji]] w algorytmach genetycznych. Problem złożoności czasowej znajdowania rozwiązania problemu grafu ~~Hamiltonowskiego~~hamiltonowskiego wiąże się z brakiem twierdzenia takiego jak [[cykl Eulera\|twierdzenie Eulera]] dla [[graf eulerowski\|grafów Eulera]]. Owo twierdzenie pozwala w czasie liniowym (tj. zależnym liniowo od, w tym przypadku, liczby wierzchołków) znaleźć odpowiedź na pytanie, czy graf jest eulerowski. W przypadku grafów Hamiltona twierdzenie takie prawdopodobnie nie istnieje. Znalezienie algorytmu znajdowania drogi Hamiltona w czasie wielomianowym jest [[Graal\|~~"Świętym~~„Świętym ~~Graalem"~~Graalem”]] informatyki, i chociaż powstały już setki publikacji opisujących rzekomo taki właśnie algorytm, problem jest nadal otwarty. Według znakomitej części specjalistów taki algorytm nie istnieje ("gdyż, zgodnie z rachunkiem prawdopodobieństwa, ktoś już by taki algorytm znalazł"), jednak do czasu udowodnienia, że takowy algorytm nie istnieje, lub udowodnienia, że taki dowód nie może zostać przeprowadzony, należy wstrzymać się z kategorycznymi osądami. [[~~Grafika~~Plik:Mycielski graph k4 hamiltonian path.svg\|thumb~~\|right~~\|Przykładowy cykl hamiltonowski w [[graf Mycielskiego\|grafie Mycielskiego]].]] == Oznaczenia == Niech <math>\! G</math> oznacza graf, <math>\! V(G)</math> zbiór jego wierzchołków, <math>\! E(G)</math> zbiór krawędzi, <math>\|A\|</math> [[moc zbioru]], <math>\! v_i</math> pojedynczy (w tym przypadku ''i-ty'') wierzchołek grafu a <math>\! deg(v)</math> stopień wierzchołka (liczbę kończących się w nim krawędzi). Tradycyjnie oznacza się <math>\|V(G)\|\ =\ n</math> oraz <math>\|E(G)\|\ =\ m</math>, zapis <math>\{v,u\}</math> będący zbiorem dwuelemtowym wierzchołków, używa się do oznaczenia krawędzi między ''v'' i ''u'' (w przypadku [[graf skierowany\|digrafów]] jest to para uporządkowana, gdyż liczy się kolejność oznaczająca kierunek krawędzi). == Indeksowanie wierzchołków == Ścieżka/cykl Hamiltona może być jednoznacznie wyznaczona przez indeksowanie wierzchołków -– tj. nadanie im indeksów, powiedzmy <math>v_0,v_1,\ldots ,v_n</math>, takich, że istnieje ścieżka Hamiltona przechodząca w takiej właśnie kolejności przez wierzchołki grafu.▼ Gdy znane jest indeksowanie <math>v_0,v_1,\ldots ,v_n</math> wyznaczające ścieżkę Hamiltona, to znalezienie (lub potwierdzenie nieistnienia) cyklu Hamiltona jest trywialne i sprowadza się do sprawdzenia, czy istnieje krawędź <math>\{v_n,v_0\}</math> -– zajmuje to, w zależności od [[Reprezentacja grafu\|sposobu reprezentacji grafu]], czas stały lub <math>\! O(n)</math>, gdzie ''n'' to liczba wierzchołków danego grafu (zobacz: [[Asymptotyczne tempo wzrostu\|Notacja dużego O]]).▼ ▲Ścieżka/cykl Hamiltona może być jednoznacznie wyznaczona przez indeksowanie wierzchołków - tj. nadanie im indeksów, powiedzmy <math>v_0,v_1,\ldots ,v_n</math>, takich, że istnieje ścieżka Hamiltona przechodząca w takiej właśnie kolejności przez wierzchołki grafu. ▲Gdy znane jest indeksowanie <math>v_0,v_1,\ldots ,v_n</math> wyznaczające ścieżkę Hamiltona, to znalezienie (lub potwierdzenie nieistnienia) cyklu Hamiltona jest trywialne i sprowadza się do sprawdzenia, czy istnieje krawędź <math>\{v_n,v_0\}</math> - zajmuje to, w zależności od [[Reprezentacja grafu\|sposobu reprezentacji grafu]], czas stały lub <math>\! O(n)</math>, gdzie ''n'' to liczba wierzchołków danego grafu (zobacz: [[Asymptotyczne tempo wzrostu\|Notacja dużego O]]). == Warunek konieczny == Jeżeli graf ''G'' jest hamiltonowski to dla każdego niepustego zbioru <math>\! V'</math> zbioru wierzchołków ''V(G)'' zachodzi :: <math>\! \omega (V(G)\ -\ V')\le \|V'\|</math>▼ ▲::<math>\! \omega (V(G)\ -\ V')\le \|V'\|</math> gdzie <math>\! \omega (G)</math> oznacza liczbę [[Spójna składowa grafu\|spójnych składowych grafu]] ''G''. == Warunki wystarczające == Istnieją jednak twierdzenia pozwalające na podstawie cech grafu, dostępnych w czasie liniowym, stwierdzić jednoznacznie, że dany graf jest hamiltonowski. Należy pamiętać, że jest to [[Implikacja logiczna\|implikacja]] jednostronna -– istnieje nieskończenie wiele grafów hamiltonowskich, które nie mają poniższych cech.▼ Twierdzenia te są matematycznym obrazem dość naturalnej obserwacji dotyczącej własności grafów -– jest logiczne, że im więcej jest krawędzi w grafie, tym ~~"większe~~„większe są ~~szanse"~~szanse” na znalezienie wśród nich drogi Hamiltona. W skrócie (i nieformalnie), poniższe twierdzenia mówią, że graf jest hamiltonowski, jeżeli tylko ma on odpowiednio dużo krawędzi w stosunku do ~~ilości~~liczby wierzchołków.▼ ▲Istnieją jednak twierdzenia pozwalające na podstawie cech grafu, dostępnych w czasie liniowym, stwierdzić jednoznacznie, że dany graf jest hamiltonowski. Należy pamiętać, że jest to [[Implikacja logiczna\|implikacja]] jednostronna - istnieje nieskończenie wiele grafów hamiltonowskich, które nie mają poniższych cech. ▲Twierdzenia te są matematycznym obrazem dość naturalnej obserwacji dotyczącej własności grafów - jest logiczne, że im więcej jest krawędzi w grafie, tym "większe są szanse" na znalezienie wśród nich drogi Hamiltona. W skrócie (i nieformalnie), poniższe twierdzenia mówią, że graf jest hamiltonowski, jeżeli tylko ma on odpowiednio dużo krawędzi w stosunku do ilości wierzchołków. Najważniejsze z nich to: * [[Twierdzenie Diraca]] ([[1952]]), * [[Twierdzenie ~~Ore~~Orego]] ([[1961]]), * [[Twierdzenie o liczbie krawędzi (graf hamiltonowski)\|Twierdzenie o liczbie krawędzi]], * [[Twierdzenie Bondy'ego-Chvátala]], * [[Graf dwudzielny#Warunki wystarczające dla grafu hamiltonowskiego\|Twierdzenie dla grafu dwudzielnego]]. == Szczególne przypadki == Linia 55 ⟶ 49: == Algorytmy znajdowania ścieżki Hamiltona == * [[Algorytm Robertsa-Floresa]] * [[Algorytm optymalizacji koloni mrówek (ant colony optimisation)]] Linia 64 ⟶ 57: * [[Robin Wilson]] – "Wprowadzenie do teorii grafów", [[Wydawnictwo Naukowe PWN\|PWN]], [[2004]] * Witold Lipski – "Kombinatoryka dla programistów", [[Wydawnictwa Naukowo-Techniczne\|WNT]], [[2004]] * Karolina Sołtys -– "[http://mimuw.edu.pl/delta/artykuly/delta0508/mrowki.pdf Mrówki, czyli piękno metaheurystyk]" == Zobacz też == * [[problem komiwojażera]] * [[cykl Hamiltona]] * [[cykl Eulera]] * [[Graf eulerowski]] * [[łańcuch Eulera]] [[Kategoria:Teoria grafów]]

Graf hamiltonowski: Różnice pomiędzy wersjami