Теорема Самнера — Лас Вергнаса - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:37:37Z

rollbackEdits.php mass rollback

185.220.101.2 в 03:59, 1 сентября 2022

2022-09-01T03:59:51Z

176.59.20.8: /* Теорема */

2021-02-10T16:58:16Z

‎Теорема

Unreal.eugene: /* См. также */

2021-01-09T14:31:20Z

‎См. также

Unreal.eugene: Новая страница: «'''Теорема Самнера — Лас Вергнаса''' даёт достаточное условие для существования совершен…»

2021-01-09T14:11:13Z

Новая страница: «'''Теорема Самнера — Лас Вергнаса''' даёт достаточное условие для существования совершен…»

Новая страница

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

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

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

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

Также можно доказать более слабое, но полезное утверждение про графы без лап (индуцированных подграфов <tex>K_{1,3}</tex>).
{{Утверждение
|about=следствие из теоремы
|statement=
Пусть <tex>G</tex> — связный граф чётного порядка <tex>2n</tex>, не содержащий лап. Тогда <tex>G</tex> содержит совершенное паросочетание.
|proof=
:Единственный связный граф порядка <tex>4</tex>, который не содержит совершенного паросочетания — это <tex>K_{1,3}</tex>. Таким образом, эта теорема является частным случаем теоремы Самнера — Лас Вергнаса при <tex>k = 2</tex>, за исключением тривиального случая <tex>n = 1</tex>.
[[Файл:all_connected_graphs_4_vertices.png|thumb|550px|center|Все связные неориентированные графы, состоящие из 4 вершин, с точностью до изоморфизма]]
}}

==См. также==
* [[Лапы и минимальные по включению барьеры в графе]]

== Источники информации ==
* [[wikipedia:en:Claw-free_graph#Matchings | Википедия {{---}} Claw-free graph]]
* [[wikipedia:ru:Граф_без_клешней#Паросочетания | Википедия {{---}} Граф без клешней]]
* ''David P. Sumner''. Graphs with 1-factors. — 1974. — Т. 42, вып. 1. — стр. 8—12

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

← Предыдущая		Версия 16:37, 4 сентября 2022
Строка 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 Майкл Наки].
−	\|}
−
	'''Теорема Самнера — Лас Вергнаса''' даёт достаточное условие для существования совершенного паросочетания в графах чётного порядка.		'''Теорема Самнера — Лас Вергнаса''' даёт достаточное условие для существования совершенного паросочетания в графах чётного порядка.

← Предыдущая		Версия 03:59, 1 сентября 2022
Строка 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 Майкл Наки].
		+	\|}
		+
	'''Теорема Самнера — Лас Вергнаса''' даёт достаточное условие для существования совершенного паросочетания в графах чётного порядка.		'''Теорема Самнера — Лас Вергнаса''' даёт достаточное условие для существования совершенного паросочетания в графах чётного порядка.

← Предыдущая		Версия 14:31, 9 января 2021
Строка 47:		Строка 47:

	==См. также==		==См. также==
		+	* [[ Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях ]]
		+	* [[ Теорема Татта о существовании полного паросочетания ]]
	* [[Лапы и минимальные по включению барьеры в графе]]		* [[Лапы и минимальные по включению барьеры в графе]]

@@ Строка 42: / Строка 42: @@
 Пусть <tex>G</tex> — связный граф чётного порядка <tex>2n</tex>, не содержащий лап. Тогда <tex>G</tex> содержит совершенное паросочетание.
 |proof=
-:Единственный связный граф порядка <tex>4</tex>, который не содержит совершенного паросочетания — это <tex>K_{1,3}</tex>. Таким образом, эта теорема является частным случаем теоремы Самнера — Лас Вергнаса при <tex>k = 2</tex>, за исключением тривиального случая <tex>n = 1</tex>.
+:Единственный связный граф порядка <tex>4</tex>, который не содержит совершенного паросочетания — это <tex>K_{1,3}</tex>. Таким образом, это утверждение является частным случаем теоремы Самнера — Лас Вергнаса при <tex>k = 2</tex>, за исключением тривиального случая <tex>n = 1</tex>.
 [[Файл:all_connected_graphs_4_vertices.png|thumb|550px|center|Все связные неориентированные графы, состоящие из 4 вершин, с точностью до изоморфизма]]
 }}