그래프 이론에서 파프 방향(Pfaff方向, 영어: Pfaffian orientation)은 그래프 위의 완벽 부합의 수를 쉽게 계산할 수 있게 하는 유향 그래프 구조이다.
그래프
위의 유향 그래프 구조를 그래프의 방향(영어: orientation)이라고 한다.
의 방향은 부분 집합
![{\displaystyle D\subseteq \operatorname {V} (\Gamma )\times \operatorname {V} (\Gamma )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d4598d78de7633d8da6968f3c4865ba2f5b89c6)
![{\displaystyle \{\{u,v\}\colon (u,v)\in D\}=\operatorname {E} (\Gamma )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/64cf654857dd8f47d332b81784771621e2ce26a4)
로 표시된다.
다음이 주어졌다고 하자.
- 유향 그래프
![{\displaystyle (\Gamma ,D)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c10d552add0bef92c6fe9fea082236c1c878d13a)
속의 (꼭짓점과 변이 겹치지 않는) 짝수 길이의 순환 ![{\displaystyle C=(v_{0},v_{1},\dotsc ,v_{2n-1},v_{2n}=v_{0})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/311615f9569525e3e304bfde44b4ddaf804ebb3f)
만약
를 (시계 방향 또는 반시계 방향으로) 순회(巡廻)할 때,
와 일치하는 방향으로 순회되는 변이 홀수 개라면, 즉
![{\displaystyle 2\nmid |\{i\in \mathbb {Z} /(2n)\colon (v_{i},v_{i+1})\in D\}|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e1cf5a2fc09af4776b6f441cb7df3cdcab539e49)
이라면,
를
-홀수 순환(영어:
-oddly oriented cycle)이라고 한다.
(
의 길이가 짝수이므로,
의 순회 방향은 상관이 없다.)
다음이 주어졌다고 하자.
- 유한 그래프
![{\displaystyle \Gamma }](https://wikimedia.org/api/rest_v1/media/math/render/svg/4cfde86a3f7ec967af9955d0988592f0693d2b19)
의 방향 ![{\displaystyle D\subseteq \operatorname {V} (\Gamma )^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d149742f52500dec9cb0fba1ccf067fbd686e91)
의 완벽 부합 ![{\displaystyle M\subseteq \operatorname {E} (\Gamma )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8e079541f91d62dc5a3f372e99c906c15d227fce)
위의 임의의 전순서. 이에 따라,
의 꼭짓점 집합이
이라고 여길 수 있다.
이제,
의 원소들이 (임의의 순서로)
![{\displaystyle \{(v_{1},v_{2}),(v_{3},v_{4}),\dotsc ,(v_{2n-1},v_{2n})\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a4d0f1d7507c64dc1d06a2172663ce0ec1c3b8e3)
이라고 하자. 그렇다면,
의
-부호는 다음과 같다.
![{\displaystyle \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\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1dc5716b17f81a7ea1eacf4f7366d0c8f226f827)
여기서 우변은 순열의 부호, 즉 군 준동형
이다.
이 값은
의 원소들의 전순서에 의존하지 않지만, 물론
위의 전순서에는 의존한다.
다음이 주어졌다고 하자.
- 그래프
![{\displaystyle \Gamma }](https://wikimedia.org/api/rest_v1/media/math/render/svg/4cfde86a3f7ec967af9955d0988592f0693d2b19)
의 방향 ![{\displaystyle D}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f34a0c600395e5d4345287e21fb26efd386990e6)
이제,
위에 임의의 전순서를 부여하였을 때, 만약
위의 임의의 두 완벽 부합
,
에 대하여
![{\displaystyle \operatorname {sgn} _{D}(M)=\operatorname {sgn} _{D}(M')}](https://wikimedia.org/api/rest_v1/media/math/render/svg/91bfd7ad7a7a5d0cc0be9a3a73c56bf00b4201ac)
이라면,
를
의 파프 방향이라고 한다.
보다 일반적으로, 다음이 주어졌다고 하자.
다음이 주어졌다고 하자.
- 유한 그래프
![{\displaystyle \Gamma }](https://wikimedia.org/api/rest_v1/media/math/render/svg/4cfde86a3f7ec967af9955d0988592f0693d2b19)
의 방향 ![{\displaystyle D_{1},\dotsc ,D_{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/671f67ba8e99e31f1307847f5221c181eec96f71)
- 유리수
![{\displaystyle \alpha _{1},\dotsc ,\alpha _{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/83609251b340d7414ca55a2074f293b995f7ca37)
만약
에 임의의 전순서를 부여하였을 때, 임의의 완벽 부합
에 대하여,
![{\displaystyle \alpha _{1}\operatorname {sgn} _{D_{1}}(M)+\dotsb +\alpha _{k}\operatorname {sgn} _{D_{k}}(M)=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ebe8d3eec56b5f09c9348b8343f2ea275c897ba7)
이라면,
![{\displaystyle (D_{i},\alpha _{i})_{1\leq i\leq k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d15eccecce6d04b990dd95b270f985bd586eec23)
를
위의
-파프 방향이라고 한다.
유한 그래프
위의
-파프 방향
이 주어졌다고 하자. 그렇다면,
의 완벽 부합의 수
![{\displaystyle \operatorname {Z} _{\Gamma }(1,0)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cb6ba1a00547dc0164171f80701c661adf7185ff)
은 다음과 같다.
![{\displaystyle \operatorname {Z} _{\Gamma }(1,0)=\left|\sum _{i=1}^{k}\alpha _{i}\operatorname {Pf} \left(\operatorname {Inc} (\Gamma ,D_{i})\right)\right|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5cc2ad88a83aeae57f90b999d2e4d559d2bbf272)
여기서
은 짝수 크기 반대칭 행렬의 파피안이다.
는 유향 그래프
의 부호 인접 행렬이다. 즉, 다음과 같다.
![{\displaystyle \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 ))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cda377223b21d6b376a1ccfb7688a30f86a7d220)
다음이 주어졌다고 하자.
- 유한 유향 그래프
![{\displaystyle (\Gamma ,D)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c10d552add0bef92c6fe9fea082236c1c878d13a)
- 콤팩트 유향 곡면
. 그 종수가
라고 하자.
- 매장
. 이에 따라,
는 유한 CW 복합체를 이룬다. (즉,
는 유한 개의 2차원 열린 공들의 분리합집합이다.)
그렇다면, 만약 다음 조건이 성립한다면,
를 카스텔레인 방향(Kasteleyn方向, 영어: Kasteleyn orientation)이라고 한다.
의 임의의 2-세포의 경계
은
-홀수 순환이다.
위의 카스텔레인 방향들은
위의 세타 지표, 즉 스핀 구조와 표준적으로 일대일 대응한다. 이에 따라,
위에는
개의 카스텔레인 방향들이 존재하며, 이들에 적절한
![{\displaystyle \alpha _{i}=\pm 2^{-g}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c82368399e9b82d07ebee0d30d99f86459db84d)
계수를 부여할 경우 이들은
-파프 방향을 이룬다.
특히,
일 경우, 임의의 평면 그래프 위의 카스텔레인 방향은 (1-)파프 방향을 이룬다. 이에 따라, 모든 평면 그래프는 파프 방향을 갖는다.
피터르 빌럼 카스텔레인(네덜란드어: Pieter Willem Kasteleyn, 1924~1996)이 도입하였다. “파프 방향”이라는 용어는 요한 프리드리히 파프의 이름을 딴 것이다. 파프는 파피안을 도입하였는데, 파프 방향의 부호 인접 행렬의 파피안으로 완벽 부합의 수를 계산할 수 있기 때문에 이와 같은 이름이 붙었다.