Паросочетания и задача о назначениях

Определения Задан граф G = (V, E). Подмн. ребер M E является паросочетанием в G, если v V инцидентно 1 ребра из M. П., покрывающее все вер. графа, наз. совершенным. Вершинным покрытием графа наз. такое подмн. вершин R V: ребро e E инцидентно 1 вершине из R. Двойственная взаимосвязь: пар. M и вер. п. R |M| |R|. Действительно, пусть M = {(i 1, j 1 ), …, (i k, j k )} паросочетание. Тогда в вер. покрытии R должна быть хотя бы одна из вершин каждой пары {i s, j s }, s = 1, …, k. |R| k = |M|.

Пример

Постановка задачи и определения max{|M| : M паросочетание в G} (1) Назовем путь P=v 0,e 1,v 1,e 2,...,e p,v p (v i V, e j E) чередующимся относительно паросочетания M, если: 1) нечетные ребра e 1,e 3,...,e odd M; 2) четные ребра e 2,e 4,...,e even M; 3) вершина v 0 не инцидентна ( ) паросочетанию M. Чередующийся путь наз. аугментальным (увеличивающим), если для него доп.: 4) количество ребер p нечетно, и вершина v p M v0v0 v1v1 v2v2 v3v3 v4v4 v5v5

Аугментальный путь Лемма. Пусть задано п. M и аугментальный путь P. Тогда симметричная разность M =(M P)\(M P) является паросочетанием мощности |M |>|M|. Доказательство. Т.к. v 0,v p M и путь P чередующийся, то M паросочетание. А т.к. p нечетно, то |P (E\M)|=|P M|+1. |M |=|M|+1.

Max паросочетания Лемма. Если в графе не аугментального относительно M пути, то M является max паросочетанием. Доказательство. Предположим противное: M не max п. Тогда п. M : |M |>|M|. Рассмотрим граф с ребрами (M M )\(M M ). Степень каждой вершины этого графа может быть равна 0,1,2. любая связная компонента этого графа путь или цикл. В любом цикле ребра из M и M чередуются и,, цикл имеет четное количество ребер и содержит одинаковое количество ребер из M и M. Т.к. |M |>|M|, то путь, содержащий > ребер из M, чем из M, причем этот путь содержит нечетное число ребер и потому является аугментальным. M M (M M )\(M M )

Max паросочетание в двудольном графе G=(V 1,V 2,E), V=V 1 V 2. Имеется нек. п. M. Нужно найти либо ауг. путь, либо показать, что такого пути нет, и значит, M max. Алг. начинает работу с пометки в-н в V 1 M. 1-е ребро чер. пути M, и все ребра, инц. помеченным в. из V 1, включаются в строящиеся пути. Конечные в. таких ребер, V 2, получают метки. 2-е ребро чер. пути M, и все ребра из M, инц. помеченным в. из V 2, включаются в чер. пути. Непом. в. из V 1, кот. являются конц. для чет. ребер, также помечаются. И т.д. Пометка вершин прекращается, когда либо помеченная вершина из V 2 M, значит, найден аугментальный путь, либо ни 1 в. > не может быть помечена, и значит, аугментального пути не.

Алгоритм Шаг 0. Имеем п. M. Все в. не помечены и не просмотрены. Шаг 1. (Пометка вершин) Приписать метку каж. непом. и M в. из V Если нет не просм. в., то - на шаг 3. Иначе, выбрать пом. и не просм. в. i. Если i V 1, то - на шаг 1.2. Если i V 2, то - на шаг (Просмотр помеч. в. i V 1 ). (i,j) M если j V 2 не помеч., то приписать j метку i. Теперь i просмотрена. На шаг (Просмотр помеч. в. i V 2 ). Если i M, то - на шаг 2. В прот. сл., (j,i) M если j V 1 не помеч., то приписать j метку i. Теперь i просмотрена. На шаг 1.1. Шаг 2. (Аугментация). Аугм. путь P найден. Использовать метки, начиная с j V 2, для восстановления этого пути. Положить M=(M P)\(M P). Удалить все метки. На шаг 1. Шаг 3. (Не аугм. пути). Стоп.

Корректность алгоритма Пусть после остановки алгоритма: мн. помеченных вершин мн. не помеченных вершин Теорема. После остановки алгоритма 1) мн.является вер. покрытием гр. G; 2) |M| = |R|, и п. M max. Доказательство. 1) Т.к. на шаге 1.2 не удается пометить ни 1 в. мн. V 2, то не ребер из в мн. покрывает все ребра графа. 2) Т.к. аугм. пути нет, то каж. в. из мн. инц. ребру e M с другим концом в вершине из множестваКаж. в. мн. инц. р. e M, т.к. иначе она была бы помечена на шаге 1.0 сим.. Др. в. р. e т.к. в прот. сл. она была бы помечена на шаге 1.2. Но |R| |M| |R| = |M| доли V i

