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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показано 13 промежуточных версий 3 участников)
Строка 8: Строка 8:
 
|statement = Пусть граф <tex> G </tex> имеет <tex>n \geqslant 3</tex> вершин и выполнены следующие два условия:
 
|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> \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>n</tex> число вершин степени <tex>(n-1)/2</tex> не превосходит <tex>(n-1)/2</tex>
  
то <tex> G </tex> {{---}} [[Гамильтоновы графы|гамильтонов]] граф.
+
тогда <tex> G </tex> {{---}} [[Гамильтоновы графы|гамильтонов]] граф.
  
 
|proof =  
 
|proof =  
[[Файл: Graph-Posha.png|500px|thumb|right|]]
+
[[Файл: 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> вершинами, удовлетворяющий условиям теоремы.
 
Предположим, что теорема неверна. Пусть <tex> G </tex> {{---}} максимальный негамильтонов граф с <tex> n </tex> вершинами, удовлетворяющий условиям теоремы.
  
Легко видеть, что добавление любого ребра в граф, обладающий указанными свойствами, приводит к графу, который также обладает этими свойствами. Таким образом, поскольку добавление к <tex> G </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>. Ясно, что вершина <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> (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>. Ясно, что вершина <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> должны быть смежны.
 
Далее, так как <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> должны быть смежны.
Строка 25: Строка 25:
 
Отсюда следует, что если <tex> \deg v \geqslant n/2 </tex> для всех вершин <tex> v </tex>, то <tex> G </tex> {{---}} гамильтонов граф. В силу изложенного выше каждая пара вершин графа <tex> G </tex> смежна, т.е. <tex> G </tex> {{---}} полный граф. Мы пришли к противоречию, поскольку <tex> K_{n} </tex> {{---}} гамильтонов граф для всех <tex> n \geqslant 3 </tex>.
 
Отсюда следует, что если <tex> \deg v \geqslant n/2 </tex> для всех вершин <tex> v </tex>, то <tex> G </tex> {{---}} гамильтонов граф. В силу изложенного выше каждая пара вершин графа <tex> G </tex> смежна, т.е. <tex> G </tex> {{---}} полный граф. Мы пришли к противоречию, поскольку <tex> K_{n} </tex> {{---}} гамильтонов граф для всех <tex> n \geqslant 3 </tex>.
  
Таким образом, в <tex> G </tex> есть вершина <tex> v </tex> с <tex> \deg v < n/2 </tex>. Обозначим через <tex> m </tex> наибольшую среди степеней всех таких вершин. Выберем такую вершину <tex> v_{1} </tex>, что <tex> \deg v_{1} = m </tex>. По принятому предположению число вершин со степенями, не превосходящими <tex> m </tex>, не больше чем <tex> m < n/2 </tex>, поэтому должно быть более чем <tex> m </tex> вершин со степенями, превосходящими <tex> m </tex>, и, следовательно, не меньшими чем <tex> n/2 </tex>. В результате найдется некоторая вершина, скажем <tex> v_{n} </tex>, степени по крайней мере <tex> n/2 </tex>, не смежная с <tex> v_{1} </tex>. Так как <tex> v_{1} </tex> и <tex> v_{n} </tex> не смежны, то существует остовная простая цепь <tex> v_{1} \dotsc v_{n} </tex>. Как и выше, обозначим через <tex> v_{{i}_{1}}, \dotsc, v_{{i}_{m}} </tex> вершины графа <tex> G </tex>, смежные с <tex> v_{1} </tex>, и заметим, что вершина <tex> v_{n} </tex> не может быть смежной ни с одной из <tex> m </tex> вершин <tex> v_{{i}_{j-1}} </tex> для <tex> 1 \leqslant j \leqslant m </tex>. Но поскольку <tex> v_{1} </tex> и <tex> v_{n} </tex> не смежны, а <tex> v_{n} </tex> имеет степень не меньше <tex> n/2 </tex>, то, как было показано в первой части доказательства, <tex> m </tex> должно быть меньше чем <tex> (n-1)/2 </tex>. Так как по предположению число вершин со степенями, не превосходящими <tex> m </tex>, меньше чем <tex> m </tex>, то хотя бы одна из <tex> m </tex> вершин <tex> v_{{i}_{j-1}} </tex>, скажем <tex> v' </tex>, должна иметь степень не меньше <tex> n/2 </tex>. Итак, мы установили, что степени двух несмежных вершин <tex> v_{n} </tex> и <tex> v' </tex> не меньше <tex> n/2 </tex>. Полученное противоречие завершает доказательство теоремы.  
+
Таким образом, в <tex> G </tex> есть вершина <tex> v </tex> с <tex> \deg v < n/2 </tex>. Обозначим через <tex> m </tex> наибольшую среди степеней всех таких вершин. Выберем такую вершину <tex> v_{1} </tex>, что <tex> \deg v_{1} = m </tex>. По принятому предположению число вершин со степенями, не превосходящими <tex> m </tex>, не больше чем <tex> m < n/2 </tex>, поэтому должно быть более чем <tex> m </tex> вершин со степенями, превосходящими <tex> m </tex>, и, следовательно, не меньшими чем <tex> n/2 </tex>. В результате найдется некоторая вершина, скажем <tex> v_{n} </tex>, степени по крайней мере <tex> n/2 </tex>, не смежная с <tex> v_{1} </tex>. Так как <tex> v_{1} </tex> и <tex> v_{n} </tex> не смежны, то существует простой гамильтонов путь <tex> v_{1} \dotsc v_{n} </tex>. Как и выше, обозначим через <tex> v_{{i}_{1}}, \dotsc, v_{{i}_{m}} </tex> вершины графа <tex> G </tex>, смежные с <tex> v_{1} </tex>, и заметим, что вершина <tex> v_{n} </tex> не может быть смежной ни с одной из <tex> m </tex> вершин <tex> v_{{i}_{j-1}} </tex> для <tex> 1 \leqslant j \leqslant m </tex>. Но поскольку <tex> v_{1} </tex> и <tex> v_{n} </tex> не смежны, а <tex> v_{n} </tex> имеет степень не меньше <tex> n/2 </tex>, то, как было показано в первой части доказательства, <tex> m </tex> должно быть меньше чем <tex> (n-1)/2 </tex>. Так как по предположению число вершин со степенями, не превосходящими <tex> m </tex>, меньше чем <tex> m </tex>, то хотя бы одна из <tex> m </tex> вершин <tex> v_{{i}_{j-1}} </tex>, скажем <tex> v' </tex>, должна иметь степень не меньше <tex> n/2 </tex>. Итак, мы установили, что степени двух несмежных вершин <tex> v_{n} </tex> и <tex> v' </tex> не меньше <tex> n/2 </tex>. Полученное противоречие завершает доказательство теоремы.  
 
}}
 
}}
  
 
==Замечания==
 
