Цветков, Максим Сергеевич
- 1 year ago
- 0
- 0
Алгоритм сжатия цветков ( англ. Blossom algorithm ) — алгоритм в теории графов для построения наибольших паросочетаний на графах. Алгоритм разработал Джек Эдмондс в 1961 году и опубликовал в 1965 году . Если дан граф G =( V , E ) общего вида, алгоритм находит паросочетание M такое, что каждая вершина из V инцидентна не более чем одному ребру из M и | M | максимально. Паросочетание строится путём итеративного улучшения начального пустого паросочетания вдоль увеличивающих путей графа. В отличие от двудольного паросочетания ключевой новой идеей было сжатие нечётного цикла в графе (цветка) в одну вершину с продолжением поиска итеративно по сжатому графу.
Основной причиной, почему алгоритм сжатия цветков важен, является то, что он дал первое доказательство возможности нахождения наибольшего паросочетания за полиномиальное время. Другой причиной является то, что метод приводит к описанию многогранника линейного программирования для многогранника паросочетаний, что приводит к алгоритму паросочетания минимального веса . Как уточнил Александр Схрейвер , дальнейшая важность результата следует из факта, что этот многогранник был первым, доказательство целочисленности которого «не просто следовало из тотальной унимодулярности , а его описание было прорывом в комбинаторике многогранников » .
Если дан граф G =( V , E ) и паросочетание M для G , вершина v голая (не покрыта паросочетанием), если нет ребра в M , инцидентного v . Путь в G является чередующейся цепью , если её рёбра попеременно не принадлежат M и содержатся в M . Увеличивающий путь P — это чередующаяся цепь, которая начинается и кончается голыми вершинами. Заметим, что число не принадлежащих паросочетанию рёбер в увеличивающем пути больше на единицу числа рёбер, принадлежащих паросочетанию, а потому число рёбер в увеличивающем пути нечётно. Увеличение паросочетаний вдоль пути P — это операция замены множества M на новое паросочетание .
По лемме Бержа , паросочетание M является наибольшим тогда и только тогда, когда нет M -увеличивающего пути в G . Следовательно, либо паросочетание является наибольшим, либо его можно увеличить. Таким образом, начав с некоторого паросочетания, мы можем вычислить наибольшее паросочетание путём увеличения текущего паросочетания с помощью увеличенного пути. Можно формализовать алгоритм следующим образом
ВХОД: Граф G, начальное паросочетание M на G
ВЫХОД: наибольшее паросочетание M* на G
A1 function найти_наибольшее_паросочетание(G, M) : M*
A2 найти_увеличивающий_путь(G, M)
A3 if P не пустое then
A4 return найти_наибольшее_паросочетание(G, увеличиваем M вдоль P)
A5 else
A6 return M
A7 end if
A8 end function
Нам нужно описать, каким образом увеличивающие пути могут быть эффективно построены. Подпрограмма их поиска использует цветки и стягивание.
Если дан граф G =( V , E ) и паросочетание M графа G , то цветок B — это цикл в G , состоящий из 2k + 1 рёбер, из которых в точности k принадлежат M и в котором есть вершина v ( база ) такая, что существует чередующаяся цепь чётной длины ( стебель ) из v в голую вершину w .
Нахождение цветков:
Определим сжатый граф G’ как граф, полученный из G путём стягивания всех рёбер цветка B , и определим сжатое паросточетание M’ как паросочетание графа G’ , соответствующее M .
G’ имеет M’ -увеличивающий путь тогда и только тогда, когда G имеет M -увеличивающий путь, а тогда любой M’ -увеличивающий путь P’ в G’ может быть поднят до M -увеличивающего пути в G путём восстановления цветка B , стянутого ранее, так что сегмент пути P’ (если такой есть), проходящий через v B заменяет на подходящий сегмент, проходящий через B . Более детально:
Тогда цветок может быть сжат и поиск может быть продолжен по сжатым графам. Это сжатие является сердцем алгоритма Эдмондса.
Поиск увеличивающего пути использует дополнительную структуру данных, представляющую собой лес F , индивидуальные деревья которого соответствуют порциям графа G . Фактически, лес F тот же самый, что и применяемый для поиска наибольших паросочетаний в двудольных графах (без необходимости стягивания цветков). На каждой итерации алгоритм либо (1) находит увеличивающий путь, либо (2) находит цветок и осуществляет рекурсию в сжатый граф, либо (3) делается вывод, что увеличивающего пути не существует. Дополнительная структура строится посредством инкрементальной процедуры, которая обсуждается ниже .
Процедура построения просматривает вершины v и рёбра e графа G и инкрементально обновляет F соответствующим образом. Если v находится в дереве T леса, мы через root(v) обозначим корень дерева T . Если и u , и v лежат в том же дереве T в F , через distance(u, v) обозначим длину единственного пути из u в v в дереве T .
ВХОД: Граф G, паросочетание M в G ВЫХОД: Увеличивающий путь P в G или пустой путь, если такого пути не найдено B01 function найти_ увеличивающий_путь(G, M):P B02 пустой лес B03 делаем все вершины и рёбра непомеченными в G, помечаем все рёбра M B05 for each голой вершины v do B06 создаём дерево из одной вершины {v} и добавляем дерево в F B07 end for B08 while имеется непомеченная вершина v в F с чётным distance(v, root(v)) do B09 while существует непомеченное ребро e={v, w} do B10 if w не в F then // w входит в паросочетание, так что добавляем ребро, // покрывающее e и w в F B11 сочетается с вершиной w в M B12 добавляем рёбра {v,w} и {w,x} в дерево для v B13 else B14 if distance(w, root( w )) нечётно then // не делаем ничего. B15 else B16 if root(v) ≠ root(w) then // Рапортуем о увеличивающем пути в F . B17 путь () B18 return P B19 else // Стягиваем цветок в G и ищем путь в сжатом графе. B20 цветок, образованный e и рёбрами пути в T B21 сжимаем G и M путём стягивания цветка B B22 найти_ увеличивающий_путь B23 поднимаем P’ в G B24 return P B25 end if B26 end if B27 end if B28 помечаем ребро e B29 end while B30 помечаем вершину v B31 end while B32 return пустой путь B33 end function
Следующие четыре рисунка иллюстрируют выполнение алгоритма. Пунктирные линии показывают рёбра, которые в этот момент не представлены в лесе. Сначала алгоритм обрабатывает ребро, не принадлежащее лесу, которое приводит к расширению текущего леса (строки B10 — B12).
Затем удаляется цветок и сжимается граф (строи B20 — B21).
Наконец, алгоритм обнаруживает увеличивающий путь P′ в сжатом графе (строка B22) и поднимает его в исходном графе (строка B23). Заметим, что способность алгоритма стягивания цветков здесь является решающим. Алгоритм не может найти P в исходном графе прямо, поскольку только рёбра не из леса между вершинами на чётном расстоянии от корня рассматриваются в строке B17 алгоритма.
Лес F , построенный функцией найти_увеличивающий_путь() , является чередующимся лесом .
Каждая итерация цикла, начиная со строки B09, либо добавляет вершину в дерево T в F (строка B10), либо находит увеличивающий путь (строка B17), либо находит цветок (строка B20). Легко видеть, что время работы алгоритма равно . Микали и Вазирани показали алгоритм, который строит наибольшее паросочетание за время .
Алгоритм сводится к стандартному алгоритму для паросочетаний в двудольных графах , если G является двудольным . Поскольку в этом случае нет нечётных циклов G , цветки никогда не будут найдены и можно просто удалить строки B20 — B24 алгоритма.
Задачу о паросочетаниях можно обобщить назначением весов рёбрам графа G . В этом случае задаётся вопрос о множестве M , которое даёт паросочетание с максимальным (минимальным) полным весом. Взвешенную задачу о паросочетаниях можно решить с помощью комбинаторного алгоритма, который использует невзвешенный алгоритм Эдмондса в качестве подпрограммы . Владимир Колмогоров дал эффективную имплементацию этого алгоритма на C++ .