Пример Начальное п. M = {(3, 8), (5, 10)} (жирные ребра) * * * * 2 8 M={(1,8),(3,7),(4,10),(5,9)} R = {3,4,5,8} M={(,8),(5,10)}}

Паросочетание max веса Взвешенный граф G=(V 1,V 2,E), каж. р. e E приписан вес c e. Требуется найти паросочетание max веса. Из свойства абсолютной унимодулярности для построения паросочетания max веса достаточно решить след. задачу ЛП где (i)={e E : e=(i, j), j V} – мн. ребер, инц. в. i.

Задача о назначениях Если |V 1 |=|V 2 |=n и требуется найти совершенное паросочетание max веса, то получаем задачу о назначениях: u i +v j c ij, i,j = 1, …, n. Двойственная задача: ПЗ ДЗ

Свойства задачи Лемма. изн. ц.ф. z ПЗ с весами c ij отличается от зн. функционала этой задачи с весамина постоянную величину. Доказательство. доп. решения ПЗ имеем: разница функционалов равна константе Следствие. Решение ПЗ с весами c ij opt оно opt для з. с весами

Свойства задачи Лемма. Если для u,v R n и x B n n выполняются условия: i,j = 1, …, n; 1) 2) x ij =1 только в случае, когда то решение x opt для ПЗ, и opt зн. ц.ф. равно Доказательство. Т.к. i,j, то По условию 2) зн. функционала на решении x равно оно opt. Из следствия opt решения x и для задачи с весами c ij, и функционал на нем равен Замечание. В лемме представлена связь решений двойственных задач. 1) – это требование доп. двойственных переменных u и v. 2) – это условие дополняющей нежесткости.

Прямо-двойственный метод Полный 2-дольный графа G=(V 1,V 2,E), V 1 ={1,...,n} и V 2 ={1,...,n }. Во время работы алг., двойственные переменные u и v всегда остаются допустимыми, т.е. В графе ищем max паросочетание. Если его мощность = n, то стоп. Иначе, на двойственном шаге меняем значения двойственных переменных.

Алгоритм Шаг 0. Пусть u, v нач. зн. дв. переменных и Найти max п. M* в графе Если |M*|=n, то M* – opt реш. задачи о назначениях. В прот. сл. запомнить M=M*, а также метки вершин мн.и на шаг 2. Шаг 1. Имеем мн.п. M и мн. пом. вершин Используя имеющиеся метки вершин и п. M, построить max п. M*. Если |M*| = n, то M* – opt реш. задачи о назначениях, алгоритм останавливается. В прот. сл. запомнить M=M* и мн. Шаг 2. (Двойственный шаг). Изменить зн. дв. пер., положив: u i =u i –, v j =v j +, На шаг 1.

Утверждения Лемма. После вып. шага 1 справедливо неравенство Лемма. На двойственном шаге > 0. Лемма. После изменения зн. дв. переменных, получаем: и новое решение дв. допустимо.

Утверждения Следствие. Зн. ц.ф. ДЗ в рез. изменения зн. дв. пер-х на шаге 2 уменьшится на Следствие. В результате дв. шага величина увеличивается. Лемма. Приведенный алг. построения opt решения для задачи о назначениях имеет трудоемкость O(n 4 ). Доказательство. Т.к. в рез. шага 2 1 ребро добавляется в мн., то общее число дв. шагов величиной O(n 2 ). Трудоемкость шага 2 = O(|E|). Сложность шага 1 также ограничена величиной O(|E|).

Пример Пусть 1 доп. дв. решение: u 1 =(0,0,0,0), v 1 =(27,19,12,8) и Во 2 строке мат. все элементы < 0 u 2 = (0, 2, 0, 0), v 2 = (27, 19, 12, 8) и w = 64

Пример

Пример u = (0, 4, 0, 2) v = (27, 19, 14, 8) w = 62

Задача о паросочетании max веса в 2-дольном графе Сведение задачи о паросочетании max веса в 2-дольном графе G = (V 1, V 2, E) к задаче о назначениях осуществим след. образом. Пусть |V 1 | = |V 2 | + a, a > 0. Добавим a вершин в мн. V 2 и дополним граф до полного 2-дольного графа G с одинаковым количеством вершин в обеих долях, положив веса добавленных ребер = 0. Применим алг. для решения задачи о назначениях для графа G. Ребра, вошедшие в opt решение и имеющие > 0 веса, определяют паросочетание max веса в исх. 2-дольном графе G.

Транспортная задача и Венгерский метод (Harold Kuhn, 1955) One of the first algorithms of CO I heard about was the Hungarian method which has been viewed by many as a prototype of algorithm design and efficiency. Harold Kuhn presented it in 1955 in [3]. Having used ideas and results of J. Egerv´ary and D. K˝onig, he gave his algorithm (generously) the name Hungarian method.