파프 방향

그래프 이론에서 **파프 방향**(Pfaff方向, Pfaffian orientation)은 그래프 위의 완벽 부합의 수를 쉽게 계산할 수 있게 하는 유향 그래프 구조이다.
# 정의
그래프 \Gamma 위의 유향 그래프 구조를 그래프의 **방향**(orientation)이라고 한다. \Gamma의 방향은 부분 집합 :D\subseteq\operatorname V(\Gamma)\times\operatorname V(\Gamma) :\\{\\{u,v\\}\colon (u,v)\in D\\}=\operatorname E(\Gamma) 로 표시된다.
## 홀수 순환
다음이 주어졌다고 하자. * 유향 그래프 (\Gamma,D) * \Gamma 속의 (꼭짓점과 변이 겹치지 않는) 짝수 길이의 순환 C=(v_0,v_1,\dotsc,v_{2n-1},v_{2n}=v_0) 만약 C를 (시계 방향 또는 반시계 방향으로) 순회(巡廻)할 때, D와 일치하는 방향으로 순회되는 변이 홀수 개라면, 즉 :2\nmid|\\{i\in\mathbb Z/(2n)\colon (v_i,v_{i+1})\in D\\}| 이라면, C를 D-홀수 순환(D-oddly oriented cycle)이라고 한다. (C의 길이가 짝수이므로, C의 순회 방향은 상관이 없다.)
## 부합의 부호
다음이 주어졌다고 하자. * 유한 그래프 \Gamma * \Gamma의 방향 D\subseteq\operatorname V(\Gamma)^2 * \Gamma의 완벽 부합 M\subseteq\operatorname E(\Gamma) * \operatorname V(\Gamma) 위의 임의의 전순서. 이에 따라, \Gamma의 꼭짓점 집합이 \\{1,2,\dotsc,2n\\}이라고 여길 수 있다. 이제, M의 원소들이 (임의의 순서로) :\\{(v_1,v_2),(v_3,v_4),\dotsc,(v_{2n-1},v_{2n})\\} 이라고 하자. 그렇다면, M의 D-**부호**는 다음과 같다. :\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\\} 여기서 우변은 순열의 부호, 즉 군 준동형 \operatorname{sgn}\colon\operatorname{Sym}(n)\to\operatorname{Cyc}(2)=\\{\pm1\\}이다. 이 값은 M의 원소들의 전순서에 의존하지 않지만, 물론 \operatorname V(\Gamma) 위의 전순서에는 의존한다.
## 파프 방향
다음이 주어졌다고 하자. * 그래프 \Gamma * \Gamma의 방향 D 이제, \operatorname V(\Gamma) 위에 임의의 전순서를 부여하였을 때, 만약 \Gamma 위의 임의의 두 완벽 부합 M, M'에 대하여 :\operatorname{sgn}_D(M)=\operatorname{sgn}_D(M') 이라면, D를 \Gamma의 **파프 방향**이라고 한다. 보다 일반적으로, 다음이 주어졌다고 하자. 다음이 주어졌다고 하자. * 유한 그래프 \Gamma * \Gamma의 방향 D_1,\dotsc,D_k * 유리수 \alpha_1,\dotsc,\alpha_k 만약 \operatorname V(\Gamma)에 임의의 전순서를 부여하였을 때, 임의의 완벽 부합 M\subseteq\operatorname E(\Gamma)에 대하여, :\alpha_1\operatorname{sgn}_{D_1}(M)+\dotsb+\alpha_k\operatorname{sgn}_{D_k}(M) = 1 이라면, :(D_i,\alpha_i)_{1\le i\le k} 를 \Gamma 위의 k-**파프 방향**이라고 한다.
# 성질

## 완벽 부합의 수
유한 그래프 \Gamma 위의 k-파프 방향 (D_i,\alpha_i)_{1\le i\le k}이 주어졌다고 하자. 그렇다면, \Gamma의 완벽 부합의 수 :\operatorname Z_\Gamma(1,0) 은 다음과 같다. :\operatorname Z_\Gamma(1,0)=\left|\sum_{i=1}^k\alpha_i\operatorname{Pf}\left(\operatorname{Inc}(\Gamma,D_i)\right)\right| 여기서 * \operatorname{Pf}(-)은 짝수 크기 반대칭 행렬의 파피안이다. * \operatorname{Inc}(\Gamma,D)는 유향 그래프 (\Gamma,D)의 부호 인접 행렬이다. 즉, 다음과 같다. *: \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))
## 카스텔레인 방향
다음이 주어졌다고 하자. * 유한 유향 그래프 (\Gamma,D) * 콤팩트 유향 곡면 \Sigma\cong(\mathbb T^2)^{\\#g}. 그 종수가 g\in\mathbb N라고 하자. * 매장 \Gamma\hookrightarrow \Sigma. 이에 따라, (\Sigma,\Gamma)는 유한 CW 복합체를 이룬다. (즉, \Gamma\setminus\Sigma는 유한 개의 2차원 열린 공들의 분리합집합이다.) 그렇다면, 만약 다음 조건이 성립한다면, D를 **카스텔레인 방향**(Kasteleyn方向, Kasteleyn orientation)이라고 한다. * (\Sigma,\Gamma)의 임의의 2-세포의 경계 C\subseteq\Gamma은 D-홀수 순환이다. (\Sigma,\Gamma) 위의 카스텔레인 방향들은 \Sigma 위의 세타 지표, 즉 스핀 구조와 표준적으로 일대일 대응한다. 이에 따라, (\Sigma,\Gamma) 위에는 4^g개의 카스텔레인 방향들이 존재하며, 이들에 적절한 :\alpha_i=\pm 2^{-g} 계수를 부여할 경우 이들은 4^g-파프 방향을 이룬다. 특히, g=0일 경우, 임의의 평면 그래프 위의 카스텔레인 방향은 (1-)파프 방향을 이룬다. 이에 따라, 모든 평면 그래프는 파프 방향을 갖는다.
# 역사
피터르 빌럼 카스텔레인(Pieter Willem Kasteleyn, 1924~1996)이 도입하였다. “파프 방향”이라는 용어는 요한 프리드리히 파프의 이름을 딴 것이다. 파프는 파피안을 도입하였는데, 파프 방향의 부호 인접 행렬의 파피안으로 완벽 부합의 수를 계산할 수 있기 때문에 이와 같은 이름이 붙었다.