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

Набор ребер без общих вершин

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

Определения

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

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

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

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

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

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

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

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

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

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

Если A и B — два максимальных паросочетания, то | А | ≤ 2| Б | и | Б | ≤ 2| А | . Чтобы убедиться в этом, заметим, что каждое ребро в 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.

Спектральная характеристика числа сопоставления графа дана Хассани Монфаредом и Малликом следующим образом: Пусть - граф на вершинах, а - различные ненулевые чисто мнимые числа, где . Тогда число совпадений равно тогда и только тогда, когда (а) существует действительная кососимметричная матрица с графиком , собственными значениями и нулями и (б) все действительные кососимметричные матрицы с графиком имеют не более чем ненулевые собственные значения . ^[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 ( √VE ) времени, и существуют более эффективные рандомизированные алгоритмы , алгоритмы аппроксимации и алгоритмы для специальных классов графов, таких как двудольные плоские графы , как описано в основной статье . .

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

Во взвешенном двудольном графе задача оптимизации состоит в том, чтобы найти паросочетание с максимальным весом; двойная задача — найти паросочетание с минимальным весом. Эту проблему часто называют максимальным взвешенным двусторонним сопоставлением или проблемой назначения . Венгерский алгоритм решает задачу назначения и положил начало алгоритмам комбинаторной оптимизации. Он использует модифицированный поиск кратчайшего пути в алгоритме увеличения пути. Если на этом этапе используется алгоритм Беллмана-Форда , время работы венгерского алгоритма становится равным , или стоимость ребра может быть смещена с возможностью достижения времени работы с алгоритмом Дейкстры и кучей Фибоначчи . ^[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 . Проверено 31 мая 2022 г. Каждый узел инцидентен не более чем одному ребру сопоставления. Говорят, что ребра независимы.
2. Алан Гиббонс, Алгоритмическая теория графов, издательство Кембриджского университета, 1985, Глава 5.
3. «Предварительный просмотр».
4. Кэмерон, Кэти (1989), «Индуцированные соответствия», Специальный выпуск Первой Монреальской конференции по комбинаторике и информатике, 1987, Дискретная прикладная математика , 24 (1–3): 97–102, doi : 10.1016/0166-218X ( 92)90275-Ф , МР  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), «Кучи Фибоначчи и их использование в улучшенных алгоритмах сетевой оптимизации», Journal of the 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), «Максимальные совпадения в общих графах посредством рандомизации», Journal of Algorithms , 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), «Нахождение всех максимально совпадающих ребер в двудольном графе», Theoretical Computer Science , 423 : 50–58, doi : 10.1016/j.tcs.2011.12.071
18. Карп, Ричард М .; Вазирани, Умеш В. ; Вазирани, Виджай В. (1990). «Оптимальный алгоритм двустороннего сопоставления в режиме онлайн» (PDF) . Материалы 22-го ежегодного симпозиума ACM по теории вычислений (STOC, 1990) . стр. 352–358. дои : 10.1145/100216.100262.
19. Махдиан, Мохаммед; Ян, Цици (2011). «Двустороннее онлайн-сопоставление со случайными поступлениями: подход, основанный на сильно выявляющих факторах ЛП». Труды сорок третьего ежегодного симпозиума ACM по теории вычислений . стр. 597–606. дои : 10.1145/1993636.1993716 .
20. См., например, Тринайстич, Ненад ; Кляйн, Дуглас Дж.; Рандич, Милан (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), «Кучи Фибоначчи и их использование в улучшенных алгоритмах сетевой оптимизации», Journal of the ACM , 34 (3): 595–615, doi : 10.1145/28869.28874 , S2CID  7904683.
5. С. Дж. Сайвин и Иван Гутман (1988), Структуры Кекуле в бензоидных углеводородах , Springer-Verlag
6. Марек Карпински и Войцех Риттер (1998), Быстрые параллельные алгоритмы для задач сопоставления графов , Oxford University Press, ISBN 978-0-19-850162-6

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

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