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

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

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

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

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

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

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

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

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

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

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

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

Вычисление

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

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

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

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

Подключение к раскраске графа

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

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

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

См. также

Ссылки

^ Алан Гиббонс, Алгоритмическая теория графов, издательство Кембриджского университета, 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. Преподобный Летт. 119, 240403 – опубликовано 15 декабря 2017 г.
^ Моше Ю. Варди , Живэй Чжан, Решение квантовых задач идеального соответствия с помощью гибридных логических ограничений на основе теоремы Тутте , arXiv:2301.09833 [cs.AI], IJCAI'23

[1] Алан Гиббонс, Алгоритмическая теория графов, издательство Кембриджского университета, 1985, Глава 5.

[2] Кейван Хассани Монфаред и Судипта Маллик, Теорема 3.6, Спектральная характеристика паросочетаний в графах, Линейная алгебра и ее приложения 496 (2016) 407–419, https://doi.org/10.1016/j.laa.2016.02.004

[3] Каллан, Дэвид (2009), Комбинаторный обзор тождеств для двойного факториала , arXiv : 0906.1317 , Bibcode : 2009arXiv0906.1317C .

[4] Марио Кренн, Сюэмей Гу, Антон Цайлингер , Квантовые эксперименты и графики: многосторонние состояния как когерентные суперпозиции идеальных совпадений , Phys. Преподобный Летт. 119, 240403 – опубликовано 15 декабря 2017 г.

[5] Моше Ю. Варди , Живэй Чжан, Решение квантовых задач идеального соответствия с помощью гибридных логических ограничений на основе теоремы Тутте , arXiv:2301.09833 [cs.AI], IJCAI'23

[1]

[2]

[3]

[4]

[5]