Теорема Самнера — Лас Вергнаса даёт достаточное условие для существования совершенного паросочетания в графах чётного порядка.
Подготовка к доказательству
| Определение: |
| Смежными листами (англ. 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.
- В начале берем какой-нибудь поток за начальный (например, нулевой).
- В остаточной сети этого потока находим какой-нибудь путь из источника к стоку и увеличиваем поток на пропускную способность этого пути.
- Повторяем пункт [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] |
- Из определения матроида (первой аксиомы) [math]\varnothing \in I[/math], где [math]I[/math] — семейство независимых множеств матроида [math]M[/math]. Откуда [math]\varnothing \notin \mathfrak{C}[/math].
- От противного. Из определения цикла: если [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].
- От противного. Пусть [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] |
См. также
Источники информации
