Лучшие вопросы
Таймлайн
Чат
Перспективы

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

Из Википедии, свободной энциклопедии

Remove ads

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

Определения

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

Remove ads

Алгоритм FKT

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

Remove ads

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

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

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

Литература

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads