Wymienione tu pojęcia noszą nazwisko Williama Hamiltona, który zaproponował grę polegającą na znalezieniu cyklu wzdłuż krawędzi dwunastościanu foremnego. Problem cykli Hamiltona w grafach wielościanów był jednak badany już rok wcześniej przez , który podał między innymi przykład wielościanu bez cykli Hamiltona. Ze znajdowaniem ścieżek i cykli Hamiltona związany jest także problem skoczka szachowego badany już w IX wieku. Obchodami skoczka interesowali się również w XVIII-wieczni matematycy: Abraham de Moivre oraz Leonhard Euler.
Przykłady Z reguły przyjmuje się, że – graf o jednym wierzchołku jest hamiltonowski. Liczba grafów hamiltonowskich o wierzchołkach jest równa odpowiednio: 1, 0, 1, 3, 8, 48, 383, … . Niektóre klasy grafów mają tę własność, że wszystkie należące do nich grafy są hamiltonowskie:
graf pełny o co najmniej trzech wierzchołkach, pełny graf dwudzielny o co najmniej czterech wierzchołkach, -kostka dla koło dla grafy platońskie (wielościanów foremnych), grafy wielościanów półforemnych.
Każdy graf wielościanu o co najwyżej 10 wierzchołkach jest hamiltonowski. Istnieją 74 niehamiltonowskie grafy wielościanów o 11 wierzchołkach. Spośród nich najmniej krawędzi ma graf Herschela.
Zobacz też cykl Eulera problem komiwojażera
Przypisy
Linki zewnętrzne
Kategoria:Teoria grafów Kategoria:William Rowan Hamilton