Рассмотрим семейство подмножеств S₁, …, Sₙ конечного множества X. Когда из Sᵢ можно выбрать по элементу так, чтобы выбранные элементы были различны? Естественно, должно выполняться следующее:
Условие Холла:
объединение любых k множеств семейства содержит не менее k элементов.
В задаче 8 мы докажем Лемму Холла: условие Холла не только необходимо, но и достаточно.
Построим двудольный граф G = (A ∪ B, E): вершины A отвечают множествам Sᵢ, вершины B элементам X, ребро проводится если элемент принадлежит множеству.
Определение.
Рассмотрим двудольный граф G.
Паросочетание в G — множество рёбер без общих концов.
Вершинное покрытие — множество вершин C ⊆ A ∪ B, содержащее хотя бы один конец каждого ребра.
Теперь можно забыть про подмножества и сформулировать задачу для произвольного двудольного графа.
1. а) Переформулируйте задачу о выборе различных представителей в терминах паросочетаний.
б) Переформулируйте условие Холла в терминах покрытий и докажите, что оно необходимо.
Решение (а)
Набор различных представителей — паросочетание, покрывающее A.
Решение (б)
Условие Холла на языке графа: |N(S)| ≥ |S| для всякого S ⊆ A. Эквивалентность с покрытиями: если τ < |A|, покрытие C с |C| < |A| оставляет S = A \ C с |N(S)| ≤ |C ∩ B| = |C| − |C ∩ A| ≤ |C| − (|A| − |S|), откуда |N(S)| < |S|. Необходимость: если M покрывает A, то рёбра M из S ведут в |S| различных вершин N(S), значит |N(S)| ≥ |S|.
Обозначим за ν(G) размер максимального паросочетания, за τ(G) — минимального вершинного покрытия.
2. а) Докажите, что ν(G) ≤ τ(G) для любого графа.
б) Приведите пример графа, в котором ν(G) < τ(G).
Решение (а)
Каждое ребро M покрыто отдельной вершиной C, значит |C| ≥ |M| и τ ≥ ν.
Решение (б)
Треугольник C₃: ν = 1, τ = 2.
В задачах 3–7 мы докажем, что в двудольном графе ν(G) = τ(G), и выведем из этого Лемму Холла.
Определение.
Паросочетание M и вершинное покрытие C согласованны, если из каждого ребра M ровно один конец лежит в C. Дефектом пары (M, C) называется число f = |C| − |M|.
3. Покажите, что дефект равен числу свободных вершин в C.
Решение
Каждое ребро M вносит в C ровно одну вершину (по согласованности): вклад |M|. Остальные вершины C — свободные. Значит f = |C| − |M| = число свободных вершин в C.
4. В интерактивной модели ниже можно менять паросочетание (клик по ребру) и покрытие (клик по вершине). Уменьшите дефект пары, изменив только паросочетание или только покрытие. Постарайтесь изменить как можно меньше рёбер или вершин.
M — паросочетание
C — покрытие
(M, C) согласована
Дефект: f =
Добавление ребра или удаление вершины запускает цепную реакцию перестроек. Если она останавливается, получается новая согласованная пара с меньшим дефектом. Формализуем эти операции.
Рассмотрим путь в G нечётной длины, рёбра которого поочерёдно принадлежат M̄ и M, вершины чередуются между C и V \ C, а оба конца свободны. Положим MP = M △ E(P).
Рассмотрим независимое подмножество S ⊆ C такое, что каждое M̄-ребро из S в V \ C продолжается M-ребром обратно в S. Положим CS = (C \ S) ∪ {M-партнёры вершин S}.
5. Покажите, что обе операции дают согласованную пару. Как меняется дефект?
Решение (операция 1)
MP — паросочетание, |MP| = |M| + 1 (на P на одно M̄-ребро больше). Новые MP-рёбра (M̄-рёбра P) имеют один конец в C, другой вне C (чередование вершин). C не изменилось. Дефект: f − 1.
Решение (операция 2)
В каждом M-ребре с концом s ∈ S представитель сменился на M-партнёра; свободные вершины S удалены. |CS| = |C| − k, где k — число свободных вершин в S. Покрытие: ребро sv, s ∈ S, v ∉ C. Если sv ∈ M: v = M-партнёр s, v ∈ CS. Если sv ∈ M̄: по условию ∃w ∈ S с vw ∈ M, v ∈ CS. Рёбер внутри S нет (S независимо). Дефект: f − k.
6. а) Докажите, что для согласованной пары с f > 0 применима одна из операций, уменьшающая дефект.
Указание
Рассмотрите множество вершин, достижимых из свободной вершины по чередующимся путям.
б) Лемма Берже. Паросочетание максимально тогда и только тогда, когда к нему не применима операция 1.
Решение (а)
Пусть v₀ ∈ C — свободная. Рассмотрим Z — множество вершин, достижимых из v₀ по путям с чередованием рёбер (M̄, M, …) и вершин (C, V\C, …). Положим S = Z ∩ C.
S независимо (Z ∩ C лежит в одной доле по двудольности и чередованию). Условие операции 2: M̄-ребро sv, s ∈ S, v ∉ C ⟹ v ∈ Z. Если v покрыта M-ребром vw ⟹ w ∈ Z ∩ C = S. Условие выполнено.
Если v свободна ⟹ путь из v₀ в v — допустимый для операции 1.
Итого: нет свободных в Z \ C → операция 2 (k ≥ 1); есть → операция 1.
Решение (б)
⟹: если допустимый путь P существует, M △ E(P) — паросочетание размера |M| + 1.
⟸: допустимых путей нет. Берём согласованную пару (M, C). Если f > 0, по (а) применима одна из операций. Операция 1 невозможна. Значит применима операция 2, уменьшающая дефект. Повторяем, пока f = 0. Тогда |M| = |C| ≥ τ ≥ ν ≥ |M|, M максимально.
7.Теорема Кёнига. Докажите, что в двудольном графе выполняется ν(G) = τ(G).
Решение
ν ≤ τ очевидно. Согласованные пары существуют (M = ∅, C = A). Среди всех согласованных пар выберем пару с наименьшим дефектом. Если f > 0, по задаче 6а дефект можно уменьшить — противоречие. Значит f = 0, и τ ≤ |C| = |M| ≤ ν.
8. Для S ⊆ A обозначим N(S) — множество вершин B, смежных хотя бы с одной вершиной из S.
а) Докажите, что τ(G) = |A| − maxS⊆A(|S| − |N(S)|).
б) Докажите, что если |N(S)| ≥ |S| для всякого S ⊆ A, то существует паросочетание, покрывающее A.
в) Лемма Холла. Если условие Холла выполняется, то существует паросочетание, покрывающее A.
Решение (а)
Покрытие C оптимально при C = (A \ S) ∪ N(S). Минимальное: τ = minS⊆A(|A \ S| + |N(S)|) = |A| − maxS⊆A(|S| − |N(S)|).
Решение (б)
Если |N(S)| ≥ |S| для всех S ⊆ A, то max(|S| − |N(S)|) = 0, τ = |A|. По Кёнигу ν = τ = |A|.
Решение (в)
Условие Холла: |N(S)| ≥ |S| для всякого S ⊆ A (задача 1б). Частный случай (б).
9. Клетки доски n × n покрашены в чёрный и белый, причём в каждой строке и каждом столбце закрашено r клеток. Докажите, что на закрашенные клетки можно поставить n ладей, чтобы они не били друг друга.
Решение
Двудольный граф: A = строки, B = столбцы, ребро (i, j) ⟺ клетка (i, j) закрашена. Каждая вершина имеет степень r. Для S ⊆ A из S выходит r|S| рёбер, каждая вершина B принимает ≤ r, значит |N(S)| ≥ |S|. По лемме Холла существует паросочетание, покрывающее A.
10*. Рассмотрим множество X из n элементов.
а) Докажите, что все подмножества X можно разбить на C(n, ⌊n/2⌋) последовательностей, в которых каждое следующее подмножество содержит предыдущее.
б) Какое наибольшее число подмножеств X можно выбрать, чтобы ни одно из них не содержалось в другом?
в) Функция f из подмножеств X в {0, 1} монотонна, если из Y ⊆ Z следует f(Y) ≤ f(Z). Докажите, что
2 + 2m < число монотонных функций < 2 + nm, где m = C(n, ⌊n/2⌋).
Решение (а)
Разобьём подмножества на слои Lᵢ = {подмножества размера i}. Для i < n/2 строим паросочетание Lᵢ → Lᵢ₊₁: каждая вершина Lᵢ имеет n − i соседей в Lᵢ₊₁, каждая вершина Lᵢ₊₁ имеет i + 1 сосед в Lᵢ. Условие Холла: k вершин из Lᵢ инцидентны k(n − i) рёбрам; если соседей менее k, то рёбер ≤ (k − 1)(i + 1) < k(n − i). Аналогично для i ≥ n/2. Склеивая, получаем C(n, ⌊n/2⌋) цепей.
Решение (б)
Антицепь пересекает каждую цепь не более чем в одном элементе: |антицепь| ≤ m. Подмножества размера ⌊n/2⌋ дают антицепь размера m.
Решение (в)
Нижняя оценка: положим f = 0 на слоях ниже среднего, f = 1 выше, на среднем — произвольно: 2m нeконстантных функций + 2 константы. Верхняя оценка: неконстантная f на цепи из ≤ n + 1 вершин определяется моментом переключения с 0 на 1: не более n вариантов на цепь. Итого не более nm + 2.
11.Перманент квадратной матрицы A = (aij) размера n × n — это число per A = ∑σ∈Sn a1σ₁ · a2σ₂ · … · anσₙ. Докажите, что перманент неотрицательной матрицы равен нулю тогда и только тогда, когда найдутся k строк и n − k + 1 столбцов, на пересечении которых все элементы нулевые.
Решение
Заменим ненулевые элементы на 1. per A = 0 ⟺ ν < n ⟺ (Кёниг) τ < n ⟺ ∃ покрытие C, |C| < n. Положим S = A \ C (k непокрытых строк), T = B \ C (непокрытые столбцы). |T| = n − |C ∩ B| ≥ n − |C| + |C ∩ A| = n − |C| + (n − k) ≥ n − k + 1. Рёбра между S и T отсутствуют (ни один конец не покрыт) = на пересечении k строк и ≥ n − k + 1 столбцов все нули.