пфаффианская ориентация

В теории графов ориентация Пфаффа неориентированного графа назначает направление каждому ребру, так что определенные циклы («четные центральные циклы») имеют нечетное количество ребер в каждом направлении. Когда граф имеет ориентацию Пфаффа, ориентацию можно использовать для подсчета идеальных паросочетаний графа. Это основная идея алгоритма FKT для подсчета совершенных паросочетаний в планарных графах , которые всегда имеют ориентацию Пфаффа. В более общем случае каждый граф, который не имеет графа полезности в качестве минора графа , имеет пфаффову ориентацию, но ${\ Displaystyle К_ {3,3}}$ ${\ Displaystyle К_ {3,3}}$ нет, как и бесконечно много других минимальных непфаффовых графов.

Пфаффова ориентация неориентированного графа — это ориентация , в которой каждый четный центральный цикл нечетно ориентирован. Термины этого определения имеют следующие значения:

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

Граф называется пфаффовым, если он имеет пфаффову ориентацию. Каждый планарный граф является пфаффовым. ^[3] Ориентация, в которой каждая грань плоского графа имеет нечетное число ребер, ориентированных по часовой стрелке, автоматически является пфаффовой. Такую ориентацию можно найти, начав с произвольной ориентации остовного дерева графа. Остальные ребра, не входящие в это дерево, образуют остов двойственного графа , и их ориентация может быть выбрана в соответствии с восходящим обходом дуального остовного дерева, чтобы гарантировать, что каждая грань исходного графа имеет нечетную количество ребер по часовой стрелке. ^[4]

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

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