Пфаффова ориентация

Пфаффова ориентация неориентированного графа $G$ — это ориентация (назначение направления каждому ребру графа), при которой любой чётный центральный цикл нечётно ориентирован.

Определения

В этом определении цикл $C$ чётный, если он содержит чётное число рёбер. $C$ является центральным, если подграф графа $G$, полученный удалением всех вершин $C$, имеет совершенное паросочетание. Центральные циклы называются также иногда знакопеременными контурами. Цикл $C$ нечётно ориентирован, если содержит нечётное число рёбер одной из двух ориентаций.

Алгоритм FKT

Основная статья: Алгоритм FKT

Пфаффовы ориентации изучались в связи с их применением в алгоритме FKT подсчёта числа совершенных паросочетаний в заданном графе. В этом алгоритме ориентации рёбер используются для назначения значений $\pm 1$ переменным в матрице Татта графа. Тогда пфаффиан матрицы (квадратный корень его определителя) даёт число совершенных паросочетаний. Каждое совершенное паросочетание даёт вклад $\pm 1$ в пфаффиан в зависимости от ориентации. Выбор пфаффовой ориентации обеспечивает, чтобы эти вклады все имели одинаковые знаки, так что ни один из них не сокращается с другим. Этот результат контрастирует с существенно большей вычислительной сложностью подсчёта сочетаний в произвольных графах.

Пфаффовы графы

Граф называется пфаффовым, если он имеет пфаффову ориентацию. Любой планарный граф пфаффов. Ориентация, в которой каждая грань планарного графа имеет нечётное число направленных по часовой стрелке рёбер, автоматически пфаффова. Такая ориентация может быть найдена, начав с произвольной ориентации остовного дерева графа. Остальные рёбра, не входящие в это дерево, образуют остовное дерево двойственного графа и их ориентации могут быть выбраны согласно порядку обхода двойственного остовного дерева снизу вверх, с целью обеспечить, чтобы каждая грань исходного графа имела нечётное число рёбер, направленных по часовой стрелке. Более обще, любой свободный от $K_{3,3}$-миноров граф имеет пфаффову ориентацию. Это графы, не имеющие коммунального графа $K_{3,3}$ (который не пфаффов) в качестве минора графа. По теореме Вагнера свободные от $K_{3,3}$-миноров графы образуются путём склеивания копий планарных графов и полного графа $K_{5}$ вдоль общих рёбер. Та же самая структура склеивания может быть использована для получения пфаффовой ориентация этих графов.

Кроме $K_{3,3}$, существует бесконечно много минимальных непфаффовых графов. Для двудольных графов можно определить, существует ли пфаффова ориентация, и если существует, найти таковую за полиномиальное время.