==Замечания==
[[Файл: Graph-Posha-Cubic.png|250px|thumb|right|]]
+
[[Файл: Graph-Posha-Cubic.png|250px|thumb|right|Кубический гамильтонов граф]]
*Приведенное достаточное условие не является необходимым. Изображенный на рисунке кубический граф гамильтонов, хотя ясно, что он не удовлетворяет условиям теоремы.
+
*Приведенное достаточное условие не является необходимым. Изображенный на рисунке кубический граф {{---}} гамильтонов, хотя ясно, что он не удовлетворяет условиям теоремы.
 
*Условия теоремы нельзя улучшить, так как при их ослаблении новое условие уже не будет достаточным для гамильтоновости графа.
 
*Условия теоремы нельзя улучшить, так как при их ослаблении новое условие уже не будет достаточным для гамильтоновости графа.
 +
  
  
Строка 41: Строка 42:
 
==Следствия==
 
==Следствия==
  
Ограничивая условия теоремы Поша, получаем более простые, но менее сильные достаточные условия, найденные Оре и Дираком соответственно:
+
Ограничивая условия теоремы Поша, получаем более простые, но менее сильные достаточные условия, найденные [[Теорема Оре|Оре]] и [[Теорема Дирака|Дираком]] соответственно:
  
 
{{Теорема
 
{{Теорема
Строка 55: Строка 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> {{---}} гамильтонов граф.
 
 
}}
 
}}
  
 
==См. также==
 
==См. также==
* [[Теорема Оре]]
+
*[[Теорема Оре]]
* [[Теорема Дирака]]
+
*[[Теорема Дирака]]
 +
*[[Теорема Хватала]]
 +
*[[Теорема Гринберга]]
 +
*[[Теорема Редеи-Камиона]]
  
==Источники==
+
==Источники информации==
 
*Харари Ф. Теория графов: Пер. с англ. / Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 60 с.
 
*Харари Ф. Теория графов: Пер. с англ. / Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 60 с.
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обходы графов]]
 
[[Категория: Обходы графов]]
 +
[[Категория: Гамильтоновы графы]]

Текущая версия на 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 с.