322
правки
Изменения
Нет описания правки
{{Теорема
|statement=
Если <tex>n \ge 3</tex> и <tex>deg\ u + deg\ v \ge n</tex> для любых двух различных несмежных вершин <tex>u</tex> и <tex>v</tex> неориентированного графа <tex>G</tex>, то <tex>G</tex> {{- --}} гамильтонов граф.
|proof=
Будем добавлять к нему новые ребра до тех пор, пока не получим максимальный негамильтонов граф <tex>G'</tex>. В силу того, что мы только добавляли ребра, условие теоремы не нарушилось.
Пусть <tex>u,v</tex> несмежные вершины в полученном графе <tex>G'</tex>. Если добавить ребро <tex>uv</tex>, появится гамильтонов цикл. Тогда путь <tex>(u,v)</tex> {{- --}} гамильтонов.
Для вершин <tex>u,v</tex> выполнено <tex>deg\ u + deg\ v \ge n.</tex>
По принципу Дирихле всегда найдутся две смежные вершины <tex> t_1,t_2</tex> на пути <tex>(u,v)</tex> ,т.е. <tex>u..t_1t_2..v</tex> , такие, что существует ребро <tex>ut_2</tex> и ребро <tex>t_1v.</tex>
Действительно, пусть <tex>S=</tex> { <tex> i| e_i=ut_{i+1} \in EG</tex> } и <tex>T = </tex> { <tex> i| f_i=t_iv \in EG</tex> }
Тогда <tex>\left\vert S\cap T \right\vert = \left\vert S \right\vert + \left\vert T \right\vert - \left\vert S+T \right\vert > 0</tex> т.е. <tex>\exists i| ut_{i+1}\in EG</tex> и <tex> t_iv \in EG.</tex>
Получили противоречие, т.к. <tex>u..t_1v..t_2u</tex> {{- --}} гамильтонов цикл.
}}
== Источники ==
1. Асанов М. О., Баранский В. А., Расин В. В. {{- --}} Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />2. Харари Ф. {{--- }} Теория графов. '''ISBN 978-5-397-00622-4'''
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]
