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

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

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

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

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

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