Graf hamiltonowski: Różnice pomiędzy wersjami

Ścieżka/cykl Hamiltona może być jednoznacznie wyznaczona przez indeksowanie wierzchołków – tj. nadanie im indeksów, powiedzmy <math>v_0,v_1,\ldotsdots, v_n,</math> takich, że istnieje ścieżka Hamiltona przechodząca w takiej właśnie kolejności przez wierzchołki grafu.

Gdy znane jest indeksowanie <math>v_0,v_1,\ldotsdots, v_n</math> wyznaczające ścieżkę Hamiltona, to znalezienie (lub potwierdzenie nieistnienia) cyklu Hamiltona jest trywialne i sprowadza się do sprawdzenia, czy istnieje krawędź <math>\{v_n,v_0\}</math> – zajmuje to, w zależności od [[Reprezentacja grafu|sposobu reprezentacji grafu]], czas stały lub <math>O(n),</math> gdzie <math>n</math> to liczba wierzchołków danego grafu (zobacz: [[Asymptotyczne tempo wzrostu|Notacja dużego O]]).

: <math>\omega (V(G)\ -\ V')\leleqslant |V'|,</math>

Oczywiste jest, że żaden [[graf spójny|graf niespójny]] nie jest hamiltonowski. Dodawanie krawędzi (w szczególności krawędzi wielokrotnych i pętli) do grafu Hamiltona w oczywisty sposób nie może uczynić z niego grafu niehamiltonowskiego. Każdy [[graf pełny]] o <math>V</math> wierzchołkach zawiera [[Silnia|''V''!]] cykli Hamiltona, gdyż dla każdej [[Permutacja|permutacji]] indeksów wierzchołków, <math>v_1, v_2, \ldotsdots, v_V, v_1</math> wyznacza istniejącą drogę, będącą cyklem Hamiltona. Każdy [[Turniej (matematyka)|turniej]] ma ścieżkę Hamiltona.