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

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

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

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

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

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

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

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

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

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

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

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

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

Приложения и обобщения [ править ]

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

Ссылки [ править ]

^ Запад, Дуглас Брент (1999), Введение в теорию графов (2-е изд.), Прентис Холл, Глава 3, ISBN 0-13-014400-2
^ a b c Chandran, Bala G .; Hochbaum, Дорит С. (2011), практические и теоретические усовершенствования для двудольного согласования с использованием алгоритма pseudoflow , Arxiv : 1105,1569 , Bibcode : 2011arXiv1105.1569C , теоретически эффективные алгоритмы , перечисленные выше , как правило, плохо работают на практике.
^ Madry, A (2013), "Навигационная Центральный путь с электрическими потоками: От Потоков к Повторению и обратно", Основы информатики и вычислительная техника (FOCS) 2013 IEEE 54 - й ежегодного симпозиума по , С. 253-262,. Arxiv : 1307.2205 , Bibcode : 2013arXiv1307.2205M
^ Боррадейл, Гленкора; Klein, Philip N .; Мозес, Шей; Нуссбаум, Яхав; Вульф-Нильсен, Кристиан (2017), «Максимальный поток с множественными источниками и множественными стоками в ориентированных плоских графах в почти линейное время», SIAM Journal on Computing , 46 (4): 1280–1303, arXiv : 1105.2228 , doi : 10.1137 / 15M1042929 , Руководство по эксплуатации 3681377 , S2CID 207071917
^ Микали, С .; Вазирани, В.В. (1980), " Алгоритм поиска максимального соответствия в общих графах", Proc. 21-й симпозиум IEEE. Основы информатики и вычислительной техники ., Стр 17-27, DOI : 10,1109 / SFCS.1980.12 , S2CID 27467816 $\scriptstyle O({\sqrt {|V|}}\cdot |E|)$ .
^ Блюм, Норберт (1990). Патерсон, Майкл С. (ред.). «Новый подход к максимальному совпадению в общих графиках» (PDF) . Автоматы, языки и программирование . Конспект лекций по информатике. Берлин, Гейдельберг: Springer. 443 : 586–597. DOI : 10.1007 / BFb0032060 . ISBN 978-3-540-47159-2.
^ Габоу, Гарольд N; Тарьян, Роберт Э (1991-10-01). «Алгоритмы более быстрого масштабирования для общих задач сопоставления графов» (PDF) . Журнал ACM . 38 (4): 815–853. DOI : 10.1145 / 115234.115366 . S2CID 18350108 .
^ Муха, М .; Санковский П. (2004), "Максимальные совпадения с помощью исключения Гаусса" (PDF) , Proc. 45-я конференция IEEE Symp. Основы компьютерных наук , стр. 248–255.
^ Дуан, Ран; Петти, Сет (01.01.2014). «Аппроксимация линейного времени для согласования максимального веса» (PDF) . Журнал ACM . 61 : 1–23. DOI : 10.1145 / 2529989 . S2CID 207208641 .
^ Карп, Ричард М. (1972), Миллер, Раймонд Э .; Тэтчер, Джеймс У .; Болингер, Джин Д. (ред.), "Сводимость среди комбинаторных проблем", Сложность компьютерных вычислений: Труды симпозиума по сложности компьютерных вычислений, состоявшегося 20–22 марта 1972 года в Исследовательском центре IBM Thomas J. Watson , Йорктаун-Хайтс, Нью-Йорк, и спонсируется Управлением военно-морских исследований, Программой математики, IBM World Trade Corporation и Департаментом математических наук IBM, Серия симпозиумов по исследованиям IBM, Бостон, Массачусетс: Springer US, стр. 85–103 , DOI : 10.1007 / 978-1-4684-2001-2_9 , ISBN 978-1-4684-2001-2

[Wes01-1] Запад, Дуглас Брент (1999), Введение в теорию графов (2-е изд.), Прентис Холл, Глава 3, ISBN 0-13-014400-2

[Chandran-2] Chandran, Bala G .; Hochbaum, Дорит С. (2011), практические и теоретические усовершенствования для двудольного согласования с использованием алгоритма pseudoflow , Arxiv : 1105,1569 , Bibcode : 2011arXiv1105.1569C , теоретически эффективные алгоритмы , перечисленные выше , как правило, плохо работают на практике.

[3] Madry, A (2013), "Навигационная Центральный путь с электрическими потоками: От Потоков к Повторению и обратно", Основы информатики и вычислительная техника (FOCS) 2013 IEEE 54 - й ежегодного симпозиума по , С. 253-262,. Arxiv : 1307.2205 , Bibcode : 2013arXiv1307.2205M

[4] Боррадейл, Гленкора; Klein, Philip N .; Мозес, Шей; Нуссбаум, Яхав; Вульф-Нильсен, Кристиан (2017), «Максимальный поток с множественными источниками и множественными стоками в ориентированных плоских графах в почти линейное время», SIAM Journal on Computing , 46 (4): 1280–1303, arXiv : 1105.2228 , doi : 10.1137 / 15M1042929 , Руководство по эксплуатации 3681377 , S2CID 207071917

[5] Микали, С .; Вазирани, В.В. (1980), " Алгоритм поиска максимального соответствия в общих графах", Proc. 21-й симпозиум IEEE. Основы информатики и вычислительной техники ., Стр 17-27, DOI : 10,1109 / SFCS.1980.12 , S2CID 27467816 $\scriptstyle O({\sqrt {|V|}}\cdot |E|)$ .

[6] Блюм, Норберт (1990). Патерсон, Майкл С. (ред.). «Новый подход к максимальному совпадению в общих графиках» (PDF) . Автоматы, языки и программирование . Конспект лекций по информатике. Берлин, Гейдельберг: Springer. 443 : 586–597. DOI : 10.1007 / BFb0032060 . ISBN 978-3-540-47159-2.

[7] Габоу, Гарольд N; Тарьян, Роберт Э (1991-10-01). «Алгоритмы более быстрого масштабирования для общих задач сопоставления графов» (PDF) . Журнал ACM . 38 (4): 815–853. DOI : 10.1145 / 115234.115366 . S2CID 18350108 .

[Mucha-8] Муха, М .; Санковский П. (2004), "Максимальные совпадения с помощью исключения Гаусса" (PDF) , Proc. 45-я конференция IEEE Symp. Основы компьютерных наук , стр. 248–255.

[9] Дуан, Ран; Петти, Сет (01.01.2014). «Аппроксимация линейного времени для согласования максимального веса» (PDF) . Журнал ACM . 61 : 1–23. DOI : 10.1145 / 2529989 . S2CID 207208641 .

[10] Карп, Ричард М. (1972), Миллер, Раймонд Э .; Тэтчер, Джеймс У .; Болингер, Джин Д. (ред.), "Сводимость среди комбинаторных проблем", Сложность компьютерных вычислений: Труды симпозиума по сложности компьютерных вычислений, состоявшегося 20–22 марта 1972 года в Исследовательском центре IBM Thomas J. Watson , Йорктаун-Хайтс, Нью-Йорк, и спонсируется Управлением военно-морских исследований, Программой математики, IBM World Trade Corporation и Департаментом математических наук IBM, Серия симпозиумов по исследованиям IBM, Бостон, Массачусетс: Springer US, стр. 85–103 , DOI : 10.1007 / 978-1-4684-2001-2_9 , ISBN 978-1-4684-2001-2

[1]