Паросочетания в двудольном графе

Паросочетания

Паросочетанием в графе называется такое подмножество его рёбер, в котором никакая пара рёбер не смежна.

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

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

Алгоритм нахождения наибольшего паросочетания использует следующие понятия.

Назовём вершину в графе связанной, если она принадлежит паросочетанию, иначе вершину назовём свободной.

Цепь назовём последовательной, если в ней последовательно повторяются ребра, принадлежащие и не принадлежащие паросочетанию.

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

Алгоритм основан на этом утверждении. Строится последовательная цепь и описанной процедурой увеличивается число рёбер в паросочетании, пока это возможно.

ПримерПример. Рассмотрим граф, приведённый на рис 3.9. Выделим в нём последовательную цепь, например, 1,2,3,5,10,11,7,12,8,4, в которой рёбра (1,2), (3,5),(10,11),(7,12),(8,4) включены в паросочетание.

Для этой цепи ищем цепь, в которую пробуем включить свободные вершины 6 и 9 так, чтобы они были начальной и конечной вершинами цепи. Такая цепь находится: (9, 10, 11, 7, 12, 8, 4, 3, 5, 1, 2, 6). Значит, получаем новое паросочетание, в котором число рёбер на единицу больше первого. Так как это паросочетание содержит все вершины, оно является наибольшим. Решением будет множество {(9, 10), (11, 7), (12, 8), (4, 3), (5, 1), (2, 6)}.

Можно убедиться, что это решение не единственное.

Паросочетание называют совершенным, если в нём участвуют все вершины. Очевидно, что совершенное паросочетание, если оно в графе существует, будет и наибольшим.

Так как с каждым ребром связана пара вершин и рёбра в паросочетании не смежные, то с любым паросочетанием связано чётное число вершин. Значит, имеет место теорема:

ТеоремаНеобходимым условием существования в графе совершенного паросочетания является чётное число его ребер.

Задача нахождения максимального или наибольшего паросочетания в двудольном графе G =<AÈ B,U> , U ÊAxB называется задачей о назначениях.

Не теряя общности, можно предположить, что |A|=|B|. Если это не так, то всегда можно меньшее множество дополнить элементами, не связанными с другими элементами.

Будем решать следующую задачу: найти в двудольном графе максимальное совершенное паросочетание.

Рассмотрим задачу в следующей семантике. Множеству А сопоставляется множество работников, множеству В – множество работ, ребра взвешены числами (целыми и положительными), определяющими эффективность назначения работника на работу. Число работников равно числу работ. Нужно найти такое назначение, когда все работники назначены на работы и все работы заняты и при этом достигается максимальная эффективность использования работников.

Условие существования совершенного паросочетания в двудольном графе определяется теоремой Кёнига-Холла:

Совершенное паросочетание существует тогда и только тогда, когда для любого А’ ÍA имеет место |A’| £ |U(A’)|

Метод выделения максимального паросочетания заключается в следующем (этот метод в литературе называют венгерским).

Взвесим вершины графа весами х_i для вершин множества A и у_i для вершин множества B таким образом, чтобы условие х_i +у_i ³с_ij удовлетворялось для любого ребра. Если в решении оставлять только те ребра, для которых выполняется равенство

х_i +у_i =с_ij(*),

и обеспечить подбором х_iи у_i выполнение условия теоремы Кёнига-Холла, то при этом сумма с_ij в паросочетании (которое существует по теореме Кёнига-Холла) будет максимально возможной, сумма всех х_i и у_i – минимально возможной, так как первая сумма ограничивает вторую сверху, вторая сумма ограничивает первую снизу. В силу условия (*) при этом Sс_ij=S х_i+S у_i

Начинается расчет с того, что значению х_i приписывается maax с_ij по всем j, а у_i –нулевые значения.

Построим граф претендентов, содержащий только те ребра исходного графа, для которых выполняется равенство (*).Для графа претендентов проверяем условие теоремы Кёнига-Холла. Если находится подмножество А’, для которого условие теоремы не выполняется, то для каждого его элемента вес х_i уменьшим на единицу, а вес каждого элемента из U(A’) увеличим на единицу. Если появляются новые ребра, для которых справедливо условие (*), их вносят в претенденты и снова проверяют условия теоремы. Это продолжается, пока не будут выполнены условия теоремы Кёнига-Холла.

