Wpisany przez Michał Knasiecki,
16 sierpnia 2005 19:38
Graf posiada cykl Hamiltona, jeśli istnieje w nim cykl (droga, która zaczyna się i kończy w tym samym wierzchołku), który zawiera każdy wierzchołek dokładnie raz. Algorytm znajdujący cykl Hamiltona w grafie jest znacznie bardziej skomplikowany, niż w przypadku cyklu
Eulera. Nie istnieje żaden algorytm rozwiązujący ten problem w czasie wielomianowym, algorytm należy więc do klasy NP-zupełnych.
Przykładowy cykl: 1,2,6,5,3,4,1 lub 1,5,6,2,4,3,1
Przykładowy cykl: 1,2,6,5,3,4,1 lub 1,5,6,2,4,3,1
Implementacje
| Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
Poprawiony: 29 sierpnia 2012 20:43
Komentarze
+9
#
Krzysiek K
2012-06-15 08:34
"Nie istnieje żaden algorytm rozwiązujący ten problem w czasie wielomianowym, algorytm należy więc do klasy NP-zupełnych". Nie jest to prawdą, ponieważ nie wiemy czy P=NP. To, że jest NP-zupełny wynika z tego, iż możemy znaleźć świadka dla tego problemu obliczalnego w czasie wykładniczym, oraz że ten problem redukuje się do dowolnego problemu NP-zupełnego ;)
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz