Сопоставление (теория графов)

Множество ребер без общих вершин

В математической дисциплине теории графов набор независимых ребер в неориентированном графе — это набор ребер без общих вершин . ^[1] Другими словами, подмножество ребер является набором, если каждая вершина появляется не более чем в одном ребре этого набора. Поиск набора в двудольном графе можно рассматривать как задачу сетевого потока .

Определения

Для данного графа G = ( V ,  E ) паросочетание M в G представляет собой набор попарно несмежных ребер, ни одно из которых не является петлей ; то есть никакие два ребра не имеют общих вершин.

Вершина соответствует (или насыщена ), если она является конечной точкой одного из ребер в сопоставлении. В противном случае вершина не соответствует (или ненасыщена ).

Максимальное паросочетание — это паросочетание M графа G , которое не является подмножеством какого-либо другого паросочетания. Паросочетание M графа G является максимальным, если каждое ребро в G имеет непустое пересечение хотя бы с одним ребром в M. На следующем рисунке показаны примеры максимальных паросочетаний (красные) в трех графах.

Максимальное паросочетание (также известное как паросочетание с максимальной мощностью ^[2] ) — это паросочетание, которое содержит наибольшее возможное количество ребер. Максимальных паросочетаний может быть много. Число паросочетаний графа G — это размер максимального паросочетания. Каждое максимальное паросочетание является максимальным, но не каждое максимальное паросочетание является максимальным паросочетанием. На следующем рисунке показаны примеры максимальных паросочетаний в тех же трех графах. ${\displaystyle \nu (G)}$

Идеальное паросочетание — это паросочетание, которое соответствует всем вершинам графа. То есть паросочетание является идеальным, если каждая вершина графа инцидентна ребру паросочетания. Паросочетание является идеальным, если . Каждое идеальное паросочетание является максимальным и, следовательно, максимальным. В некоторой литературе используется термин полное паросочетание . На приведенном выше рисунке только часть (b) показывает идеальное паросочетание. Идеальное паросочетание также является минимальным по размеру ребровым покрытием . Таким образом, размер максимального паросочетания не больше размера минимального по размеру ребрового покрытия: ⁠ ⁠ . Граф может содержать идеальное паросочетание только в том случае, если граф имеет четное число вершин. ${\displaystyle |M|=|V|/2}$ ${\displaystyle \nu (G)\leq \rho (G)}$

Почти идеальное паросочетание — это такое, в котором ровно одна вершина не совпадает. Очевидно, что граф может содержать только почти идеальное паросочетание, когда граф имеет нечетное число вершин, а почти идеальные паросочетания являются максимальными паросочетаниями. На рисунке выше часть (c) показывает почти идеальное паросочетание. Если каждая вершина не совпадает с некоторым почти идеальным паросочетанием, то граф называется факторно-критическим .

При наличии паросочетания M чередующийся путь — это путь, который начинается с непарной вершины ^[3] и чьи ребра попеременно принадлежат паросочетанию и не принадлежат паросочетанию. Увеличивающий путь — это чередующийся путь, который начинается со свободных (непарных) вершин и заканчивается ими. Лемма Берже утверждает, что паросочетание M является максимальным тогда и только тогда, когда не существует увеличивающего пути относительно M .

Индуцированное сопоставление — это сопоставление, которое является множеством ребер индуцированного подграфа . ^[4]

Характеристики

В любом графе без изолированных вершин сумма числа совпадений и числа покрытия рёбер равна числу вершин. ^[5] Если имеется совершенное паросочетание, то и число совпадений, и число покрытия рёбер равны | V | / 2 .

Если A и B — два максимальных паросочетания, то | A | ≤ 2| B | и | B | ≤ 2| A | . Чтобы увидеть это, заметим, что каждое ребро в B  \  A может быть смежным не более чем с двумя ребрами в A  \  B, поскольку A — паросочетание; более того, каждое ребро в A  \  B смежно с ребром в B  \  A по максимальности B , следовательно

${\displaystyle |A\setminus B|\leq 2|B\setminus A|.}$

Далее мы делаем вывод, что

${\displaystyle |A|=|A\cap B|+|A\setminus B|\leq 2|B\cap A|+2|B\setminus A|=2|B|.}$

В частности, это показывает, что любое максимальное паросочетание является 2-аппроксимацией максимального паросочетания, а также 2-аппроксимацией минимально максимального паросочетания. Это неравенство является узким: например, если G — путь с 3 ребрами и 4 вершинами, размер минимального максимального паросочетания равен 1, а размер максимального паросочетания равен 2.

Спектральная характеристика числа совпадений графа дана Хассани Монфаредом и Малликом следующим образом: Пусть будет графом на вершинах, и будут различными ненулевыми чисто мнимыми числами , где . Тогда число совпадений равно тогда и только тогда, когда (a) существует действительная кососимметричная матрица с графиком и собственными значениями и нулями, и (b) все действительные кососимметричные матрицы с графиком имеют не более чем нулевые собственные значения . ^[6] Обратите внимание, что (простой) граф действительной симметричной или кососимметричной матрицы порядка имеет вершины и ребра, заданные ненулевыми недиагональными элементами . ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle \lambda _{1}>\lambda _{2}>\ldots >\lambda _{k}>0}$ ${\displaystyle k}$ ${\displaystyle 2k\leq n}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle \pm \lambda _{1},\pm \lambda _{2},\ldots ,\pm \lambda _{k}}$ ${\displaystyle n-2k}$ ${\displaystyle G}$ ${\displaystyle 2k}$ ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle A}$

Сопоставление многочленов

Производящая функция числа k -сопоставлений ребер в графе называется многочленом сопоставления. Пусть G — граф, а m _k — число k -сопоставлений ребер. Один многочлен сопоставления G — это

${\displaystyle \sum _{k\geq 0}m_{k}x^{k}.}$

Другое определение дает соответствующий многочлен как

${\displaystyle \sum _{k\geq 0}(-1)^{k}m_{k}x^{n-2k},}$

где n — количество вершин в графе. Каждый тип имеет свое применение; для получения дополнительной информации см. статью о сопоставлении многочленов.

Алгоритмы и вычислительная сложность

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

Фундаментальной проблемой комбинаторной оптимизации является нахождение максимального паросочетания . Эта задача имеет различные алгоритмы для различных классов графов.

В невзвешенном двудольном графе задача оптимизации заключается в поиске максимального кардинального соответствия . Задача решается алгоритмом Хопкрофта-Карпа за время O ( √ V E ) , и существуют более эффективные рандомизированные алгоритмы , аппроксимационные алгоритмы и алгоритмы для специальных классов графов, таких как двудольные планарные графы , как описано в основной статье.

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

В взвешенном двудольном графе задача оптимизации заключается в поиске паросочетания с максимальным весом; двойственная задача заключается в поиске паросочетания с минимальным весом. Эту задачу часто называют двудольным паросочетанием с максимальным весом или задачей назначения . Венгерский алгоритм решает задачу назначения и был одним из начальных этапов комбинаторных алгоритмов оптимизации. Он использует модифицированный поиск кратчайшего пути в алгоритме увеличивающегося пути. Если для этого шага используется алгоритм Беллмана-Форда , время работы венгерского алгоритма становится , или стоимость ребра может быть смещена с потенциалом достижения времени работы с алгоритмом Дейкстры и кучей Фибоначчи . ^[7] ${\displaystyle O(V^{2}E)}$ ${\displaystyle O(V^{2}\log {V}+VE)}$

В недвудольном взвешенном графе задача сопоставления максимального веса может быть решена за время с помощью алгоритма Эдмондса . ${\displaystyle O(V^{2}E)}$

Максимальные паросочетания

Максимальное соответствие можно найти с помощью простого жадного алгоритма . Максимальное соответствие также является максимальным соответствием, и, следовательно, можно найти наибольшее максимальное соответствие за полиномиальное время. Однако не известен ни один алгоритм полиномиального времени для нахождения минимального максимального соответствия , то есть максимального соответствия, содержащего наименьшее возможное количество ребер.

