Теорема Самнера — Лас Вергнаса (WIP) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
Строка 1: Строка 1:
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 
|+
 
|-align="center"
 
|'''НЕТ ВОЙНЕ'''
 
|-style="font-size: 16px;"
 
|
 
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 
 
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 
 
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 
 
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 
 
''Антивоенный комитет России''
 
|-style="font-size: 16px;"
 
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 
|-style="font-size: 16px;"
 
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 
|}
 
 
 
'''Теорема Самнера — Лас Вергнаса''' даёт достаточное условие для существования совершенного паросочетания в графах чётного порядка.
 
'''Теорема Самнера — Лас Вергнаса''' даёт достаточное условие для существования совершенного паросочетания в графах чётного порядка.
  

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

Теорема Самнера — Лас Вергнаса даёт достаточное условие для существования совершенного паросочетания в графах чётного порядка.

Подготовка к доказательству

Определение:
Смежными листами (англ. coincident endpoints) в неориентрированном графе называется такая пара вершин [math]x, y[/math], что [math]\operatorname{deg}x = 1, \operatorname{deg}y = 1[/math], причём обе вершины имеют общую смежную вершину (другими словами, расстояние между этими вершинами [math]\rho(x, y) = 2[/math]).

Для доказательства основной теоремы потребуется доказать вспомогательную лемму:

Лемма:
Если [math]G[/math] — связный граф, состоящий из [math]n \geq 3[/math] вершин и не содержащий смежных листов, то найдутся такие две смежные вершины [math]x, y[/math], что граф [math]G \backslash \{x, y\}[/math] также будет связен.
Доказательство:
[math]\triangleright[/math]
Лемма, очевидно выполняется для полных графов [math]K_n[/math]. Таким образом, будем считать далее, что диаметр графа [math]d \geq 2[/math].
Пусть [math]a, y[/math] — вершины графа [math]G[/math], находящиеся на расстоянии [math]\rho(a, y) = d[/math], а [math]D = a \dots xy[/math] — путь между этими вершинами длины [math]d[/math] (вершины [math]a[/math] и [math]x[/math] могут совпадать).
Предположим, что [math]G^* = G \backslash \{x, y\}[/math] не связен. Обозначим за [math]A[/math] компоненту связности [math]G^*[/math] такую, что [math]a \in A[/math]. Так как [math]D[/math] является диаметром графа [math]G[/math], то все вершины графа [math]G^* \backslash A[/math] смежны с [math]x[/math] в графе [math]G[/math] (иначе мы бы нашли пару вершин, расстояние между которыми было бы больше, чем [math]d[/math]). После этого возможны несколько случаев:
  1. Граф [math]G^* \backslash A[/math] содержит компоненту [math]B[/math] размера [math]m \geq 2[/math]. Тогда для [math]\forall b, c \in B[/math], которые в [math]B[/math] являются смежными, в [math]G \backslash \{b, c\}[/math] будет существовать путь из каждой вершины до [math]x[/math], а значит, [math]G \backslash \{b, c\}[/math] связен.
  2. Граф [math]G^* \backslash A[/math] содержит вершину [math]e[/math], смежную с [math]y[/math] в графе [math]G[/math]. Тогда по аналогичным причинам граф [math]G \backslash \{e, y\}[/math] связен.
  3. Граф [math]G^* \backslash A[/math] не содержит компонент размера [math]m \geq 2[/math] (случай 1), а значит он содержит только изолированные вершины. Тогда все вершины [math]G^* \backslash A[/math] связаны только с [math]x[/math] в исходном графе [math]G[/math] (они могли быть связаны максимум с еще одной вершиной [math]y[/math], а это было рассмотрено в случае 2). Но, так как граф не содержит смежных листов, то [math]G^* \backslash A[/math] состоит из единственной вершины [math]f[/math]. Если [math]\operatorname{deg}y = 1[/math], то [math]f[/math] и [math]y[/math] являлись бы смежными листами. Таким образом, [math]y[/math] должен быть связан с вершиной из [math]A[/math]. Следовательно, [math]G \backslash \{f, x\}[/math] связен.
[math]\triangleleft[/math]

Теорема

Докажем оригинальную версию теоремы, доказанную независимо Самнером (Sumner, 1974) и Лас Вергнасом (Las Vergnas, 1975). Напомним, что индуцированный подграф [math]-[/math] это граф, образованный из подмножества вершин графа вместе со всеми рёбрами, соединяющими пары вершин из этого подмножества.

Теорема (Самнера — Лас Вергнаса):
Пусть [math]G[/math] — связный граф четного порядка [math]2n \geq 3[/math], и [math]k[/math] [math]-[/math] такое число, что любой индуцированный связный подграф [math]G[/math] четного порядка [math]2k[/math] содержит совершенное паросочетание ([math]1 \lt k \leq n[/math]). Тогда [math]G[/math] также содержит совершенное паросочетание.
Доказательство:
[math]\triangleright[/math]
Докажем теорему по индукции.
Теорема довольно просто проверяется для случаев [math]n = 2, 3[/math]. Предположим, что теорема выполняется для [math]n - 1[/math] ([math]n \geq 4[/math]). Пусть [math]G[/math] — связный граф порядка [math]2n[/math] и предположим, что [math]k[/math] [math]-[/math] это такое число, что любой индуцированный связный подграф [math]G[/math] четного порядка [math]2k[/math] содержит совершенное паросочетание.
Случай [math]k = n[/math] очевиден, поэтому можно считать, что [math]k \leq n - 1[/math].
Если граф содержит смежные листы [math]a[/math] и [math]b[/math], то рассмотрим любой связный подграф графа [math]G[/math] четного порядка [math]2k[/math], содержащий эти вершины. Тогда хотя бы одна из вершин [math]a, b[/math] будет не покрыта паросочетанием.
Таким образом, граф [math]G[/math] не содержит смежных листов. Тогда из леммы следует, что существуют смежные вершины [math]x[/math] и [math]y[/math], что граф [math]G \backslash \{x, y\}[/math] связен.
По нашему индукционному предположению, граф [math]G \backslash \{x, y\}[/math] содержит совершенное паросочетание, а значит, добавив ребро [math]xy[/math], мы получим совершенное паросочетание для [math]G[/math].
[math]\triangleleft[/math]

Также можно доказать более слабое, но полезное утверждение про графы без лап (индуцированных подграфов [math]K_{1,3}[/math]).

Утверждение (следствие из теоремы):
Пусть [math]G[/math] — связный граф чётного порядка [math]2n[/math], не содержащий лап. Тогда [math]G[/math] содержит совершенное паросочетание.
[math]\triangleright[/math]
Единственный связный граф порядка [math]4[/math], который не содержит совершенного паросочетания — это [math]K_{1,3}[/math]. Таким образом, эта теорема является частным случаем теоремы Самнера — Лас Вергнаса при [math]k = 2[/math], за исключением тривиального случая [math]n = 1[/math].
Все связные неориентированные графы, состоящие из 4 вершин, с точностью до изоморфизма
[math]\triangleleft[/math]

См. также

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