71
правка
Изменения
м
Нет описания правки
Тогда <tex>S \cup T \subset \{2,3,...,n\}</tex>, откуда <tex>|S \cup T |< n</tex>. Но <tex>|S|+|T| = \operatorname{deg}\ v_1 + \operatorname{deg}\ v_2 \ge n</tex> по условию [[Теорема Оре|теоремы Оре]] или [[Теорема Дирака|теоремы Дирака]], в зависимости от наших начальных условий. А значит <tex>S \cap T \ne \varnothing</tex>, следовательно искомая вершина обязательно найдется.
Поскольку каждый раз, когда у нас нет ребра между двумя обрабатываемыми вершинами, мы переворачиваем нашу последовательность так, чтобы после переворота <tex>\mathrm{v}_i, \mathrm{v}_{i+1}</tex> и <tex>\mathrm{v}_j, \mathrm{v}_{j+1}</tex> становились связанными ребром, то, рассмотрев все пары вершин в последовательности, мы добьемся того, что любые две соседние пары вершин <tex>\mathrm{v}_i, \mathrm{v}_{i+1}</tex> будут связаны ребром, а это и значит что мы нашли цикл.
== Сложность алгоритма ==
Алгоритм работает за <tex>O(n^2)</tex>. Действительно, количество итераций внешнего цикла <tex>\mathrm{for}</tex> всегда равно <tex>n - 1</tex>, во внутреннем цикле, в худшем случае, будет выполнено <tex>n - 2</tex> итерации, получаем время работы <tex>O(n^2)</tex>.
== См.также ==
