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

Материал из Викиконспекты
Перейти к: навигация, поиск
(WIP)
 
Строка 1: Строка 1:
 
'''Теорема Самнера — Лас Вергнаса''' даёт достаточное условие для существования совершенного паросочетания в графах чётного порядка.
 
'''Теорема Самнера — Лас Вергнаса''' даёт достаточное условие для существования совершенного паросочетания в графах чётного порядка.
−
 
  
 
==Подготовка к доказательству==
 
==Подготовка к доказательству==
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
'''Смежными листами''' (англ. ''coincident endpoints'') в неориентрированном графе называется такая пара вершин <tex>u, v</tex>, что <tex>\operatorname{deg}u = 1, \operatorname{deg}v = 1</tex>, а также имеющая общюю соседнюю вершину (или, другими словами, <tex>\rho(u, v) = 2</tex>).  
+
'''Смежными листами''' (англ. ''coincident endpoints'') в неориентрированном графе называется такая пара вершин <tex>x, y</tex>, что <tex>\operatorname{deg}x = 1, \operatorname{deg}y = 1</tex>, а также обе вершины имеют общюю смежную вершину (другими словами, расстояние между этими вершинами <tex>\rho(x, y) = 2</tex>).  
 
}}
 
}}
  
Строка 11: Строка 10:
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
−
Если <tex>G</tex> — связный граф, состоящий из <tex>n \geq 3</tex> вершин и не содержащий ''смежных листов'', то найдутся такие две '''смежные''' вершины <tex>u, v</tex>, что граф <tex>G \backslash \{u, v\}</tex> также будет связен.
+
Если <tex>G</tex> — связный граф, состоящий из <tex>n \geq 3</tex> вершин и не содержащий ''смежных листов'', то найдутся такие две '''смежные''' вершины <tex>x, y</tex>, что граф <tex>G \backslash \{x, y\}</tex> также будет связен.
 
|proof=
 
|proof=
 
:Лемма, очевидно выполняется для полных графов <tex>K_n</tex>. Таким образом, будем считать далее, что диаметр графа <tex>d \geq 2</tex>.
 
:Лемма, очевидно выполняется для полных графов <tex>K_n</tex>. Таким образом, будем считать далее, что диаметр графа <tex>d \geq 2</tex>.
−
:Пусть <tex>a, y</tex> — вершины графа <tex>G</tex>, находящиеся на расстоянии \rho(a, y) = d.
+
:Пусть <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>2</tex> до тех пор, пока находится хоть какой-то путь в остаточной сети.
+
:# Граф <tex>G^* \backslash A</tex> содержит только изолированные вершины. Тогда, так как граф не содержит смежных листов, то <tex>G^* \backslash A</tex> состоит из единственной вершины <tex>f</tex>. Если <tex>\operatorname{deg}y = 1</tex>, то <tex>f, y</tex> являлись бы смежными листами. Таким образом, <tex>y</tex> должен быть связан с вершиной из <tex>A</tex>. Следовательно, <tex>G \backslash \{f, x\}</tex> связен.
−
 
 
−
:То, что получится в конце, будет максимальным потоком. В случае целочисленной сети достаточно в качестве начального приближения взять нулевой поток, и не трудно видеть, что на каждой итерации (в том числе и последней) этот поток будет оставаться целочисленным, что и докажет требуемое.
 
 
}}
 
}}
−
 
  
 
==Теорема==
 
