Теорема Самнера — Лас Вергнаса (WIP)

Материал из Викиконспекты
Версия от 12:28, 9 декабря 2020; Unreal.eugene (обсуждение | вклад) (WIP)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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


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

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


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

Лемма:
Если [math]G[/math] — связный граф, состоящий из [math]n \geq 3[/math] вершин и не содержащий смежных листов, то найдутся такие две смежные вершины [math]u, v[/math], что граф [math]G \backslash \{u, v\}[/math] также будет связен.
Доказательство:
[math]\triangleright[/math]
Лемма, очевидно выполняется для полных графов [math]K_n[/math]. Таким образом, будем считать далее, что диаметр графа [math]d \geq 2[/math].
Пусть [math]a, y[/math] — вершины графа [math]G[/math], находящиеся на расстоянии \rho(a, y) = d.
  1. В начале берем какой-нибудь поток за начальный (например, нулевой).
  2. В остаточной сети этого потока находим какой-нибудь путь из источника к стоку и увеличиваем поток на пропускную способность этого пути.
  3. Повторяем пункт [math]2[/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]
  1. Из определения матроида (первой аксиомы) [math]\varnothing \in I[/math], где [math]I[/math] — семейство независимых множеств матроида [math]M[/math]. Откуда [math]\varnothing \notin \mathfrak{C}[/math].
  2. От противного. Из определения цикла: если [math]C_1 \subset C_2[/math], то [math]C_1 \in I[/math]. Значит [math]C_1 \notin \mathfrak{C}[/math]. Противоречие. Аналогично [math]C_2 \nsubseteq C_1[/math].
  3. От противного. Пусть [math]D = (C_1 \cup C_2) \setminus p[/math] независимо.
    Обозначим [math]A = C_1 \cap C_2[/math]. Покажем, что [math]|A| \lt |D|[/math]. Из предыдущего пункта очевидным образом следует, что [math]|C_1 \setminus C_2| \gt 0[/math] и [math]|C_2 \setminus C_1| \gt 0[/math].
    [math]|D| = |C_1 \setminus C_2| + |C_2 \setminus C_1| + |A| - 1 \geqslant |A| + 1 + 1 - 1 = |A| + 1 \gt |A|.[/math]
    Отсюда путем многократного применения третьей аксиомы матроидов получим [math]\exists B: A \subset B[/math] и [math]|B| = |D|[/math], причем [math]B[/math] — независимо.
    Поскольку [math]C_1[/math] — цикл, [math]C_1 \nsubseteq B[/math]. Значит, найдется хотя бы один элемент в [math]C_1 \setminus A[/math], не лежащий в [math]B[/math]. Следовательно в [math]B[/math] лежит не более чем [math]|C_1 \setminus A| - 1[/math] элементов из этого множества. Аналогично в [math]B[/math] лежит не более чем [math]|C_2 \setminus A| - 1[/math] элементов из множества [math]C_2 \setminus A[/math] .
    Получаем: [math]|B| \leqslant |A| + |C_1 \setminus A| - 1 + |C_2 \setminus A| - 1 = |C_1 \cup C_2| - 2 = |D| - 1[/math] . А поскольку [math]|B| = |D|[/math] получаем противоречие.
[math]\triangleleft[/math]

См. также

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