31
правка
Изменения
WIP
'''Теорема Самнера — Лас Вергнаса''' даёт достаточное условие для существования совершенного паросочетания в графах чётного порядка.
==Подготовка к доказательству==
{{Определение
|definition=
'''Смежными листами''' (англ. ''coincident endpoints'') в неориентрированном графе называется такая пара вершин <tex>u, v</tex>, что <tex>\operatorname{deg}u = 1, \operatorname{deg}v = 1</tex>, а также имеющая общюю соседнюю вершину (или, другими словами, <tex>\rho(u, v) = 2</tex>).
}}
Для доказательства основной теоремы потребуется доказать вспомогательную лемму:
{{Лемма
|statement=
Если <tex>G</tex> — связный граф, состоящий из <tex>n \geq 3</tex> вершин и не содержащий ''смежных листов'', то найдутся такие две '''смежные''' вершины <tex>u, v</tex>, что граф <tex>G \backslash \{u, v\}</tex> также будет связен.
|proof=
:Лемма, очевидно выполняется для полных графов <tex>K_n</tex>. Таким образом, будем считать далее, что диаметр графа <tex>d \geq 2</tex>.
:Пусть <tex>a, y</tex> — вершины графа <tex>G</tex>, находящиеся на расстоянии \rho(a, y) = d.
:# В начале берем какой-нибудь поток за начальный (например, нулевой).
:# В остаточной сети этого потока находим какой-нибудь путь из источника к стоку и увеличиваем поток на пропускную способность этого пути.
:# Повторяем пункт <tex>2</tex> до тех пор, пока находится хоть какой-то путь в остаточной сети.
:То, что получится в конце, будет максимальным потоком. В случае целочисленной сети достаточно в качестве начального приближения взять нулевой поток, и не трудно видеть, что на каждой итерации (в том числе и последней) этот поток будет оставаться целочисленным, что и докажет требуемое.
}}
==Теорема==
Для начала докажем оригинальную версию теоремы, доказанную независимо Самнером (''Sumner'', 1974) и Лас Вергнасом (''Las Vergnas'', 1975).
{{Теорема
|about=
Самнера — Лас Вергнаса
|statement=
Пусть <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>\varnothing \in I</tex>, где <tex>I</tex> {{---}} семейство независимых множеств матроида <tex>M</tex>. Откуда <tex>\varnothing \notin \mathfrak{C}</tex>.
# От противного. Из определения цикла: если <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>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> получаем противоречие.
}}
==См. также==
* [[Лапы и минимальные по включению барьеры в графе]]
== Источники информации ==
* [[wikipedia:en:Claw-free_graph#Matchings | Википедия {{---}} Claw-free graph]]
* [[wikipedia:ru:Граф_без_клешней#Паросочетания | Википедия {{---}} Граф без клешней]]
* ''David P. Sumner''. Graphs with 1-factors. — 1974. — Т. 42, вып. 1. — стр. 8—12
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]
==Подготовка к доказательству==
{{Определение
|definition=
'''Смежными листами''' (англ. ''coincident endpoints'') в неориентрированном графе называется такая пара вершин <tex>u, v</tex>, что <tex>\operatorname{deg}u = 1, \operatorname{deg}v = 1</tex>, а также имеющая общюю соседнюю вершину (или, другими словами, <tex>\rho(u, v) = 2</tex>).
}}
Для доказательства основной теоремы потребуется доказать вспомогательную лемму:
{{Лемма
|statement=
Если <tex>G</tex> — связный граф, состоящий из <tex>n \geq 3</tex> вершин и не содержащий ''смежных листов'', то найдутся такие две '''смежные''' вершины <tex>u, v</tex>, что граф <tex>G \backslash \{u, v\}</tex> также будет связен.
|proof=
:Лемма, очевидно выполняется для полных графов <tex>K_n</tex>. Таким образом, будем считать далее, что диаметр графа <tex>d \geq 2</tex>.
:Пусть <tex>a, y</tex> — вершины графа <tex>G</tex>, находящиеся на расстоянии \rho(a, y) = d.
:# В начале берем какой-нибудь поток за начальный (например, нулевой).
:# В остаточной сети этого потока находим какой-нибудь путь из источника к стоку и увеличиваем поток на пропускную способность этого пути.
:# Повторяем пункт <tex>2</tex> до тех пор, пока находится хоть какой-то путь в остаточной сети.
:То, что получится в конце, будет максимальным потоком. В случае целочисленной сети достаточно в качестве начального приближения взять нулевой поток, и не трудно видеть, что на каждой итерации (в том числе и последней) этот поток будет оставаться целочисленным, что и докажет требуемое.
}}
==Теорема==
Для начала докажем оригинальную версию теоремы, доказанную независимо Самнером (''Sumner'', 1974) и Лас Вергнасом (''Las Vergnas'', 1975).
{{Теорема
|about=
Самнера — Лас Вергнаса
|statement=
Пусть <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>\varnothing \in I</tex>, где <tex>I</tex> {{---}} семейство независимых множеств матроида <tex>M</tex>. Откуда <tex>\varnothing \notin \mathfrak{C}</tex>.
# От противного. Из определения цикла: если <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>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> получаем противоречие.
}}
==См. также==
* [[Лапы и минимальные по включению барьеры в графе]]
== Источники информации ==
* [[wikipedia:en:Claw-free_graph#Matchings | Википедия {{---}} Claw-free graph]]
* [[wikipedia:ru:Граф_без_клешней#Паросочетания | Википедия {{---}} Граф без клешней]]
* ''David P. Sumner''. Graphs with 1-factors. — 1974. — Т. 42, вып. 1. — стр. 8—12
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]