==Теорема==
−
Для начала докажем оригинальную версию теоремы, доказанную независимо Самнером (''Sumner'', 1974) и Лас Вергнасом (''Las Vergnas'', 1975).
+
Докажем оригинальную версию теоремы, доказанную независимо Самнером (''Sumner'', 1974) и Лас Вергнасом (''Las Vergnas'', 1975).
  
 
{{Теорема
 
{{Теорема
Строка 31: Строка 27:
 
Самнера — Лас Вергнаса
 
Самнера — Лас Вергнаса
 
|statement=
 
|statement=
−
Пусть <tex>G</tex> — связный граф порядка <tex>2n \geq 3</tex>, и существует число <tex>1 < k \leq n</tex> такое, что любой индуцированный связный подграф <tex>G</tex> порядка <tex>2k</tex> содержит совершенное паросочетание. Тогда <tex>G</tex> также содержит совершенное паросочетание.
+
Пусть <tex>G</tex> — связный граф порядка <tex>2n \geq 3</tex>, и <tex>1 < k \leq n</tex> такое число, что любой индуцированный связный подграф <tex>G</tex> порядка <tex>2k</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>1 < k \leq n</tex> такое число, что любой индуцированный связный подграф <tex>G</tex> порядка <tex>2k</tex> содержит совершенное паросочетание.
 +
:Случай <tex>k = n</tex> очевиден, поэтому можно считать, что <tex>k \leq n - 1</tex>.
 +
:Если граф содержит смежные листы <tex>a, b</tex>, то рассмотрим любой связный граф <tex>G^*</tex> порядка <tex>2k</tex>, содержащий эти вершины. Тогда хотя бы одна из вершин <tex>a, b</tex> будет не покрыта паросочетанием.
 +
:Таким образом, граф <tex>G</tex> не содержит смежных листов. Тогда из леммы следует, что существуют смежные вершины <tex>x, 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>).
 +
{{Теорема
 +
|statement=
 +
Пусть <tex>G</tex> — связный граф чётного порядка <tex>2n</tex>, не содержащий лап. Тогда <tex>G</tex> содержит совершенное паросочетание.
 
|proof=
 
|proof=
−
# Из [[Определение матроида|определения матроида]] (первой аксиомы) <tex>\varnothing \in I</tex>, где <tex>I</tex> {{---}} семейство независимых множеств матроида <tex>M</tex>. Откуда <tex>\varnothing \notin \mathfrak{C}</tex>.
+
[[Файл:all_connected_graphs_4_vertices.png|thumb|500px|center|Все связные неориентированные графы, состоящие из 4 вершин]]
−
# От противного. Из определения цикла: если <tex>C_1 \subset C_2</tex>, то <tex>C_1 \in I</tex>. Значит <tex>C_1 \notin \mathfrak{C}</tex>. Противоречие. Аналогично <tex>C_2 \nsubseteq C_1</tex>.
+
:Единственный связный граф порядка <tex>4</tex>, который не содержит совершенного паросочетания — это <tex>K_{1,3}</tex>. Таким образом, эта теорема — частный случай теоремы Самнера — Лас Вергнаса при <tex>k = 2</tex>, за исключением тривиального случая <tex>n = 1</tex>.
−
# От противного. Пусть <tex>D = (C_1 \cup C_2) \setminus p</tex> независимо.
 
−
#: Обозначим <tex>A = C_1 \cap C_2</tex>. Покажем, что <tex>|A| < |D|</tex>. Из предыдущего пункта очевидным образом следует, что <tex>|C_1 \setminus C_2| > 0</tex> и <tex>|C_2 \setminus C_1| > 0</tex>.
 
−
#: <tex>|D| = |C_1 \setminus C_2| + |C_2 \setminus C_1| + |A| - 1 \geqslant |A| + 1 + 1 - 1 = |A| + 1 > |A|.</tex>
 
−
#: Отсюда путем многократного применения третьей аксиомы матроидов получим <tex>\exists B: A \subset B</tex> и <tex>|B| = |D|</tex>, причем <tex>B</tex> {{---}} независимо.
 
−
#: Поскольку <tex>C_1</tex> {{---}} цикл, <tex>C_1 \nsubseteq B</tex>. Значит, найдется хотя бы один элемент в <tex>C_1 \setminus A</tex>, не лежащий в <tex>B</tex>.  Следовательно в <tex>B</tex> лежит не более чем <tex>|C_1 \setminus A| - 1</tex> элементов из этого множества. Аналогично в <tex>B</tex> лежит не более чем <tex>|C_2 \setminus A| - 1</tex> элементов из множества <tex>C_2 \setminus A</tex> .
 
−
#: Получаем: <tex>|B| \leqslant |A| + |C_1 \setminus A| - 1 + |C_2 \setminus A| - 1 = |C_1 \cup C_2| - 2 = |D| - 1</tex> .  А поскольку <tex>|B| = |D|</tex> получаем противоречие.  
 
 
}}
 
}}
  

Версия 14:02, 9 декабря 2020

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

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

Определение:
Смежными листами (англ. 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]G^* \backslash A[/math] состоит из единственной вершины [math]f[/math]. Если [math]\operatorname{deg}y = 1[/math], то [math]f, y[/math] являлись бы смежными листами. Таким образом, [math]y[/math] должен быть связан с вершиной из [math]A[/math]. Следовательно, [math]G \backslash \{f, x\}[/math] связен.
[math]\triangleleft[/math]

Теорема

Докажем оригинальную версию теоремы, доказанную независимо Самнером (Sumner, 1974) и Лас Вергнасом (Las Vergnas, 1975).

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

См. также

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теорема_Самнера_—_Лас_Вергнаса_(WIP)&oldid=75223»