파피안 방향

Pfaffian orientation

그래프 이론에서, 비방향 그래프의 파피안 방향은 각 에지에 방향을 할당하여 특정 사이클("짝수 중심 사이클")이 각 방향에서 홀수 수의 에지를 갖도록 한다.그래프가 Paffian 방향을 갖는 경우, 방향은 그래프의 완벽한 일치를 세는 데 사용될 수 있다.이것은 항상 파피안 방향을 가지고 있는 평면 그래프의 완벽한 일치를 세기 위한 FKT 알고리즘의 주요 아이디어다.보다 일반적으로 유틸리티 그래프 3, 을(를) 그래프 마이너로서 가지고 있지 않은 모든 그래프에는 Pafeian 방향이 있지만 3, {\는 그렇지 않으며, 그 밖의 최소의 비Pappeian 그래프는 무한히 많지 않다.

정의들

비방향 그래프의 Pafeian 방향은 모든 중심 사이클이 이상하게도 방향인 방향이다.이 정의의 용어는 다음과 같은 의미를 갖는다.

  • 방향은 그래프의 각 가장자리에 방향을 할당하는 것이다.
  • 사이클 은(는) 짝수 에지를 포함하고 있더라도 동일하다.
  • {\의 정점을 모두 제거하여 된 G 의 하위 그래프가 완벽하게 일치하면 C 사이클 displaystyle 이(가) 중심이며, 중앙 사이클을 교대 회로라고도 한다.
  • 사이클 의 두 방향 각각이 방향의 홀수 수의 가장자리와 일치할 사이클C {\displaystyle C은([1][2]는) 이상 방향이다.

일치 항목 개수 적용

주어진 그래프에서 완벽한 일치의 수를 세기 위한 FKT 알고리즘과 관련하여 Paffian 오리엔테이션이 연구되었다.이 알고리즘에서 가장자리 방향은 그래프 투트 행렬의 변수에± 1 값을 할당하는 데 사용된다.그런 다음 이 행렬의 파피안(결정인자의 제곱근)은 완벽한 일치의 수를 제공한다.각각의 완벽한 매칭은 어떤 방향이 사용되든 ± 1 을(를) Paffian에 기여한다. Paffian 방향을 선택하면 이러한 기여들이 모두 서로 동일한 기호를 가지며, 따라서 어느 것도 취소되지 않는다.이 결과는 임의 그래프에서 일치 항목을 계산하는 계산 복잡성이 훨씬 높은 것과 대조적이다.[2]

파피안 그래프

그래프는 파피안 방향이 있으면 파피안이라고 한다.모든 평면 그래프는 파피안이다.[3]평면 그래프의 각 면에 시계 방향의 가장자리 수가 홀수인 방향은 자동으로 Paffian이다.이러한 방향은 그래프의 스패닝 트리의 임의적인 방향에서 시작하여 찾을 수 있다.이 트리가 아닌 나머지 가장자리는 듀얼 그래프의 스패닝 트리를 형성하며, 원래 그래프의 각 면에 시계방향의 홀수 수가 있는지 확인하기 위해 듀얼 스패닝 트리의 상향 이동에 따라 방향을 선택할 수 있다.[4]

보다 일반적으로 모든 , -minor-free 그래프에는 Pafeian 방향이 있다.이 그래프들은 그래프 마이너로서 유틸리티 그래프 K , Pafeian이 아님)가 없는 그래프들이다.바그너의 정리로는 K , -minor-free 그래프를 평면 그래프의 복사본과 전체 그래프 K 를 공유 가장자리를 따라 붙임으로써 형성된다.동일한 접착 구조를 사용하여 이러한 그래프에 대한 Pafeian 방향을 얻을 수 있다.[4]

, 와 함께 무한히 많은 최소 비 Pappeian 그래프가 있다[1]초당적 그래프의 경우 다항 시간 내에 Pafeian 방향이 존재하는지 여부를 확인할 수 있다.[5]

참조

  1. ^ a b Norine, Serguei; Thomas, Robin (2008), "Minimally non-Pfaffian graphs", Journal of Combinatorial Theory, Series B, 98 (5): 1038–1055, doi:10.1016/j.jctb.2007.12.005, MR 2442595
  2. ^ a b Thomas, Robin (2006), "A survey of Pfaffian orientations of graphs" (PDF), International Congress of Mathematicians. Vol. III, Zürich: Eur. Math. Soc., pp. 963–984, doi:10.4171/022-3/47, MR 2275714
  3. ^ Kasteleyn, P. W. (1967), "Graph theory and crystal physics", Graph Theory and Theoretical Physics, London: Academic Press, pp. 43–110, MR 0253689
  4. ^ a b Little, Charles H. C. (1974), "An extension of Kasteleyn's method of enumerating the 1-factors of planar graphs", Combinatorial Mathematics (Proc. Second Australian Conf., Univ. Melbourne, Melbourne, 1973), Lecture Notes in Mathematics, Springer, Berlin, 403: 63–72, MR 0382062
  5. ^ Robertson, Neil; Seymour, P. D.; Thomas, Robin (1999), "Permanents, Pfaffian orientations, and even directed circuits", Annals of Mathematics, Second Series, 150 (3): 929–975, arXiv:math/9911268, doi:10.2307/121059, JSTOR 121059, MR 1740989