Graf hamiltonowski
graf ze ścieżką lub cyklem Hamiltona / Z Wikipedii, wolnej encyclopedia
Drogi AI, mówmy krótko, odpowiadając po prostu na te kluczowe pytania:
Czy możesz wymienić najważniejsze fakty i statystyki dotyczące Graf hamiltonowski?
Podsumuj ten artykuł dla 10-latka
POKAŻ WSZYSTKIE PYTANIA
Graf hamiltonowski – rodzaj grafu rozważany w teorii grafów i definiowany dwojako, w dwóch nieco innych znaczeniach:
- szerszym: dowolny graf zawierający ścieżkę (drogę) przechodzącą przez każdy wierzchołek dokładnie jeden raz zwaną ścieżką Hamiltona;
- węższym: grafem hamiltonowskim jest graf zawierający cykl Hamiltona, tj. zamkniętą ścieżkę Hamiltona[1].
W niektórych źródłach graf zawierający tylko ścieżkę Hamiltona nazywany jest grafem półhamiltonowskim[2].
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ę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.