WikiSort.ru - Не сортированное

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

Определения

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

Алгоритм FKT

Пфаффовы ориентации изучались в связи с их применением в алгоритме FKT подсчёта числа совершенных паросочетаний в заданном графе. В этом алгоритме ориентации рёбер используются для назначения значений ${\displaystyle \pm 1}$ переменным в матрице Тата^[en] графа. Тогда пфаффиан матрицы (квадратный корень его определителя) даёт число совершенных паросочетаний. Каждое совершенное паросочетание даёт вклад ${\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].

Литература

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. Проверить статью на грамматические и орфографические ошибки.