Максимальное соответствие с k ребрами — это набор, доминирующий по ребрам, с k ребрами. И наоборот, если нам дан минимальный набор, доминирующий по ребрам, с k ребрами, мы можем построить максимальный набор с k ребрами за полиномиальное время. Следовательно, задача нахождения минимального максимального соответствия по сути эквивалентна задаче нахождения минимального набора, доминирующего по ребрам. ^[8] Известно, что обе эти задачи оптимизации являются NP-трудными ; версии решений этих задач являются классическими примерами NP-полных задач. ^[9] Обе задачи можно аппроксимировать в пределах фактора 2 за полиномиальное время: просто найти произвольное максимальное соответствие M . ^[10]

Проблемы с подсчетом

Число паросочетаний в графе известно как индекс Хосойи графа. Вычисление этой величины является #P-полным , даже для двудольных графов. ^[11] Также является #P-полным подсчет совершенных паросочетаний , даже в двудольных графах , поскольку вычисление перманента произвольной матрицы 0–1 (еще одна #P-полная задача) совпадает с вычислением числа совершенных паросочетаний в двудольном графе, имеющем заданную матрицу в качестве матрицы двусмежности . Однако существует полностью полиномиальная по времени рандомизированная аппроксимационная схема для подсчета числа двудольных паросочетаний. ^[12] Замечательная теорема Кастелейна утверждает, что число совершенных паросочетаний в плоском графе может быть вычислено точно за полиномиальное время с помощью алгоритма FKT .

Число совершенных паросочетаний в полном графе K _n (где n четное) задается двойным факториалом ( n  − 1)!!. ^[13] Число паросочетаний в полных графах, без ограничения совершенства паросочетаний, задается телефонными номерами . ^[14]

Число идеальных паросочетаний в графе также известно как гафниан его матрицы смежности .

Нахождение всех максимально совпадающих ребер

Одной из основных задач в теории сопоставлений является нахождение в заданном графе всех ребер, которые могут быть расширены до максимального сопоставления в графе (такие ребра называются максимально сопоставляемыми ребрами , или разрешенными ребрами). Алгоритмы для этой задачи включают:

• Для общих графов — детерминированный алгоритм во времени и рандомизированный алгоритм во времени . ^{[15] [16]} ${\displaystyle O(VE)}$ ${\displaystyle {\tilde {O}}(V^{2.376})}$
• Для двудольных графов, если найдено единственное максимальное паросочетание, детерминированный алгоритм запускается за время . ^[17] ${\displaystyle O(V+E)}$

Двудольное сопоставление онлайн

Проблема разработки онлайн-алгоритма для сопоставления была впервые рассмотрена Ричардом М. Карпом , Умешем Вазирани и Виджаем Вазирани в 1990 году. ^[18]

В онлайн-режиме узлы с одной стороны двудольного графа поступают по одному и должны быть немедленно сопоставлены с другой стороной графа или отброшены. Это естественное обобщение задачи секретаря , и оно применимо к аукционам онлайн-рекламы. Лучший онлайн-алгоритм для случая невзвешенной максимизации с моделью случайного прибытия достигает конкурентного коэффициента 0,696 . [ ^19]

Характеристика

Теорема Кёнига утверждает, что в двудольных графах максимальное паросочетание равно по размеру минимальному вершинному покрытию . Благодаря этому результату задачи минимального вершинного покрытия, максимального независимого множества и максимальной вершинной биклики могут быть решены за полиномиальное время для двудольных графов.

Теорема Холла о браке дает характеристику двудольных графов, имеющих идеальное паросочетание, а теорема Тутта дает характеристику для произвольных графов.

Приложения

Сопоставление в общих графах

• Структура Кекуле ароматического соединения состоит из идеального соответствия его углеродного скелета , показывая расположение двойных связей в химической структуре . Эти структуры названы в честь Фридриха Августа Кекуле фон Страдоница , который показал, что бензолу (в терминах теории графов, циклу с 6 вершинами) можно придать такую ​​структуру. ^[20]
• Индекс Хосоя — это число непустых соответствий плюс один; он используется в исследованиях по вычислительной химии и математической химии органических соединений.
• Задача о китайском почтальоне включает в себя нахождение идеального паросочетания минимального веса в качестве подзадачи.

Сопоставление в двудольных графах

