Теорема Оре

НЕТ ВОЙНЕ

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

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

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

Теорема:

Если [math]n \geqslant 3[/math] и [math]\operatorname{deg} u + \operatorname{deg} v \geqslant n[/math] для любых двух различных несмежных вершин [math]u[/math] и [math]v[/math] неориентированного графа [math]G[/math], то [math]G[/math] — гамильтонов граф.

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

[math]\triangleright[/math]

Пусть, от противного, существует граф [math]G[/math], который удовлетворяет условию теоремы, но не является гамильтоновым графом. Будем добавлять к нему новые ребра до тех пор, пока не получим максимальный негамильтонов граф [math]G'[/math]. В силу того, что мы только добавляли ребра, условие теоремы не нарушилось. Пусть [math]u,v[/math] несмежные вершины в полученном графе [math]G'[/math]. Если добавить ребро [math]uv[/math], появится гамильтонов цикл. Тогда путь [math](u,v)[/math] — гамильтонов. Для вершин [math]u,v[/math] выполнено [math]\operatorname{deg} u + \operatorname{deg} v \geqslant n.[/math] По принципу Дирихле всегда найдутся две смежные вершины [math] t_1,t_2[/math] на пути [math](u,v)[/math], т.е. [math]u \dots t_1t_2 \dots v[/math] , такие, что существует ребро [math]ut_2[/math] и ребро [math]t_1v.[/math] Действительно, пусть [math]S=[/math] [math]\{ i \mid e_i=ut_{i+1} \in EG \}[/math] и [math]T = [/math] [math]\{ i \mid f_i=t_iv \in EG \}[/math] Имеем: [math]\left\vert S \right\vert + \left\vert T \right\vert = \operatorname{deg} u + \operatorname{deg} v \geqslant n [/math], но [math]\left\vert S + T \right\vert \lt n.[/math] Тогда [math]\left\vert S\cap T \right\vert = \left\vert S \right\vert + \left\vert T \right\vert - \left\vert S+T \right\vert \gt 0[/math], т. е. [math]\exists i: ut_{i+1}\in EG[/math] и [math] t_iv \in EG.[/math] Получили противоречие, т. к. [math]u \dots t_1v \dots t_2u[/math] — гамильтонов цикл.

[math]\triangleleft[/math]

См. также

• Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
• Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре
• Теорема Дирака

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

• Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2
• Харари — Теория графов. ISBN 978-5-397-00622-4