Математика · объяснение и практика
Теорема Кёнига: паросочетание и покрытие всех рёбер
Строим минимальное вершинное покрытие двудольного графа по чередующейся достижимости и доказываем равенство его размера наибольшему паросочетанию.

В теме Доказательства и комбинаторные модели · Учебная карта
Главная мысль
В конечном двудольном графе размер наибольшего паросочетания равен наименьшему числу вершин, касающихся всех рёбер. Такое множество вершин называется вершинным покрытием. По наибольшему паросочетанию покрытие строится через достижимость по чередующимся направлениям.
Два разных способа выбрать объекты графа
Паросочетание выбирает рёбра без общих концов. Вершинное покрытие выбирает вершины: у каждого ребра хотя бы один конец должен оказаться выбранным. Не требуется покрывать каждую вершину, а изолированные вершины вообще не нужны покрытию. Это также не выбор рёбер, касающихся всех вершин, — у той задачи другое определение.
Любое покрытие содержит хотя бы столько вершин, сколько рёбер в любом паросочетании. Каждое выбранное ребро требует свой покрывающий конец, а разные рёбра паросочетания концами не делятся. Пока это лишь неравенство. Теорема Кёнига утверждает достижимость равенства именно для двудольного графа.
У треугольника наибольшее паросочетание имеет одно ребро, а покрытие требует две вершины. Поэтому условие двудольности нельзя убрать. Изолированные вершины равенству не мешают: их добавление не меняет ни число пар, ни необходимое покрытие.
Как получить покрытие по чередующейся достижимости
Пусть доли называются L и R, а M — наибольшее паросочетание. Начинаем из всех свободных вершин доли L. По невыбранным рёбрам идём из L в R, а по рёбрам M — из R в L. Обозначим достигнутые множества ZL и ZR. Свободная вершина R не может достигаться, иначе путь увеличил бы M.
Возьмём C=(L\ZL)∪ZR. Оно покрывает любое ребро. Действительно, непокрытое ребро должно было бы соединять достигнутую вершину L с недостигнутой R. Если ребро не входит в M, по нему можно продолжить поиск. Если входит, достигнутая занятая вершина L уже пришла по этому ребру от своего партнёра. Оба предположения дают противоречие.
Пример
В L находятся А, Б, В; в R — x,y. Рёбра: А−x, Б−x, Б−y, В−y. Для M={А−x,В−y} постройте покрытие.
Свободная Б достигает x и y, затем по выбранным рёбрам — А и В. Поэтому ZL={А,Б,В}, ZR={x,y}. Формула даёт покрытие {x,y} размера два. Две пары уже найдены, а две правые вершины покрывают все четыре ребра: обе оценки совпали. Нельзя получить три пары, поскольку справа только две вершины.
Почему найденное покрытие имеет точный размер
Все вершины ZR заняты, а их партнёры принадлежат ZL. У каждого ребра M достижимость его концов совпадает: из достигнутого правого конца сразу достигается левый, а достигнутый занятый левый имеет достигнутого партнёра. Поэтому C выбирает ровно один конец каждого ребра M.
Кроме того, свободные левые вершины входят в ZL по началу поиска и не попадают в C. Свободные правые вершины в ZR не попадают. Значит, в покрытии нет лишних вершин вне концов M, и |C|=|M|. Общая нижняя оценка уже доказана, следовательно, одновременно установлены минимум покрытия и максимум числа пар.
Если начать с произвольного паросочетания и встретить свободный правый конец, нужно сначала увеличить паросочетание. Тот же обход до завершения поиска максимума не даёт права объявлять записанную формулу минимальным покрытием. Свидетельство оптимальности требует и допустимого покрытия, и равенства его размера числу независимых пар.
От чтения к действию
А теперь — вы
Частые вопросы
Покрытие обязано содержать по вершине из каждой доли?
Нет. В примере всё покрытие лежит справа; это не нарушает требования к каждому ребру.
Может ли минимум покрытия быть неединственным?
Да. Теорема утверждает равенство размеров оптимумов, а не единственность набора выбранных вершин.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Паросочетание: как чередующийся путь увеличивает число пар
Увеличивающий путь в двудольном паросочетании: перестановка занятых назначений вместо жадного отказа свободной вершине.
Открыть темуПоток и разрез: как получить проверяемую верхнюю границу
Разрез сети как доказательство оптимальности: направленные ёмкости через границу, верхняя оценка потока и совпадение с допустимым решением.
Открыть тему