파프 방향 문서 원본 보기

[[그래프 이론]]에서 '''파프 방향'''(Pfaff方向, {{llang|en|Pfaffian orientation}})은 그래프 위의 [[완벽 부합]]의 수를 쉽게 계산할 수 있게 하는 [[유향 그래프]] 구조이다.

== 정의 ==
그래프 <math>\Gamma</math> 위의 [[유향 그래프]] 구조를 그래프의 '''방향'''({{llang|en|orientation}})이라고 한다. <math>\Gamma</math>의 방향은 부분 집합
:<math>D\subseteq\operatorname V(\Gamma)\times\operatorname V(\Gamma)</math>
:<math>\{\{u,v\}\colon (u,v)\in D\}=\operatorname E(\Gamma)</math>
로 표시된다.

=== 홀수 순환 ===
다음이 주어졌다고 하자.
* [[유향 그래프]] <math>(\Gamma,D)</math>
* <math>\Gamma</math> 속의 (꼭짓점과 변이 겹치지 않는) 짝수 길이의 [[순환 (그래프 이론)|순환]] <math>C=(v_0,v_1,\dotsc,v_{2n-1},v_{2n}=v_0)</math>
만약 <math>C</math>를 (시계 방향 또는 반시계 방향으로) 순회(巡廻)할 때, <math>D</math>와 일치하는 방향으로 순회되는 변이 홀수 개라면, 즉
:<math>2\nmid|\{i\in\mathbb Z/(2n)\colon (v_i,v_{i+1})\in D\}|</math>
이라면, <math>C</math>를 <math>D</math>-홀수 순환({{llang|en|<math>D</math>-oddly oriented cycle}})이라고 한다.

(<math>C</math>의 길이가 짝수이므로, <math>C</math>의 순회 방향은 상관이 없다.)

=== 부합의 부호 ===
다음이 주어졌다고 하자.
* [[유한 그래프]] <math>\Gamma</math>
* <math>\Gamma</math>의 방향 <math>D\subseteq\operatorname V(\Gamma)^2</math>
* <math>\Gamma</math>의 [[완벽 부합]] <math>M\subseteq\operatorname E(\Gamma)</math>
* <math>\operatorname V(\Gamma)</math> 위의 임의의 [[전순서]]. 이에 따라, <math>\Gamma</math>의 꼭짓점 집합이 <math>\{1,2,\dotsc,2n\}</math>이라고 여길 수 있다.
이제, <math>M</math>의 원소들이 (임의의 순서로)
:<math>\{(v_1,v_2),(v_3,v_4),\dotsc,(v_{2n-1},v_{2n})\}</math>
이라고 하자. 그렇다면, <math>M</math>의 <math>D</math>-'''부호'''는 다음과 같다.
:<math>\operatorname{sgn}_D(M)=\operatorname{sgn}
\begin{pmatrix}
1&2&\dotsm&2n-2&2n\\
v_1&v_2&\dotsm&v_{2n-2}&v_{2n}
\end{pmatrix}\in\{+1,-1\}</math>
여기서 우변은 [[순열]]의 부호, 즉 [[군 준동형]] <math>\operatorname{sgn}\colon\operatorname{Sym}(n)\to\operatorname{Cyc}(2)=\{\pm1\}</math>이다.

이 값은 <math>M</math>의 원소들의 [[전순서]]에 의존하지 않지만, 물론 <math>\operatorname V(\Gamma)</math> 위의 [[전순서]]에는 의존한다.

