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

Сопоставление, охватывающее каждый узел графа

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

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

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

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

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

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

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

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

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

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

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

Вычисление

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

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

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

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

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

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

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

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

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

• Сопоставление без зависти
• Сопоставление максимальной мощности
• Идеальное совпадение в гиперграфах высокой степени
• Теоремы типа Холла для гиперграфов

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

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