Теорема Поша — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показаны 3 промежуточные версии 3 участников)
Строка 49: Строка 49:
 
|statement =  
 
|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> {{---}} гамильтонов граф.  
 
Если <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 =
 
Возьмем две любые несмежные вершины <tex> u </tex> и <tex> v </tex>. Пусть <tex> \deg u = k </tex>. Тогда <tex> \deg v \geqslant n - k </tex>. Возьмем <tex> k </tex> как в условии теоремы Поша. Тогда, учитывая ограничения теоремы и что вершины несмежны, получаем, что следствие верно.
 
 
}}
 
}}
  
Строка 58: Строка 56:
 
|statement =  
 
|statement =  
 
Если <tex> n > 3 </tex> и <tex> \deg v  \geqslant n/2 </tex> для любой вершины <tex> v </tex> графа <tex> G </tex>, то <tex> G </tex> {{---}} гамильтонов граф.  
 
Если <tex> n > 3 </tex> и <tex> \deg v  \geqslant n/2 </tex> для любой вершины <tex> v </tex> графа <tex> G </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> {{---}} гамильтонов граф.
 
 
}}
 
}}
  
Строка 74: Строка 70:
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обходы графов]]
 
[[Категория: Обходы графов]]
 +
[[Категория: Гамильтоновы графы]]

Текущая версия на 19:42, 4 сентября 2022

Теорема

Теорема (Поша):
Пусть граф [math] G [/math] имеет [math]n \geqslant 3[/math] вершин и выполнены следующие два условия:
  • [math] \forall [/math] [math]k,\, 1 \leqslant k \lt (n-1)/2[/math], число вершин со степенями, не превосходящими [math]k[/math], меньше чем [math]k[/math]
  • для нечетного [math]n[/math] число вершин степени [math](n-1)/2[/math] не превосходит [math](n-1)/2[/math]
тогда [math] G [/math]гамильтонов граф.
Доказательство:
[math]\triangleright[/math]
Гамильтонов цикл [math] v_{1} v_{2} \dotsc v_{{i}_{j-1}} v_{n} v_{n-1} \dotsc v_{{i}_{j}} v_{1} [/math]

Предположим, что теорема неверна. Пусть [math] G [/math] — максимальный негамильтонов граф с [math] n [/math] вершинами, удовлетворяющий условиям теоремы.

Легко видеть, что добавление любого ребра в граф, обладающий указанными свойствами, приводит к графу, который также обладает этими свойствами. Таким образом, поскольку добавление к [math] G [/math] произвольного ребра приводит к гамильтонову графу, любые две несмежные вершины соединимы простым гамильтоновым путем.

Покажем сначала, что всякая вершина, степень которой не меньше [math] (n-1)/2 [/math], смежна с каждой вершиной со степенью, большей чем [math] (n-1)/2 [/math]. Не умаляя общности, допустим, что [math] \deg v_{1} \geqslant (n-1)/2 [/math] и [math] \deg v_{n} \geqslant n/2 [/math], но вершины [math] v_{1} [/math] и [math] v_{n} [/math] не смежны. Тогда существует простой гамильтонов путь [math] v_{1} v_{2} \dotsc v_{n} [/math], соединяющий [math] v_{1} [/math] и [math] v_{n} [/math]. Обозначим вершины, смежные с [math] v_{1} [/math], через [math] v_{{i}_{1}}, \dotsc,v_{{i}_{k}} [/math], где [math] k = \deg v_{1} [/math] и [math] 2=i_{1} \lt i_{2} \lt \dotsc \lt i_{k} [/math]. Ясно, что вершина [math] v_{n} [/math] не может быть смежной ни с одной вершиной из [math] G [/math] вида [math] v_{{i}_{j-1}} [/math], поскольку тогда в [math] G [/math] был бы гамильтонов цикл [math] v_{1} v_{2} \dotsc v_{{i}_{j-1}} v_{n} v_{n-1} \dotsc v_{{i}_{j}} v_{1} [/math].

