71
правка
Изменения
м
→Доказательство алгоритма
* Каждый раз, когда нам надо искать вершину <tex>v_i</tex>, где <tex>i > 2</tex>, такую что <tex>v_1v_i, v_2v_{i+1} \in \mathbb{E}</tex>, такая вершина действительно существует.
* После <tex>n* (n - 1)</tex> итераций между каждой парой соседних вершин очереди существует ребро.
Докажем первое. Рассмотрим множество <tex>S = \{i\mid v_1v_i \in \mathbb{E}\}</tex>, состоящее из индексов вершин, смежных с <tex>v_1</tex>, и множество <tex>T = \{i+1 \mid v_2v_{i+1} \in \mathbb{E}\}</tex>, индексов вершин смежных с <tex>v_2</tex>. Заметим, что <tex>S \subset \{3, 4,...,n\}</tex>, а <tex>T \subset \{2, 3,...,n - 1\}</tex>, тогда <tex>S\cup T\subset \{2, 3,...,n\} </tex>, а значит <tex>\left\vert S\cup T\right\vert \le n-1</tex>, в то же время <tex>\left\vert S \right\vert + \left\vert T \right\vert = \operatorname{deg} v_1 + \operatorname{deg} v_2 \ge n</tex> (по условию [[Теорема Оре|теоремы Оре]] или [[Теорема Дирака|теоремы Дирака]]). Из этого следует, что <tex>S\cap T\ne \varnothing</tex>, а это и значит, что искомая вершина существует.
Для доказательства второй части, достаточно заметить, что каждую итерацию алгоритма, мы, в случае отсутствия ребра, между <tex>v_1</tex> и <tex>v_{2}</tex> увеличиваем количество пар соседних в очереди вершин, между которыми есть ребро, как минимум на 1 (это прямое следствие условия поиска нужной вершины, в случае отсутствия ребра), а таких для поиска такой пары требуется не более <tex>n</tex> итераций. Таких пар изначально не более <tex>n</tex>. Откуда , откуда следует, что после <tex>n</tex> итераций, второе условие будет выполнено.
== Сложность алгоритма ==