В графе претендентов решение находится путём перебора. При этом вначале для всех вершин, степень которых равна 1, то естьт.е. для которых назначения однозначны, производятся назначения, и соответствующие пары вершин из графа удаляются, что сокращает объём перебора.

3.5.6. Поток в транспортной сети

 

Транспортной сетью называют связный граф без контуров, в котором:

· существует единственная вершина x₀, из которой дуги только выходят, называемая входом сети;

· существует единственная вершина z, в которую дуги только заходят, называемая выходом сети;

· каждая дуга (i,j) взвешена неотрицательным целым числом с_ij, называемым пропускной способностью дуги.

Потоком в сети j называется целочисленная функция, заданная на дугах графа, такая, что:

· для любой дуги 0£j_ij £ с_ij;

· для любой вершины i, кроме входа и выхода сети, имеет место равенство
Sj_ij = Sj_ji,
jÎP jÎQ

 

где Р - множество вершин, связанных с вершиной i по исходящим, Q -по заходящим дугам.

Последнее равенство означает, что суммарный поток, входящий в вершину, равен суммарному потоку, выходящему из неё. Из этого равенства и из того, что в сети нет контуров, следует, что суммарный поток, исходящий из вершины x₀, равен суммарному потоку, заходящему в вершину z, то естьт.е. Sj_0j=Sj_zi=j. Эта величина называется величиной потока.

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

Назовем дугу насыщенной, если для нее величина потока равна пропускной способности дуги: j_ij=с_ij . Путь между вершинами x₀ и z назовём полным, если он содержит хотя бы одну насыщенную дугу. Поток назовем полным, если в нём любой путь полный.

Рассмотрим алгоритм решения этой задачи, предложенный Фордом и Фалкерсоном.

Алгоритм Форда и Фалкерсона.

Пункт 1. Зададим любой поток и доведем его до полного. Для этого перебираем все пути между входом и выходом сети и если некоторый путь неполон, то, увеличивая поток по нему, доводим его до полного.

Пункт 2. Проведем последовательную разметку графа:

• вершину x₀ пометим символом 0;
• если вершина х_i отмечена, то непомеченные вершины, связанные с ней по исходящим дугам, пометим как +i, если дуга не насыщена, и связанные по заходящим дугам как -i, если поток в дуге не равен нулю. ;

*· еЕсли в результате разметки будет помечен выход сети, то переходим к пункту 3, иначе - конец алгоритма.

Пункт 3. Разметка выделяет цепь между входом и выходом сети. Будем двигаться по ней от входа к выходу и изменять поток в проходимых дугах по правилу: если направление движения совпадает с направлением дуги, то значение потока увеличим на единицу, если противоположен, то уменьшим на единицу. Так как для дуги цепи, исходящей из входа, и дуги, заходящей в выход сети, направление дуги и направление движения всегда совпадают, то в результате величина потока увеличится.

После этого переходим к пункту 2.

Можно показать, что в результате такого изменения потока условия, сформулированные в определении потока, нарушены не будут. Действительно, для отмеченной вершины x возможные сочетания инцидентных дуг к другим отмеченным вершинам показаны на рис.3.10.

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

ПримерПример. Рассмотрим транспортную сеть, приведенную на рис 3.11. Здесь цифрами в скобках отмечена величина потока по дугам, без скобок - пропускные способности. Нетрудно убедиться, что поток является полным, то естьт.е. по каждому пути его увеличить нельзя. Жирными линиями выделена цепь, полученная после разметки графа в соответствии с п. 3 алгоритма. По этому пути поток по дугам (х1,х4), (х4,х6),(х2,х7) и (х7,х8) увеличится на единицу, поток по дуге (х2,х6) уменьшится на единицу, общий поток увеличится на единицу.

Повторная разметка графа невозможна, значит, полученный поток максимален.

Разобьем множество вершин Асети на два подмножества, А1 и А2, при котором в первое подмножество включен вход сети, во второе - её выход. Множество дуг, начинающихся в А1 и заканчивающихся в А2, называется разрезом сети, а сумма пропускных способностей этих дуг называется величиной разреза.

Разрез, величина которого минимальна, называется минимальным разрезом.

Для проверки того, является ли поток максимальным, служит теорема Форда и Фалкерсона: максимальный поток в сети равен величине ее минимального разреза.

Теорема позволяет проверить, является ли поток максимальным. Если находится разрез, в котором все дуги насыщены, то величина потока будет максимальной.

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