파프 방향

그래프 이론에서 **파프 방향**(Pfaff方向, )은 그래프 위의 완벽 부합의 수를 쉽게 계산할 수 있게 하는 유향 그래프 구조이다.

## 정의
그래프 \Gamma 위의 유향 그래프 구조를 그래프의 **방향**()이라고 한다. \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-홀수 순환()이라고 한다.

(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方向, )이라고 한다.
* (\Sigma,\Gamma)의 임의의 2-세포의 경계 C\subseteq\Gamma은 D-홀수 순환이다.

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

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

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

## 참고 문헌
* 
* 
* 

## 외부 링크
* 

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