Далее, так как [math] k \geqslant (n-1)/2 [/math], то [math] n/2 \leqslant \deg v_{n} \leqslant n-1-k \lt n/2 [/math], что невозможно. Поэтому [math] v_{1} [/math] и [math] v_{n} [/math] должны быть смежны.

Отсюда следует, что если [math] \deg v \geqslant n/2 [/math] для всех вершин [math] v [/math], то [math] G [/math] — гамильтонов граф. В силу изложенного выше каждая пара вершин графа [math] G [/math] смежна, т.е. [math] G [/math] — полный граф. Мы пришли к противоречию, поскольку [math] K_{n} [/math] — гамильтонов граф для всех [math] n \geqslant 3 [/math].

Таким образом, в [math] G [/math] есть вершина [math] v [/math] с [math] \deg v \lt n/2 [/math]. Обозначим через [math] m [/math] наибольшую среди степеней всех таких вершин. Выберем такую вершину [math] v_{1} [/math], что [math] \deg v_{1} = m [/math]. По принятому предположению число вершин со степенями, не превосходящими [math] m [/math], не больше чем [math] m \lt n/2 [/math], поэтому должно быть более чем [math] m [/math] вершин со степенями, превосходящими [math] m [/math], и, следовательно, не меньшими чем [math] n/2 [/math]. В результате найдется некоторая вершина, скажем [math] v_{n} [/math], степени по крайней мере [math] n/2 [/math], не смежная с [math] v_{1} [/math]. Так как [math] v_{1} [/math] и [math] v_{n} [/math] не смежны, то существует простой гамильтонов путь [math] v_{1} \dotsc v_{n} [/math]. Как и выше, обозначим через [math] v_{{i}_{1}}, \dotsc, v_{{i}_{m}} [/math] вершины графа [math] G [/math], смежные с [math] v_{1} [/math], и заметим, что вершина [math] v_{n} [/math] не может быть смежной ни с одной из [math] m [/math] вершин [math] v_{{i}_{j-1}} [/math] для [math] 1 \leqslant j \leqslant m [/math]. Но поскольку [math] v_{1} [/math] и [math] v_{n} [/math] не смежны, а [math] v_{n} [/math] имеет степень не меньше [math] n/2 [/math], то, как было показано в первой части доказательства, [math] m [/math] должно быть меньше чем [math] (n-1)/2 [/math]. Так как по предположению число вершин со степенями, не превосходящими [math] m [/math], меньше чем [math] m [/math], то хотя бы одна из [math] m [/math] вершин [math] v_{{i}_{j-1}} [/math], скажем [math] v' [/math], должна иметь степень не меньше [math] n/2 [/math]. Итак, мы установили, что степени двух несмежных вершин [math] v_{n} [/math] и [math] v' [/math] не меньше [math] n/2 [/math]. Полученное противоречие завершает доказательство теоремы.
[math]\triangleleft[/math]

Замечания

Кубический гамильтонов граф
  • Приведенное достаточное условие не является необходимым. Изображенный на рисунке кубический граф — гамильтонов, хотя ясно, что он не удовлетворяет условиям теоремы.
  • Условия теоремы нельзя улучшить, так как при их ослаблении новое условие уже не будет достаточным для гамильтоновости графа.





Следствия

Ограничивая условия теоремы Поша, получаем более простые, но менее сильные достаточные условия, найденные Оре и Дираком соответственно:

Теорема (Следствие 1):
Если [math] n \geqslant 3 [/math] и [math] \deg u + \deg v \geqslant n [/math] для любой пары [math] u [/math] и [math] v [/math] несмежных вершин графа [math] G [/math], то [math] G [/math] — гамильтонов граф.
Теорема (Следствие 2):
Если [math] n \gt 3 [/math] и [math] \deg v \geqslant n/2 [/math] для любой вершины [math] v [/math] графа [math] G [/math], то [math] G [/math] — гамильтонов граф.

См. также

Источники информации

  • Харари Ф. Теория графов: Пер. с англ. / Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 60 с.