Теорема Поша

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Теорема

Теорема (Поша):

Пусть граф [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 с.