Сопоставление (теория графов) - Matching (graph theory) - Wikipedia

Для сравнения двух графиков см. Сопоставление графиков.

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

Определения

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

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

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

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

А идеальное соответствие соответствие, которое соответствует всем вершинам графа. То есть соответствие является идеальным, если каждая вершина графа инцидент к краю соответствия. Каждое идеальное совпадение является максимальным и, следовательно, максимальным. В некоторой литературе термин полное соответствие используется. На приведенном выше рисунке только часть (b) показывает идеальное совпадение. Идеальное сочетание - это также минимальный размер край крышки. Таким образом, размер максимального соответствия не больше размера минимального краевого покрытия: ν (G) ≤ ρ (G) . Граф может содержать идеальное соответствие только в том случае, если у него четное число вершин.

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

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

An индуцированное соответствие - соответствие, которое является набором ребер индуцированный подграф.^[3]

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

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

Если А и B два максимальных совпадения, то |А| ≤ 2|B| и |B| ≤ 2|А|. Чтобы убедиться в этом, обратите внимание, что каждое ребро в B \ А может быть смежным не более чем с двумя ребрами в А \ B потому что А это соответствие; кроме того, каждый край в А \ B примыкает к ребру в B \ А по максимальности 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-приближением минимального максимального совпадения. Это неравенство жесткое: например, если грамм - это путь с 3 ребрами и 4 вершинами, размер минимального максимального сопоставления равен 1, а размер максимального сопоставления равен 2.

Соответствующие многочлены

Основная статья: Соответствующий полином

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

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

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

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

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

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

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

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

Основная проблема в комбинаторная оптимизация находит максимальное соответствие. В этой задаче используются различные алгоритмы для разных классов графов.

В невзвешенный двудольный граф, задача оптимизации - найти максимальное соответствие количества элементов. Проблема решается Алгоритм Хопкрофта-Карпа во время О(√VE) время, а есть более эффективные рандомизированные алгоритмы, аппроксимационные алгоритмы, и алгоритмы для специальных классов графов, таких как двудольные планарные графы, как описано в основной статье.

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

Основная статья: Подбор максимального веса

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

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

Максимальные соответствия

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

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

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

Основная статья: Индекс Хосоя

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

Количество идеальных совпадений в полный график K_п (с п даже) дается двойной факториал (п − 1)!!.^[11] Количество совпадений в полных графах, без ограничения совпадений на идеальность, задается телефонные номера.^[12]

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

Основная статья: Максимально подходящий край

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

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

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

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

В интерактивном режиме узлы на одной стороне двудольного графа прибывают по одному и должны либо быть немедленно сопоставлены с другой стороной графа, либо отброшены. Это естественное обобщение проблема секретаря и имеет приложения для онлайн-аукционов рекламы. Лучший онлайн-алгоритм для случая невзвешенной максимизации с моделью случайных приходов достигает конкурентное соотношение из ${\displaystyle 0.696}$.^[17]

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

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

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

Приложения

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

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

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

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

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

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

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

