Лемма Бержа

В этой статье мы докажем одну лемму, ключевую для алгоритма нахождения паросочетания в двудольном графе. Но перед этим потребуется ввести ещё несколько понятий.

Цепью длины $k$ назовём некоторый простой путь (т.е. не содержащий повторяющихся вершин или рёбер), содержащий ровно $k$ рёбер.

Чередующейся цепью относительно некоторого паросочетания назовём простой путь длины $k$ в котором рёбра поочередно принадлежат/не принадлежат паросочетанию.

Увеличивающей цепью относительно некоторого паросочетания назовём чередующуюся цепь, у которой начальная и конечная вершины не принадлежат паросочетанию.

Как подсказывает название, с помощью увеличивающей цепи можно увеличить мощность паросочетания на единицу. Для этого можно взять такую цепь и провести чередование: убрать из паросочетания все рёбра, принадлежащие цепи, и вместо них добавить все остальные ребра цепи.

Всего в увеличивающей цепи нечетное число рёбер, а первое и последнее были не в паросочетании. После чередования каждая затронутая вершина будет соединена ровно с одной из другой доли. Значит, после чередования паросочетание осталось корректным, а его мощность увеличилась ровно на единицу.

В примере выше добавятся синие рёбра $(1, 8)$, $(3, 7)$ и $(4, 6)$, а удалятся красные $(3, 6)$ и $(4, 8)$. С ребром $(2, 5)$ ничего не случится — оно не в увеличивающей цепи. Таким образом, размер паросочетания увеличится на единицу.

Раз чередованием увеличивающей цепи можно увеличить мощность паросочетания на единицу, то у максимального паросочетания увеличивающих цепей быть не должно. Оказывается, обратное тоже верно.

#Теорема Бержа

Теорема. Паросочетание без увеличивающих цепей является максимальным.

Доказательство проведём от противного: пусть есть два паросочетания вершин $|A| \leq |B|$, и для $A$ нет увеличивающих путей. Покажем, как найти этот путь и увеличить $A$ на единицу.

Раскрасим ребра из паросочетания, соответствующего $A$ в красный цвет, $B$ — в синий, а ребра из обоих паросочетаний — в пурпурный. Рассмотрим теперь граф из только красных и синих ребер. Так как это фактически симметричная разность двух паросочетаний, у каждой вершины будет не более 2 смежных ребер. Значит, любая компонента связности в нём представляет собой либо путь, либо цикл, состоящий из чередующихся красных и синих ребер. В любом цикле будет равное число красных и синих рёбер, а так как всего синих рёбер больше, то должен существовать путь, начинающийся и оканчивающийся синим ребром — он и будет увеличивающей цепью для $A$, а значит $A$ не максимальное, и мы получили противоречие.