Соответствие максимальной мощности - Maximum cardinality matching

Соответствие максимальной мощности - фундаментальная проблема теории графов . Нам дан граф , и цель состоит в том, чтобы найти соответствие, содержащее как можно больше ребер, то есть подмножество ребер с максимальной мощностью, так что каждая вершина смежна не более чем с одним ребром подмножества. Поскольку каждое ребро покрывает ровно две вершины, эта проблема эквивалентна задаче поиска соответствия, которое покрывает как можно больше вершин. ${\ displaystyle G}$

Важным частным случаем задачи согласования максимальной мощности является случай, когда G является двудольным графом , чьи вершины V разделены между левыми вершинами в X и правыми вершинами в Y , а ребра в E всегда соединяют левую вершину с правой вершиной. В этом случае проблема может быть эффективно решена с помощью более простых алгоритмов, чем в общем случае.

Алгоритмы для двудольных графов

Самый простой способ вычислить соответствие максимальной мощности - следовать алгоритму Форда – Фулкерсона . Этот алгоритм решает более общую проблему вычисления максимального потока , но его можно легко адаптировать: мы просто преобразуем граф в потоковую сеть , добавляя исходную вершину к графу, имеющему ребро ко всем левым вершинам в X , добавляя вершину стока. имея ребро из всех правых вершин в Y , сохраняя все ребра между X и Y и давая емкость 1 каждому ребру. Затем алгоритм Форда – Фулкерсона продолжит работу, многократно находя увеличивающий путь от некоторого x ∈ X до некоторого y ∈ Y и обновляя сопоставление M , взяв симметричную разность этого пути с M (при условии, что такой путь существует). Поскольку каждый путь может быть найден в момент, время работы является , и согласующий максимум состоит из ребер Е , которые несут вытекать из X в Y . ${\ Displaystyle \ O (E)}$${\ Displaystyle \ O (В.Е.)}$

Улучшение этого алгоритма дается более сложным алгоритмом Хопкрофта – Карпа , который одновременно ищет несколько путей увеличения. Этот алгоритм работает во времени. ${\ displaystyle O ({\ sqrt {V}} E)}$

Алгоритм Чандрана и Хохбаума для двудольных графов работает во времени, которое зависит от размера максимального соответствия , которое для равно . С помощью логических операций над словами размера сложность еще больше улучшается . ${\ displaystyle k}$${\ Displaystyle | X | <| Y |}$${\ displaystyle O \ left (\ min \ {| X | k, E \} + {\ sqrt {k}} \ min \ {k ^ {2}, E \} \ right)}$${\ displaystyle \ lambda}$${\ displaystyle O \ left (\ min \ left \ {| X | k, {\ frac {| X || Y |} {\ lambda}}, E \ right \} + k ^ {2} + {\ frac {k ^ {2.5}} {\ lambda}} \ right)}$

Существуют более эффективные алгоритмы для специальных видов двудольных графов:

• Для разреженных двудольных графов проблема максимального согласования может быть решена с помощью алгоритма Мадри, основанного на электрических потоках.${\ displaystyle {\ tilde {O}} (E ^ {10/7})}$
• Для плоских двудольных графов проблема может быть решена за время, где n - количество вершин, путем сведения задачи к максимальному потоку с несколькими источниками и стоками.${\ Displaystyle О (п \ журнал ^ {3} п)}$

Алгоритмы для произвольных графов

Алгоритм цветения находит соответствие максимального числа элементов в целом (не обязательно двудольный) графов. Он работает во времени . Лучшая производительность O ( √ V E ) для общих графов, соответствующая производительности алгоритма Хопкрофта – Карпа на двудольных графах, может быть достигнута с помощью гораздо более сложного алгоритма Микали и Вазирани. Такая же оценка была достигнута с помощью алгоритма Блюма ( де ) и алгоритма Габова и Тарьяна . ${\ Displaystyle O (| V | ^ {2} \ cdot | E |)}$

Альтернативный подход использует рандомизацию и основан на алгоритме быстрого умножения матриц . Это дает рандомизированный алгоритм для общих графов со сложностью . Теоретически это лучше для достаточно плотных графов , но на практике алгоритм работает медленнее. ${\ displaystyle O (V ^ {2.376})}$

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

Приложения и обобщения

• Найдя соответствие максимальной мощности, можно решить, существует ли идеальное соответствие .
• Проблема поиска соответствия с максимальным весом во взвешенном графе называется проблемой согласования максимального веса , а ее ограничение на двудольные графы называется проблемой присваивания . Если каждая вершина может быть сопоставлена ​​с несколькими вершинами одновременно, то это обобщенная проблема присваивания .
• Соответствующий приоритет является частным соответствующей максимальными кардинальным , в котором вершины Приоритетные согласованы в первую очередь.
• Проблема поиска паросочетания максимальной мощности в гиперграфе является NP-полной даже для 3-однородных гиперграфов.

Рекомендации