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

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

Определения

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

Алгоритм FKT

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

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

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

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

Литература

  1. 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.
  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.
  3. Kasteleyn P. W. Graph theory and crystal physics // Graph Theory and Theoretical Physics. — Academic Press, 1967. — С. 43–110.
  4. 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.
  5. 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.