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

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

Определения

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

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

Приложение для подсчета совпадений

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

Графы Пфаффа

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

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

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

Ссылки

^ Jump up to: ^а ^б Норина, Сергей; Томас, Робин (2008), «Минимально непфаффовы графы», Журнал комбинаторной теории , серия B, 98 (5): 1038–1055, doi : 10.1016/j.jctb.2007.12.005 , MR 2442595
^ Jump up to: ^а ^б Томас, Робин (2006), «Обзор пфаффовой ориентации графов» (PDF) , Международный конгресс математиков. Том. III , том. 3, Цюрих: Евр. Математика. Soc., стр. 963–984, doi : 10.4171/022-3/47 , ISBN. 978-3-98547-038-9 , МР 2275714
^ Кастелейн, П.В. (1967), «Теория графов и физика кристаллов», Теория графов и теоретическая физика , Лондон: Academic Press, стр. 43–110, MR 0253689
^ Jump up to: ^а ^б Литтл, Чарльз Х.К. (1974), «Расширение метода Кастелейна для перечисления 1-факторов плоских графов», Комбинаторная математика (Труды Второй австралийской конференции, Университет Мельбурна, Мельбурн, 1973) , Конспекты лекций по математике, 403 , Шпрингер, Берлин: 63–72, MR 0382062
^ Робертсон, Нил ; Сеймур, Полиция ; Томас, Робин (1999), «Перманенты, пфаффовы ориентации и даже направленные схемы», Annals of Mathematics , Second Series, 150 (3): 929–975, arXiv : math/9911268 , doi : 10.2307/121059 , JSTOR 121059 , МР 1740989

[nt-1] Jump up to: ^а ^б Норина, Сергей; Томас, Робин (2008), «Минимально непфаффовы графы», Журнал комбинаторной теории , серия B, 98 (5): 1038–1055, doi : 10.1016/j.jctb.2007.12.005 , MR 2442595

[t-2] Jump up to: ^а ^б Томас, Робин (2006), «Обзор пфаффовой ориентации графов» (PDF) , Международный конгресс математиков. Том. III , том. 3, Цюрих: Евр. Математика. Soc., стр. 963–984, doi : 10.4171/022-3/47 , ISBN. 978-3-98547-038-9 , МР 2275714

[k-3] Кастелейн, П.В. (1967), «Теория графов и физика кристаллов», Теория графов и теоретическая физика , Лондон: Academic Press, стр. 43–110, MR 0253689

[l-4] Jump up to: ^а ^б Литтл, Чарльз Х.К. (1974), «Расширение метода Кастелейна для перечисления 1-факторов плоских графов», Комбинаторная математика (Труды Второй австралийской конференции, Университет Мельбурна, Мельбурн, 1973) , Конспекты лекций по математике, 403 , Шпрингер, Берлин: 63–72, MR 0382062

[rst-5] Робертсон, Нил ; Сеймур, Полиция ; Томас, Робин (1999), «Перманенты, пфаффовы ориентации и даже направленные схемы», Annals of Mathematics , Second Series, 150 (3): 929–975, arXiv : math/9911268 , doi : 10.2307/121059 , JSTOR 121059 , МР 1740989

[1]

[2]

[3]

[4]

[5]