1. Алан Гиббонс, Алгоритмическая теория графов, Cambridge University Press, 1985, глава 5.
2. http://diestel-graph-theory.com/basic.html
3. Кэмерон, Кэти (1989), «Индуцированные сопоставления», специальный выпуск для Первой Монреальской конференции по комбинаторике и информатике, 1987 г., Дискретная прикладная математика, 24 (1–3): 97–102, Дои:10.1016 / 0166-218X (92) 90275-F, МИСТЕР  1011265
4. Галлай, Тибор (1959), "Über extreme Punkt- und Kantenmengen", Анна. Univ. Sci. Будапешт. Eötvös Sect. Математика., 2: 133–138.
5. Фредман, Майкл Л .; Тарьян, Роберт Эндре (1987), «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети», Журнал ACM, 34 (3): 596–615, Дои:10.1145/28869.28874
6. Яннакакис, Михалис; Гаврил, Фаника (1980), «Множества с преобладанием ребер в графах» (PDF), Журнал SIAM по прикладной математике, 38 (3): 364–372, Дои:10.1137/0138030.
7. Гарей, Майкл Р.; Джонсон, Дэвид С. (1979), Компьютеры и непреодолимость: руководство по теории NP-полноты, W.H. Фриман, ISBN  0-7167-1045-5. Множество с преобладанием ребер (вариант решения) обсуждается в рамках задачи о доминирующем множестве, которой является проблема GT2 в Приложении A1.1. Минимальное максимальное соответствие (вариант решения) - это проблема GT10 в Приложении A1.1.
8. Аузиелло, Джорджио; Крещенци, Пьерлуиджи; Гамбози, Джорджио; Канн, Вигго; Маркетти-Спаккамела, Альберто; Протаси, Марко (2003), Сложность и аппроксимация: задачи комбинаторной оптимизации и их свойства аппроксимируемости, Springer. Набор минимальных доминирующих ребер (оптимизационная версия) - это задача GT3 в Приложении B (стр. 370). Минимальное максимальное соответствие (оптимизационная версия) - это проблема GT10 в Приложении B (стр. 374). Смотрите также Минимальный набор доминирования края и Минимальное максимальное соответствие в веб-сборник.
9. Лесли Валиант, Сложность перечисления и проблемы надежности, SIAM J. Comput., 8 (3), 410–421
10. Безакова, Ивона; Штефанкович, Даниэль; Вазирани, Виджай В.; Вигода, Эрик (2008). «Ускорение имитации отжига для постоянных и комбинаторных задач счета». SIAM Журнал по вычислениям. 37 (5): 1429–1454. CiteSeerX  10.1.1.80.687. Дои:10.1137/050644033.
11. Каллан, Дэвид (2009), Комбинаторный обзор тождеств для двойного факториала, arXiv:0906.1317, Bibcode:2009arXiv0906.1317C.
12. Тихи, Роберт Ф .; Вагнер, Стефан (2005), «Экстремальные задачи для топологических индексов комбинаторной химии» (PDF), Журнал вычислительной биологии, 12 (7): 1004–1013, Дои:10.1089 / cmb.2005.12.1004, PMID  16201918.
13. Рабин, Майкл O .; Вазирани, Виджай В. (1989), "Максимальные соответствия в общих графах посредством рандомизации", Журнал алгоритмов, 10 (4): 557–567, Дои:10.1016/0196-6774(89)90005-9
14. Чериян, Джозеф (1997), "Рандомизированный ${\displaystyle {\widetilde {O}}(M(|V|))}$ алгоритмы для задач теории согласования », SIAM Журнал по вычислениям, 26 (6): 1635–1655, Дои:10.1137 / S0097539793256223
15. Тасса, Тамир (2012), "Нахождение всех максимально совместимых ребер в двудольном графе", Теоретическая информатика, 423: 50–58, Дои:10.1016 / j.tcs.2011.12.071
16. Карп, Ричард М.; Вазирани, Умеш В.; Вазирани, Виджай В. (1990). «Оптимальный алгоритм он-лайн двустороннего сопоставления» (PDF). Материалы 22-го ежегодного симпозиума ACM по теории вычислений (STOC 1990). С. 352–358. Дои:10.1145/100216.100262.
17. Махдиан, Мохаммад; Ян, Цици (2011). «Онлайн-двустороннее сопоставление со случайным поступлением: подход, основанный на сильно раскрывающих факторы LP». Материалы сорок третьего ежегодного симпозиума ACM по теории вычислений. С. 597–606. Дои:10.1145/1993636.1993716.
18. См., Например, Тринайстич, Ненад; Кляйн, Дуглас Дж .; Рандич, Милан (1986), «О некоторых решенных и нерешенных проблемах химической теории графов», Международный журнал квантовой химии, 30 (S20): 699–742, Дои:10.1002 / qua.560300762.

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

1. Ловас, Ласло; Пламмер, М. (1986), Теория соответствия, Анналы дискретной математики, 29, Северная Голландия, ISBN  0-444-87916-1, МИСТЕР  0859549
2. Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест и Клиффорд Штайн (2001), Введение в алгоритмы (второе изд.), MIT Press and McGraw – Hill, Chapter 26, pp. 643–700, ISBN  0-262-53196-8
3. Андраш Франк (2004). По венгерскому методу Куна - дань уважения Венгрии (PDF) (Технический отчет). Egerváry Research Group.
4. Майкл Л. Фредман и Роберт Э. Тарджан (1987), «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети», Журнал ACM, 34 (3): 595–615, Дои:10.1145/28869.28874.
5. С. Дж. Цивин и Иван Гутман (1988), Структуры Кекуле в бензоидных углеводородах, Springer-Verlag
6. Марек Карпински и Войцех Риттер (1998), Быстрые параллельные алгоритмы для задач сопоставления графов, Издательство Оксфордского университета, ISBN  978-0-19-850162-6

внешняя ссылка

• Библиотека графов с реализацией сопоставления максимальной мощности элементов на основе Хопкрофта – Карпа и Пуш – Релабеля.