210
правок
Изменения
Нет описания правки
Поша
|statement = Пусть граф <tex> G </tex> имеет <tex>n \geqslant 3</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 =
Предположим, что теорема неверна, и пусть . Пусть <tex> G </tex> {{---}} максимальный негамильтонов граф с <tex> n </tex> вершинами, удовлетворяющий условиям теоремы.
Легко видеть, что добавление любого ребра в граф, обладающий указанными свойствами, приводит к графу, который также обладает этими свойствами. Таким образом, поскольку добавление к <tex> G </tex> произвольного ребра приводит к гамильтонову ребру, любые две несмежные вершины соединимы простой остовной цепью.
Покажем сначала, что всякая вершина, степень которой не меньше <tex> (n-1)/2 </tex>, смежна с каждой вершиной со степенью, большей чем <tex> (n-1)/2 </tex>. Допустим (не теряя Не умаляя общности), допустим, что <tex> \deg v_{1} \geqslant (n-1)/2 </tex> и <tex> \deg v_{n} \geqslant n/2 </tex>, но вершины <tex> v_{1} </tex> и <tex> v_{n} </tex> не смежны. Тогда существует простая остовная цепь <tex> v_{1} v_{2} \dotsc v_{n} </tex>, соединяющая <tex> v_{1} </tex> и <tex> v_{n} </tex>. Обозначим вершины, смежные с <tex> v_{1} </tex>, через <tex> v_{{i}_{1}}, \dotsc,v_{{i}_{k}} </tex>, где <tex> k = \deg v_{1} </tex> и <tex> 2=i_{1} < i_{2} < \dotsc < i_{k} </tex>. [[Файл: Graph-Posha.png|380px|thumb|right|]] Ясно, что вершина <tex> v_{n} </tex> не может быть смежной ни с одной вершиной из <tex> G </tex> вида <tex> v_{{i}_{j-1}} </tex>, поскольку тогда в <tex> G </tex> был бы гамильтонов цикл <tex> v_{1} v_{2} \dotsc v_{{i}_{j-1}} v_{n} v_{n-1} \dotsc v_{{i}_{j}} v_{1} </tex>.
Далее, так как <tex> k \geqslant (n-1)/2 </tex>, то <tex> n/2 \leqslant \deg v_{n} \leqslant n-1-k < n/2 </tex>, что невозможно. Поэтому <tex> v_{1} </tex> и <tex> v_{n} </tex> должны быть смежны.
}}
Ограничивая условия теоремы Поша, получаем более простые, но менее сильные достаточные условия, найденные Оре и Дираком соответственно: {{Теорема|id = Th2|about = Следствие 1|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> {{---}} гамильтонов граф. |proof =
}}
{{Теорема
|id = Th3
|about = Следствие 2
|statement =
Если <tex> n > 3 </tex> и <tex> \deg v \geqslant n/2 </tex> для любой вершины <tex> v </tex> графа <tex> G </tex>, то <tex> G </tex> {{---}} гамильтонов граф.
}}
==Источники==
*Харари Ф. Теория графов: Пер. с англ. / Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 60 с.
