Идеальное соответствие

В теории графов идеальное паросочетание в графе — это паросочетание , которое покрывает каждую вершину графа. Более формально, если задан граф $G = (V, E)$ , идеальное паросочетание в $G$ — это подмножество $M$ множества ребер $E$ , такое, что каждая вершина в множестве вершин $V$ смежна ровно с одним ребром в $M$ .

Идеальное соответствие также называется 1-фактором ; см. Факторизация графа для объяснения этого термина. В некоторой литературе используется термин полное соответствие .

Каждое идеальное соответствие является соответствием с максимальной мощностью , но обратное неверно. Например, рассмотрим следующие графики: ^[1]

В графе (b) имеется идеальное паросочетание (размера 3), поскольку все 6 вершин сопоставлены; в графах (a) и (c) имеется паросочетание максимальной мощности (размера 2), которое не является идеальным, поскольку некоторые вершины не сопоставлены.

Идеальное соответствие также является минимальным размером покрытия ребер . Если есть идеальное соответствие, то и число соответствия, и число покрытия ребер равны $| V | / 2$ .

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

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

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

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

Совершенное паросочетание — это охватывающий 1-регулярный подграф, также известный как 1-фактор . В общем случае охватывающий k -регулярный подграф — это k -фактор .

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

Вычисление

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

Однако подсчет числа совершенных паросочетаний, даже в двудольных графах , является #P-полной задачей . Это связано с тем, что вычисление перманента произвольной матрицы 0–1 (еще одна #P-полная задача) равносильно вычислению числа совершенных паросочетаний в двудольном графе, имеющем заданную матрицу в качестве матрицы бисмежности .

Замечательная теорема Кастелейна утверждает, что число совершенных паросочетаний в плоском графе можно вычислить точно за полиномиальное время с помощью алгоритма FKT .

Число совершенных паросочетаний в полном графе K _n (где n четное) определяется двойным факториалом : ^[3] $(n-1)!!$

Связь с раскраской графа

Граф с рёберной раскраской может индуцировать количество (не обязательно правильных) раскрасок вершин , равное количеству идеальных сопоставлений, поскольку каждая вершина покрывается ровно один раз в каждом сопоставлении. Это свойство было исследовано в квантовой физике ^[4] и теории вычислительной сложности . ^[5]

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

Многогранник идеального паросочетания графа — это многогранник в R ^|E| , в котором каждый угол является вектором инцидентности идеального паросочетания.

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

Соответствие без зависти
Сопоставление с максимальной мощностью
Идеальное соответствие в гиперграфах высокой степени
Теоремы типа Холла для гиперграфов
Проблема уникального идеального соответствия ^[6]^[7]^[8]

Ссылки

^ Алан Гиббонс, Алгоритмическая теория графов, Cambridge University Press, 1985, Глава 5.
^ Кейван Хассани Монфаред и Судипта Маллик, Теорема 3.6, Спектральная характеристика соответствий в графах, Линейная алгебра и ее приложения 496 (2016) 407–419, https://doi.org/10.1016/j.laa.2016.02.004
^ Каллан, Дэвид (2009), Комбинаторный обзор тождеств для двойного факториала , arXiv : 0906.1317 , Bibcode : 2009arXiv0906.1317C.
^ Марио Кренн, Сюэмей Гу, Антон Цайлингер , Квантовые эксперименты и графы: многопартийные состояния как когерентные суперпозиции идеальных совпадений, Phys. Rev. Lett. 119, 240403 – Опубликовано 15 декабря 2017 г.
^ Моше И. Варди , Живэй Чжан, Решение квантово-вдохновленных задач идеального соответствия с помощью гибридных булевых ограничений на основе теоремы Тутта, arXiv:2301.09833 [cs.AI], IJCAI'23
^ Ван, Сюмэй; Шан, Вэйпин; Юань, Цзиньцзян (2015-09-01). «О графах с уникальным совершенным паросочетанием». Графы и комбинаторика . 31 (5): 1765–1777. doi :10.1007/s00373-014-1463-8. ISSN 1435-5914.
^ Хоанг, Тхань Минь; Махаджан, Мина ; Тиерауф, Томас (2006). Буглиези, Мишель; Пренель, Барт; Сассоне, Владимиро; Вегенер, Инго (ред.). «О проблеме двудольного уникального совершенного соответствия». Автоматы, языки и программирование . Берлин, Гейдельберг: Springer: 453–464. doi :10.1007/11786986_40. ISBN 978-3-540-35905-0.
^ Козен, Декстер; Вазирани, Умеш В.; Вазирани, Виджай В. (1985). Махешвари, С. Н. (ред.). «NC-алгоритмы для графов сопоставимости, интервальных графов и тестирование на уникальное совершенное соответствие». Основы программных технологий и теоретической информатики . Берлин, Гейдельберг: Springer: 496–503. doi :10.1007/3-540-16042-6_28. ISBN 978-3-540-39722-9.