В теории графов , совершенное паросочетание в графе есть соответствие , которое покрывает все вершины графа. Более формально, учитывая график G = ( V , E ), идеальное соответствие в G представляет собой подмножество М из Е , такие , что каждая вершина V смежна с одним краем в М .
Идеальное соответствие также называется 1-фактором ; См. объяснение этого термина в разделе « Факторизация графа» . В некоторой литературе используется термин полное соответствие .
Каждое идеальное сопоставление - это сопоставление максимальной мощности , но обратное неверно. Например, рассмотрим следующие графики: [1]
В графе (b) имеется идеальное соответствие (размера 3), так как все 6 вершин совпадают; в графах (a) и (c) есть соответствие максимальной мощности (размера 2), которое не является идеальным, поскольку некоторые вершины не совпадают.
Идеально сочетается также с кромкой минимального размера . Если есть идеальное совпадение, то и номер совпадения, и номер кромочного покрытия равны | V | / 2 .
Идеальное совпадение может произойти только в том случае, если граф имеет четное число вершин. Почти идеальное совпадение - это совпадение, в котором ровно одна вершина не совпадает. Это может произойти только тогда, когда граф имеет нечетное количество вершин, и такое совпадение должно быть максимальным. На приведенном выше рисунке часть (c) показывает почти идеальное соответствие. Если для каждой вершины в графе существует почти идеальное соответствие, которое пропускает только эту вершину, граф также называется факторно-критическим .
Характеристики [ править ]
Теорема Холла о браке дает характеристику двудольных графов, которые имеют идеальное соответствие.
Теорема Тутте дает характеристику произвольных графов.
Идеальное соответствие - это охватывающий 1-регулярный подграф, также известный как 1-фактор . В общем случае остовный k -регулярный подграф является k- фактором .
Вычисление [ править ]
Решение о том, допускает ли граф идеальное соответствие, может быть выполнено за полиномиальное время с использованием любого алгоритма для поиска максимального соответствия мощности .
Однако подсчет количества совершенных паросочетаний даже в двудольных графах является # P-полным . Это связано с тем, что вычисление перманента произвольной матрицы 0–1 (еще одна проблема # P-полной) аналогично вычислению числа точных сопоставлений в двудольном графе, имеющем данную матрицу в качестве матрицы двойного сопряжения .
Замечательная теорема Кастелейна утверждает, что количество совершенных паросочетаний в плоском графе может быть вычислено точно за полиномиальное время с помощью алгоритма FKT .
Количество совершенных паросочетаний в полном графе K n (с четным n ) задается двойным факториалом : [2]
Совершенный совпадающий многогранник [ править ]
Идеальное соответствие многогранник графа является многогранник в R | E | в котором каждый угол является вектором инцидентности идеального совпадения.
См. Также [ править ]
- Соответствие без зависти
- Соответствие максимальной мощности
- Идеальное соответствие в гиперграфах высокой степени
- Теоремы холловского типа для гиперграфов
Ссылки [ править ]
