Изменения
Нет описания правки
Пусть граф G имеет <tex>p \geq 3</tex> вершин. Если для всякого <tex>n,\, 1 \leq n < (p-1)/2</tex> число вершин состепенями, не превосходящими <tex>n</tex>, меньше чем <tex>n</tex>, и для нечетного <tex>p</tex> число вершин степени <tex>(p-1)/2</tex> не превосходит <tex>(p-1)/2</tex>, то G - гамильтонов граф
}}
==Алгорит нахождения гамильтового цикла==
Основан на [[Обход в глубину, цвета вершин|обходе в глубину]].
===Псевдокод===
search_cycle(0, 0, number_of_vertices);
bool search_cycle(int v, int w, int d)
{
if(w == v)
return (d == 0);
visited[v] = true;
for (t <tex>\in</tex> Adj[v])
if(!visited[t])
if(search_cycle(t, w, d - 1))
return true;
visited[v] = false;
return false;
}
==Источники==
*Харари Ф. Теория графов: Пер. с англ. / Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 60 с.
*Седжвик Р. Фундаментальные алгоритмы на C++. Алгоритмы на графах. — СПб: ООО «ДиаСофтЮП», 2002.
