Witam ponownie!
Dziś zajmiemy się cyklem Hamiltona. Jest to zagadnienie podobne do cyklu Eulera z ta różnicą, że tym razem musimy przejść raz nie przez wszystkie krawędzie, a przez wszystkie wierzchołki.

Na poniższym obrazie, przykład drogi Hamiltona w grafie:

Cykl Hamiltona wiedzie przez poniżej wypisane wierzchołki:
A B H I Q P G F O T S R K J C D L M N E A

Z cyklem Hamiltona jest związane kilka ciekawych twierdzeń. Oto one:

Twierdzenie Orego
-Jeżeli w grafie prostym G o n wierzchołkach i n>2 zachodzi następująca nierówność:

\displaystyle{deg(v)+deg(u) \ge n-1}

dla każdej pary niepołączonych bezpośrednio krawędzią wierzchołków u i v (tj. takich, że \{v,u\}\neq E to graf G posiada drogę Hamiltona.

Twierdzenie o liczbie krawędzi-Jeśli graf prosty o n wierzchołkach ma co najmniej m krawędzi, gdzie:

m=\frac{1}{2}\cdot(n-1)(n-2)+2 to jest hamiltonowski.

Algorytm najbliższego sąsiada
– algorytm zachłanny służący do rozwiązywania problemu komiwojażera polegający na odwiedzaniu, począwszy od wybranego wierzchołka, wierzchołka znajdującego się najbliżej wierzchołka ostatnio odwiedzonego. Dla grafu pełnego o n wierzchołkach złożoność czasowa algorytmu wynosi O(n^2).

Teraz kilka wyjaśnień:

algorytm zachłanny-algorytm, który w celu wyznaczenia rozwiązania w każdym kroku dokonuje zachłannego, tj. najlepiej rokującego w danym momencie wyboru rozwiązania częściowego

graf pełny-jest grafem prostym, w którym dla każdej pary węzłów istnieje krawędź je łącząca.

Przechodzimy teraz do problemu komiwojażera, jednego z ważniejszych zagadnień teorii grafów.

Problem komiwojażera-
zagadnienie optymalizacyjne, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym
Problem komiwojażera(symetryczny problem komiwojażera) wiąże się z dużą ilością danych do przetworzenia, a więc dla n miast liczba kombinacji wynosi \frac{(n-1)!}{2} a więc dla 20 miast wynik wynosi \frac{19!}{2} \sim 6\times 10^{16}.

Kolejnym twierdzeniem, jest twierdzenie Diraca– Jeżeli G jest grafem zwyczajnym o n\ge 3 wierzchołkach oraz dla każdego wierzchołka v \in V
d(v)\ge \frac{n}{2} to graf G jest hamiltonowski.

Na dziś tyle, jeszcze wrócimy do teorii grafów.
Dzięki!

1 KOMENTARZ

ZOSTAW ODPOWIEDŹ

Please enter your comment!
Please enter your name here