Введение

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

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

Совершенное соответствие также называется 1-фактором; подробнее о данном термине см. в разделе Факторизация графа. В некоторых источниках используется термин «полное соответствие». Каждое совершенное соответствие является соответствием максимальной мощности, но обратное неверно. Например, рассмотрим следующие графы:

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

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

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

Теорема Холла о браке предоставляет характеристику двудольных графов, имеющих совершенное паросочетание. Теорема Тютте предоставляет характеристику для произвольных графов. Совершенное паросочетание — это остовный 1-регулярный подграф, также известный как 1-фактор. В общем случае, остовный k-регулярный подграф является k-фактором. Спектральная характеристика графа, имеющего совершенное паросочетание, дана Хасани Монфаредом и Малликом следующим образом: Пусть G — граф на четном числе вершин, а λ₁, …, λₙ — n различных ненулевых чисто мнимых чисел. Тогда G имеет совершенное паросочетание тогда и только тогда, когда существует вещественная кососимметричная матрица A с графом G и спектром λ₁, …, λₙ. Обратите внимание, что (простой) граф вещественной симметричной или кососимметричной матрицы A порядка n имеет n вершин и ребра, заданные ненулевыми внедиагональными элементами матрицы A.

Связь с окрашиванием графа

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

Совершенно совпадающий политоп

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