Пфаффова ориентация неориентированного графа — это ориентация (назначение направления каждому ребру графа), при которой любой чётный центральный цикл нечётно ориентирован.
Определения
правитьВ этом определении цикл чётный, если он содержит чётное число рёбер. является центральным, если подграф графа , полученный удалением всех вершин , имеет совершенное паросочетание. Центральные циклы называются также иногда знакопеременными контурами. Цикл нечётно ориентирован, если содержит нечётное число рёбер одной из двух ориентаций[1][2].
Алгоритм FKT
правитьПфаффовы ориентации изучались в связи с их применением в алгоритме FKT подсчёта числа совершенных паросочетаний в заданном графе. В этом алгоритме ориентации рёбер используются для назначения значений переменным в матрице Татта[англ.] графа. Тогда пфаффиан матрицы (квадратный корень его определителя) даёт число совершенных паросочетаний. Каждое совершенное паросочетание даёт вклад в пфаффиан в зависимости от ориентации. Выбор пфаффовой ориентации обеспечивает, чтобы эти вклады все имели одинаковые знаки, так что ни один из них не сокращается с другим. Этот результат контрастирует с существенно большей вычислительной сложностью подсчёта сочетаний в произвольных графах[2].
Пфаффовы графы
правитьГраф называется пфаффовым, если он имеет пфаффову ориентацию. Любой планарный граф пфаффов[3]. Ориентация, в которой каждая грань планарного графа имеет нечётное число направленных по часовой стрелке рёбер, автоматически пфаффова. Такая ориентация может быть найдена, начав с произвольной ориентации остовного дерева графа. Остальные рёбра, не входящие в это дерево, образуют остовное дерево двойственного графа и их ориентации могут быть выбраны согласно порядку обхода двойственного остовного дерева снизу вверх, с целью обеспечить, чтобы каждая грань исходного графа имела нечётное число рёбер, направленных по часовой стрелке. Более обще, любой свободный от -миноров граф имеет пфаффову ориентацию. Это графы, не имеющие коммунального графа (который не пфаффов) в качестве минора графа. По теореме Вагнера свободные от -миноров графы образуются путём склеивания копий планарных графов и полного графа вдоль общих рёбер. Та же самая структура склеивания может быть использована для получения пфаффовой ориентация этих графов[4].
Кроме , существует бесконечно много минимальных непфаффовых графов[1]. Для двудольных графов можно определить, существует ли пфаффова ориентация, и если существует, найти таковую за полиномиальное время[5].
Литература
править- ↑ 1 2 Serguei Norine, Robin Thomas. Minimally non-Pfaffian graphs // Journal of Combinatorial Theory. — 2008. — Т. 98, вып. 5. — С. 1038–1055. — doi:10.1016/j.jctb.2007.12.005.
- ↑ 1 2 Robin Thomas. A survey of Pfaffian orientations of graphs // International Congress of Mathematicians. Vol. III. — Eur. Math. Soc., 2006. — С. 963–984. — doi:10.4171/022-3/47.
- ↑ Kasteleyn P. W. Graph theory and crystal physics // Graph Theory and Theoretical Physics. — Academic Press, 1967. — С. 43–110.
- ↑ Charles H. C. Little. An extension of Kasteleyn's method of enumerating the 1-factors of planar graphs // Combinatorial mathematics (Proc. Second Australian Conf., Univ. Melbourne, Melbourne, 1973). — Springer, Berlin, 1974. — Т. 403. — С. 63–72.
- ↑ Neil Robertson, Paul Seymour, Robin Thomas. Permanents, Pfaffian orientations, and even directed circuits // Annals of Mathematics. — 1999. — Т. 150, вып. 3. — С. 929–975. — doi:10.2307/121059. — arXiv:math/9911268.
Для улучшения этой статьи желательно:
|