1632
правки
Изменения
м
|proof =
Из условия теоремы Поша ясно, что количество вершин, степень которых больше <tex> n / 2 </tex>, больше <tex> n / 2 </tex>. Тогда данное условие <tex> \deg u + \deg v \geqslant n </tex> удовлетворяет условию теоремы Поша. Следовательно <tex> G </tex> {{---}} гамильтонов граф.
|proof =
Возьмем любые несмежные вершины <tex> u, v \in G </tex>.
Тогда <tex> \displaystyle \deg u + \deg v \geqslant \frac n 2 + \frac n 2 = n </tex>.
По теореме Оре <tex> G </tex> {{---}} гамильтонов граф.
rollbackEdits.php mass rollback
|statement = Пусть граф <tex> G </tex> имеет <tex>n \geqslant 3</tex> вершин и выполнены следующие два условия:
*для всякого <tex> \forall </tex> <tex>k,\, 1 \leqslant k < (n-1)/2</tex>, число вершин со степенями, не превосходящими <tex>k</tex>, меньше чем <tex>k</tex>;*для нечетного <tex>n</tex> число вершин степени <tex>(n-1)/2</tex> не превосходит <tex>(n-1)/2</tex>,
тогда <tex> G </tex> {{---}} [[Гамильтоновы графы|гамильтонов]] граф.
|proof =
[[Файл: Graph-Posha.png|500px|thumb|right|Гамильтонов цикл <tex> v_{1} v_{2} \dotsc v_{{i}_{j-1}} v_{n} v_{n-1} \dotsc v_{{i}_{j}} v_{1} </tex>]]
Предположим, что теорема неверна. Пусть <tex> G </tex> {{---}} максимальный негамильтонов граф с <tex> n </tex> вершинами, удовлетворяющий условиям теоремы.
==Замечания==
[[Файл: Graph-Posha-Cubic.png|250px|thumb|right|Кубический гамильтонов граф]]
*Приведенное достаточное условие не является необходимым. Изображенный на рисунке кубический граф {{---}} гамильтонов, хотя ясно, что он не удовлетворяет условиям теоремы.
*Условия теоремы нельзя улучшить, так как при их ослаблении новое условие уже не будет достаточным для гамильтоновости графа.
|statement =
Если <tex> n \geqslant 3 </tex> и <tex> \deg u + \deg v \geqslant n </tex> для любой пары <tex> u </tex> и <tex> v </tex> несмежных вершин графа <tex> G </tex>, то <tex> G </tex> {{---}} гамильтонов граф.
}}
|statement =
Если <tex> n > 3 </tex> и <tex> \deg v \geqslant n/2 </tex> для любой вершины <tex> v </tex> графа <tex> G </tex>, то <tex> G </tex> {{---}} гамильтонов граф.
}}
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]
[[Категория: Гамильтоновы графы]]
