Соответствие максимальной мощности

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

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

• 1 Алгоритмы для двудольных графов
• 2 Алгоритмы для произвольных графов
• 3 Приложения и обобщения
• 4 ссылки

Самый простой способ вычислить соответствие максимальной мощности - следовать алгоритму Форда – Фулкерсона. Этот алгоритм решает более общую проблему вычисления максимального потока, но его можно легко адаптировать: мы просто преобразуем граф в потоковую сеть, добавляя исходную вершину к графу, имеющему ребро ко всем левым вершинам в 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 | lt;| 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-однородных гиперграфов.