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

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

Определения

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

Алгоритм FKT

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

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

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

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