=== 파프 방향 ===
다음이 주어졌다고 하자.
* [[그래프]] <math>\Gamma</math>
* <math>\Gamma</math>의 방향 <math>D</math>
이제, <math>\operatorname V(\Gamma)</math> 위에 임의의 전순서를 부여하였을 때, 만약 <math>\Gamma</math> 위의 임의의 두 [[완벽 부합]] <math>M</math>, <math>M'</math>에 대하여
:<math>\operatorname{sgn}_D(M)=\operatorname{sgn}_D(M')</math>
이라면, <math>D</math>를 <math>\Gamma</math>의 '''파프 방향'''이라고 한다.

보다 일반적으로, 다음이 주어졌다고 하자.
다음이 주어졌다고 하자.
* [[유한 그래프]] <math>\Gamma</math>
* <math>\Gamma</math>의 방향 <math>D_1,\dotsc,D_k</math>
* 유리수 <math>\alpha_1,\dotsc,\alpha_k</math>
만약 <math>\operatorname V(\Gamma)</math>에 임의의 [[전순서]]를 부여하였을 때, 임의의 [[완벽 부합]] <math>M\subseteq\operatorname E(\Gamma)</math>에 대하여,
:<math>\alpha_1\operatorname{sgn}_{D_1}(M)+\dotsb+\alpha_k\operatorname{sgn}_{D_k}(M) = 1</math>
이라면,
:<math>(D_i,\alpha_i)_{1\le i\le k}</math>
를 <math>\Gamma</math> 위의 <math>k</math>-'''파프 방향'''이라고 한다.

== 성질 ==
=== 완벽 부합의 수 ===
[[유한 그래프]] <math>\Gamma</math> 위의 <math>k</math>-파프 방향 <math>(D_i,\alpha_i)_{1\le i\le k}</math>이 주어졌다고 하자. 그렇다면, <math>\Gamma</math>의 [[완벽 부합]]의 수
:<math>\operatorname Z_\Gamma(1,0)</math>
은 다음과 같다.
:<math>\operatorname Z_\Gamma(1,0)=\left|\sum_{i=1}^k\alpha_i\operatorname{Pf}\left(\operatorname{Inc}(\Gamma,D_i)\right)\right|</math>
여기서
* <math>\operatorname{Pf}(-)</math>은 짝수 크기 [[반대칭 행렬]]의 [[파피안]]이다.
* <math>\operatorname{Inc}(\Gamma,D)</math>는 [[유향 그래프]] <math>(\Gamma,D)</math>의 부호 [[인접 행렬]]이다. 즉, 다음과 같다.
*: <math>\langle u|\operatorname{Inc}(\Gamma,D)|v\rangle=\begin{cases}
1&(u,v)\in D\\
-1&(v,u)\in D\\
0&(u,v),(v,u)\not\in D
\end{cases}\qquad(u,v\in\operatorname V(\Gamma))</math>

=== 카스텔레인 방향 ===
다음이 주어졌다고 하자.
* [[유한 그래프|유한]] [[유향 그래프]] <math>(\Gamma,D)</math>
* [[콤팩트 공간|콤팩트]] [[유향 다양체|유향]] [[곡면]] <math>\Sigma\cong(\mathbb T^2)^{\#g}</math>. 그 종수가 <math>g\in\mathbb N</math>라고 하자.
* 매장 <math>\Gamma\hookrightarrow \Sigma</math>. 이에 따라, <math>(\Sigma,\Gamma)</math>는 유한 [[CW 복합체]]를 이룬다. (즉, <math>\Gamma\setminus\Sigma</math>는 유한 개의 2차원 [[열린 공]]들의 [[분리합집합]]이다.)
그렇다면, 만약 다음 조건이 성립한다면, <math>D</math>를 '''카스텔레인 방향'''(Kasteleyn方向, {{llang|en|Kasteleyn orientation}})이라고 한다.
* <math>(\Sigma,\Gamma)</math>의 임의의 2-세포의 경계 <Math>C\subseteq\Gamma</math>은 <math>D</math>-홀수 순환이다.

<math>(\Sigma,\Gamma)</math> 위의 카스텔레인 방향들은 <math>\Sigma</math> 위의 [[세타 지표]], 즉 [[스핀 구조]]와 표준적으로 [[일대일 대응]]한다. 이에 따라, <math>(\Sigma,\Gamma)</math> 위에는 <Math>4^g</math>개의 카스텔레인 방향들이 존재하며, 이들에 적절한
:<math>\alpha_i=\pm 2^{-g}</math>
계수를 부여할 경우 이들은 <math>4^g</math>-파프 방향을 이룬다.

특히, <math>g=0</math>일 경우, 임의의 [[평면 그래프]] 위의 카스텔레인 방향은 (1-)파프 방향을 이룬다. 이에 따라, 모든 [[평면 그래프]]는 파프 방향을 갖는다.

== 역사 ==
피터르 빌럼 카스텔레인({{llang|nl|Pieter Willem Kasteleyn}}, 1924~1996)이 도입하였다. “파프 방향”이라는 용어는 [[요한 프리드리히 파프]]의 이름을 딴 것이다. 파프는 [[파피안]]을 도입하였는데, 파프 방향의 부호 [[인접 행렬]]의 [[파피안]]으로 [[완벽 부합]]의 수를 계산할 수 있기 때문에 이와 같은 이름이 붙었다.

== 참고 문헌 ==
* {{서적 인용|장=A survey of Pfaffian orientations of graphs| 장url=http://people.math.gatech.edu/~thomas/PAP/pfafsurv.pdf | doi=10.4171/022-3/47 | 이름=Robin | 성=Thomas | 쪽=963–984 | 제목=Proceedings of the International Congress of Mathematicians, Madrid, August 22–30, 2006. Volume Ⅲ. Invited lectures | 날짜=2007 | zbl=1101.05054 | isbn=978-3-03719-022-7 | 언어=en}}
* {{저널 인용|arxiv=1409.4631|bibcode=2014arXiv1409.4631C|제목=The geometry of dimer models|이름=David|성=Cimasoni|날짜=2014|doi=10.5802/wbln.3|저널=Winter Braids Lecture Notes|권=1|쪽=2|언어=en}}
* {{서적 인용 | url=https://esc.fnwi.uva.nl/thesis/centraal/files/f887198315.pdf | 제목=Perfect matchings and Kasteleyn orientation | 기타=학사 학위 논문 (지도 교수 Dion Gĳswĳt) | 이름=Jeanette | 성=Nguyen | 출판사=[[암스테르담 대학교]] | 날짜=2008-05-15 | 언어=en | access-date=2017-06-28 | archive-date=2019-01-10 | archive-url=https://web.archive.org/web/20190110212207/https://esc.fnwi.uva.nl/thesis/centraal/files/f887198315.pdf }}

== 외부 링크 ==
* {{웹 인용|url=https://www.math.brown.edu/~res/MathNotes/pfaff.pdf | 제목=Kasteleyn’s formula for perfect matchings | 이름=Rich | 성=Schwartz | 날짜=2013-04-08 | 언어=en}}
{{위키데이터 속성 추적}}

[[분류:그래프 이론]]
[[분류:그래프 알고리즘]]
[[분류:평면 그래프]]