Cykl Hamiltona

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.