• Задача о выпуске заключается в выборе минимального набора предметов из заданных требований для выпуска.
• Транспортная задача Хичкока включает в себя двудольное паросочетание как подзадачу.
• Проблема изоморфизма поддеревьев включает в себя двудольное соответствие в качестве подзадачи.

Смотрите также

• Сопоставление в гиперграфах — обобщение сопоставления в графах.
• Дробное соответствие .
• Разложение Дульмейджа–Мендельсона , разбиение вершин двудольного графа на подмножества, при котором каждое ребро принадлежит совершенному паросочетанию тогда и только тогда, когда его конечные точки принадлежат тому же подмножеству.
• Раскраска рёбер , разбиение рёбер графа на паросочетания
• Препятствие совпадению , минимальное количество ребер, которое необходимо удалить, чтобы предотвратить идеальное совпадение из существующих
• Радужное соответствие — соответствие в двудольном графе с рёберной раскраской, в котором цвета не повторяются.
• Кососимметричный граф — тип графа, который можно использовать для моделирования поиска соответствий по чередующимся путям.
• Стабильное соответствие — соответствие, в котором никакие два элемента не отдают предпочтение друг другу перед своими сопоставляемыми партнерами.
• Независимый набор вершин , набор вершин (а не ребер), никакие две из которых не являются смежными друг с другом.
• Проблема стабильного брака (также известная как проблема стабильного соответствия)

Ссылки

1. "is_matching". Документация NetworkX 2.8.2 . Получено 2022-05-31 . Каждый узел инцидентен не более чем одному ребру в паросочетании. Ребра называются независимыми.
2. Алан Гиббонс, Алгоритмическая теория графов, Cambridge University Press, 1985, Глава 5.
3. "Предварительный просмотр".
4. Кэмерон, Кэти (1989), «Индуцированные соответствия», Специальный выпуск для Первой Монреальской конференции по комбинаторике и информатике, 1987, Discrete Applied Mathematics , 24 (1–3): 97–102, doi : 10.1016/0166-218X(92)90275-F , MR  1011265
5. Галлай, Тибор (1959), «Über Extreme Punkt- und Kantenmengen», Ann. унив. наук. Будапешт. Секта Этвёша. Математика. , 2 : 133–138.
6. Кейван Хассани Монфаред и Судипта Маллик, Теорема 3.6, Спектральная характеристика соответствий в графах, Линейная алгебра и ее приложения 496 (2016) 407–419, https://doi.org/10.1016/j.laa.2016.02.004, https://arxiv.org/abs/1602.03590
7. Фредман, Майкл Л.; Тарьян, Роберт Эндре (1987), «Кучи Фибоначчи и их использование в улучшенных алгоритмах сетевой оптимизации», Журнал ACM , 34 (3): 596–615, doi : 10.1145/28869.28874 , S2CID  7904683
8. Яннакакис, Михалис; Гаврил, Фаника (1980), «Наборы с доминирующими рёбрами в графах» (PDF) , SIAM Journal on Applied Mathematics , 38 (3): 364–372, doi :10.1137/0138030.
9. Гэри, Майкл Р.; Джонсон , Дэвид С. (1979), Компьютеры и неразрешимость: Руководство по теории NP-полноты , WH Freeman, ISBN 0-7167-1045-5. Множество доминирующих ребер (версия решения) обсуждается в задаче доминирующего множества, которая является задачей GT2 в Приложении A1.1. Минимально-максимальное паросочетание (версия решения) является задачей GT10 в Приложении A1.1.
10. Аусиелло, Джорджио; Крешенци, Пьерлуиджи; Гамбози, Джорджио; Канн, Вигго; Маркетти-Спаккамела, Альберто; Протаси, Марко (2003), Сложность и аппроксимация: задачи комбинаторной оптимизации и их свойства аппроксимируемости , Springer. Минимальный набор доминирующих ребер (оптимизационная версия) — это задача GT3 в Приложении B (стр. 370). Минимально максимальное соответствие (оптимизационная версия) — это задача GT10 в Приложении B (стр. 374). См. также Минимальный набор доминирующих ребер и Минимально максимальное соответствие в веб-справочнике.
11. Лесли Валиант , Сложность проблем перечисления и надежности , SIAM J. Comput., 8(3), 410–421
12. Безакова, Ивона; Штефанкович, Даниэль; Вазирани, Виджай В .; Вигода, Эрик (2008). «Ускорение моделирования отжига для решения постоянных и комбинаторных задач счета». SIAM Journal по вычислительной технике . 37 (5): 1429–1454. CiteSeerX 10.1.1.80.687 . дои : 10.1137/050644033. S2CID  755231. 
13. Каллан, Дэвид (2009), Комбинаторный обзор тождеств для двойного факториала , arXiv : 0906.1317 , Bibcode : 2009arXiv0906.1317C.
14. Тичи, Роберт Ф.; Вагнер, Стефан (2005), «Экстремальные задачи для топологических индексов в комбинаторной химии» (PDF) , Журнал вычислительной биологии , 12 (7): 1004–1013, doi :10.1089/cmb.2005.12.1004, PMID  16201918.
15. Рабин, Майкл О.; Вазирани, Виджай В. (1989), «Максимальные соответствия в общих графах посредством рандомизации», Журнал алгоритмов , 10 (4): 557–567, CiteSeerX 10.1.1.228.1996 , doi :10.1016/0196-6774(89)90005-9 
16. Чериан, Джозеф (1997), «Рандомизированные алгоритмы для задач в теории соответствия», SIAM Journal on Computing , 26 (6): 1635–1655, doi :10.1137/S0097539793256223 ${\displaystyle {\widetilde {O}}(M(|V|))}$
17. Тасса, Тамир (2012), «Нахождение всех максимально совместимых ребер в двудольном графе», Теоретическая информатика , 423 : 50–58, doi : 10.1016/j.tcs.2011.12.071
18. Карп, Ричард М .; Вазирани, Умеш В .; Вазирани, Виджай В. (1990). "Оптимальный алгоритм для онлайнового двудольного сопоставления" (PDF) . Труды 22-го ежегодного симпозиума ACM по теории вычислений (STOC 1990) . стр. 352–358. doi :10.1145/100216.100262. ISBN 0-89791-361-2.
19. Махдиан, Мохаммад; Ян, Цици (2011). «Онлайн-двудольное сопоставление со случайными поступлениями: подход, основанный на сильно факторно-раскрывающих логических алгоритмах». Труды сорок третьего ежегодного симпозиума ACM по теории вычислений . стр. 597–606. doi : 10.1145/1993636.1993716 .
20. См., например, Trinajstić, Nenad ; Klein, Douglas J.; Randić, Milan (1986), «О некоторых решенных и нерешенных проблемах химической теории графов», International Journal of Quantum Chemistry , 30 (S20): 699–742, doi :10.1002/qua.560300762.

