Теорема Дирака

НЕТ ВОЙНЕ

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

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

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

9м топ остальным по лицу хлоп

Альтернативное доказательство

Теорема (Дирак — альтернативное доказательство):

Пусть [math]G[/math] — неориентированный граф и [math]\delta[/math] — минимальная степень его вершин. Если [math]n \geqslant 3[/math] и [math]\delta \geqslant n/2[/math], то [math]G[/math] — гамильтонов граф.

Доказательство:

[math]\triangleright[/math]

Для [math]\forall k[/math] верна импликация [math]d_k \leqslant k \lt n/2 \Rightarrow d_{n-k} \geqslant n-k[/math], поскольку левая её часть всегда ложна. Тогда по теореме Хватала [math]G[/math] — гамильтонов граф.

[math]\triangleleft[/math]

Теорема (Вывод из теоремы Оре):

Пусть [math]G[/math] — неориентированный граф и [math]\delta[/math] — минимальная степень его вершин. Если [math]n \geqslant 3[/math] и [math]\delta \geqslant n/2[/math], то [math]G[/math] — гамильтонов граф.

Доказательство:

[math]\triangleright[/math]

Возьмем любые неравные вершины [math] u, v \in G [/math]. Тогда [math] \displaystyle \deg u + \deg v \geqslant \frac n 2 + \frac n 2 = n [/math]. По теореме Оре [math] G [/math] — гамильтонов граф.

[math]\triangleleft[/math]

См. также

• Гамильтоновы графы
• Теорема Хватала
• Теорема Оре
• Теорема Поша

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

• Wikipedia — Dirac's Theorem
• Graham, R.L., Groetschel M., and Lovász L., eds. (1996). Handbook of Combinatorics, Volumes 1 and 2. Elsevier (North-Holland), Amsterdam, and MIT Press, Cambridge, Mass. ISBN 0-262-07169-X.