Изменения

Пусть у нас есть граф <tex>\mathbb{G} = \left \langle \mathbb{V, E} \right \rangle</tex>, удовлетворяющий условию [[Теорема ДиракаОре|теоремы Оре]] или [[Теорема Дирака|теоремы Дирака]], и требуется найти в нем гамильтонов цикл. Поступим следующим образом: заведем очередь и положим в нее все вершины нашего графа(не важно в каком порядке). Теперь <tex>n *(n -1)</tex>, где <tex> n = \left | \mathbb{V}\right |</tex> , раз будем делать следующую операцию:

* Если между первой (здесь и далее первая вершина - вершина в голове очереди) и второй вершиной в очереди есть ребро в графе <tex>\mathbb{G}</tex>, то перемещаем первую вершину в конец очереди и переходим к следующей итерации.* Если между первой и второй вершиной в очереди ребра нет, то найдем вершину <tex>v_i</tex>, где <tex>i > 2</tex>, такую что, ребра <tex>v_1v_i, v_2v_{i+1} \in \mathbb{E}</tex> (так как у нас для графа выполнена либо [[Теорема Оре|теорема Оре]], либо [[Теорема Дирака|теорема Дирака]], то такая вершина обязательно найдется; чуть позже мы это докажем явно). После чего поменяем в очереди местами вершины <tex>v_2</tex> и <tex>v_i</tex>, <tex>v_3</tex> и <tex>v_{i-1}</tex>, <tex>v_{2+j} </tex> и <tex>v_{i-j}</tex>, и так далее, пока <tex>2 + j < i - j</tex> (то есть <tex>j</tex> пробегает все значения от 0 до значения заданного неравенством). Теперь у нас появилось ребро между первой и второй вершинами в очереди (теперь вторая вершина, это та, которая была до разворота на <tex>i</tex>-й позиции), а также, гарантированно существует ребро между <tex>i</tex>-й и <tex>(i+1)</tex>-й вершинами очереди. После этого, так же как и в первом случае, оправляем первую вершину в конец очереди.