Дальнейшее чтение

1. Ловас, Ласло ; Пламмер, доктор медицинских наук (1986), Теория соответствия , Анналы дискретной математики, том. 29, Северная Голландия, ISBN 0-444-87916-1, МР  0859549
2. Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стайн (2001), Введение в алгоритмы (второе издание), MIT Press и McGraw–Hill, Глава 26, стр. 643–700, ISBN 0-262-53196-8{{citation}}: CS1 maint: несколько имен: список авторов ( ссылка )
3. Андраш Франк (2004). О венгерском методе Куна – дань уважения Венгрии (PDF) (Технический отчет). Исследовательская группа Эгервари.
4. Майкл Л. Фредман и Роберт Э. Тарьян (1987), «Кучи Фибоначчи и их использование в улучшенных алгоритмах сетевой оптимизации», Журнал ACM , 34 (3): 595–615, doi : 10.1145/28869.28874 , S2CID  7904683.
5. SJ Cyvin & Ivan Gutman (1988), Структуры Кекуле в бензоидных углеводородах , Springer-Verlag
6. Марек Карпински и Войцех Риттер (1998), Быстрые параллельные алгоритмы для задач сопоставления графов , Oxford University Press, ISBN 978-0-19-850162-6

Внешние ссылки

• Библиотека графов с реализацией соответствия максимальной мощности на основе алгоритмов Хопкрофта–Карпа и Push–Relabel