П АРОСОЧЕТАНИЯ В ДВУДОЛЬНЫХ ГРАФАХ

Подмножество М ребер графа G=(V,E) называется паросочетанием, если никакие два ребра из М не имеют общей вершины. Паросочетание называется наибольшим, если оно содержит максимально возможное число ребер. Если наибольшее паросочетание покрывает все вершины графа, то оно называется совершенным.

З АДАЧА О ПАРОСОЧЕТАНИИ СОСТОИТ В НАХОЖДЕНИИ НАИБОЛЬШЕГО ПАРОСОЧЕТАНИЯ. Особенно часто она возникает для двудольных графов, множество вершин которых разбивается на 2 непересекающихся подмножества V 1 и V 2, а любое ребро имеет одним своим концом вершину из V 1, а другим – из V 2. Задача имеет многочисленные интерпретации и приложения. Укажем некоторые из них. Если V 1 - множество юношей, V 2 - множество девушек, желающих вступить в брак, а ребро в графе соответствует взаимному согласию к вступлению в брак, то задача о паросочетаниях является задачей о заключении максимального числа счастливых браков.

Если V 1 - множество лиц, желающих получить работу, V 2 - множество вакантных мест, и ребро в графе обозначает способность определенного лица выполнить данную работу, то задача о паросочетании становится задачей о трудоустройстве. Множество V 1 может быть также множеством подмножеств некоторого множества, а V 2 - множеством элементов этого же множества. Ребро в этом случае соответствует вхождению элемента в подмножество. Тогда задача о паросочетании становится задачей о выборе различных представителей. Пусть, например, в Думе имеется ряд комитетов, причем член Думы может состоять в нескольких комитетах, но возглавлять не более одного. Тогда задачу выбора председателя в каждом комитете можно рассматривать как задачу о системе различных представителей.

Универсальным подходом, позволяющим строить эффективные алгоритмы для задачи о паросочетании, является подход, основанный на идее чередующейся цепи. Пусть в графе имеется некоторое паросочетание. Если удастся найти цепь, первая и последняя вершина которой не покрыты паросочетанием, а ребра чередуются, попеременно то не входя, то входя в паросочетание, то мощность паросочетания можно нарастить на единицу. Для этого достаточно все ребра цепи, не входящие в паросочетание, включить в него, а все входящие в паросочетание ребра – исключить из паросочетания.

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