Изменения

==Алгорит Алгоритм нахождения гамильтового цикла==Основан на [[Обход в глубину, цвета вершин|обходе в глубину]]Приведём два алгоритма поиска гамильтонова цикла.===Псевдокод=== search_cyclebool check_hamiltonian(0graph g, 0bool[] used, number_of_vertices); bool search_cycle(int vvert, int wcount, int d[] next): { if(w count == vg.vertices): next[vert] = 0 return (d =vert; 0) in g.edges for (i = 0; i < g.vertices; i++);: visited if (!used[vi] = true&& (vert;i) in g.edges): for (t <tex>\in</tex> Adj used[vi])= true if(!visitednext[tvert])= i if(search_cyclecheck_hamiltonian(tg, used, wi, d - count + 1, next)): return true; visited used[vi] = false; return false; }* used — отметки о посещении* vert — текущая вершина* count — количество посещённых вершин  Приведённая процедура работает следующим образом: перебираются всё рёбра из текущей вершины в ещё не посещённые. Чтобы проверить граф на гамильтоновость, необходимо запустить процедуру из вершины с номером 0 и параметром count = 1. Если процедура возвращает true, то в массиве next будет храниться следующая вершина на гамильтоновом цикле.