그래프 이론 에서 파프 방향 (Pfaff方向, 영어 : Pfaffian orientation )은 그래프 위의 완벽 부합 의 수를 쉽게 계산할 수 있게 하는 유향 그래프 구조이다.
그래프
Γ
{\displaystyle \Gamma }
유향 그래프 구조를 그래프의 방향 (영어 : orientation )이라고 한다.
Γ
{\displaystyle \Gamma }
D
⊆
V
(
Γ
)
×
V
(
Γ
)
{\displaystyle D\subseteq \operatorname {V} (\Gamma )\times \operatorname {V} (\Gamma )}
{
{
u
,
v
}
:
(
u
,
v
)
∈
D
}
=
E
(
Γ
)
{\displaystyle \{\{u,v\}\colon (u,v)\in D\}=\operatorname {E} (\Gamma )}
로 표시된다.
다음이 주어졌다고 하자.
유향 그래프
(
Γ
,
D
)
{\displaystyle (\Gamma ,D)}
Γ
{\displaystyle \Gamma }
순환
C
=
(
v
0
,
v
1
,
…
,
v
2
n
−
1
,
v
2
n
=
v
0
)
{\displaystyle C=(v_{0},v_{1},\dotsc ,v_{2n-1},v_{2n}=v_{0})}
만약
C
{\displaystyle C}
D
{\displaystyle D}
2
∤
|
{
i
∈
Z
/
(
2
n
)
:
(
v
i
,
v
i
+
1
)
∈
D
}
|
{\displaystyle 2\nmid |\{i\in \mathbb {Z} /(2n)\colon (v_{i},v_{i+1})\in D\}|}
이라면,
C
{\displaystyle C}
D
{\displaystyle D}
영어 :
D
{\displaystyle D}
(
C
{\displaystyle C}
C
{\displaystyle C}
다음이 주어졌다고 하자.
유한 그래프
Γ
{\displaystyle \Gamma }
Γ
{\displaystyle \Gamma }
D
⊆
V
(
Γ
)
2
{\displaystyle D\subseteq \operatorname {V} (\Gamma )^{2}}
Γ
{\displaystyle \Gamma }
완벽 부합
M
⊆
E
(
Γ
)
{\displaystyle M\subseteq \operatorname {E} (\Gamma )}
V
(
Γ
)
{\displaystyle \operatorname {V} (\Gamma )}
전순서 . 이에 따라,
Γ
{\displaystyle \Gamma }
{
1
,
2
,
…
,
2
n
}
{\displaystyle \{1,2,\dotsc ,2n\}}
이제,
M
{\displaystyle M}
{
(
v
1
,
v
2
)
,
(
v
3
,
v
4
)
,
…
,
(
v
2
n
−
1
,
v
2
n
)
}
{\displaystyle \{(v_{1},v_{2}),(v_{3},v_{4}),\dotsc ,(v_{2n-1},v_{2n})\}}
이라고 하자. 그렇다면,
M
{\displaystyle M}
D
{\displaystyle D}
부호 는 다음과 같다.
sgn
D
(
M
)
=
sgn
(
1
2
⋯
2
n
−
2
2
n
v
1
v
2
⋯
v
2
n
−
2
v
2
n
)
∈
{
+
1
,
−
1
}
{\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\}}
여기서 우변은 순열 의 부호, 즉 군 준동형
sgn
:
Sym
(
n
)
→
Cyc
(
2
)
=
{
±
1
}
{\displaystyle \operatorname {sgn} \colon \operatorname {Sym} (n)\to \operatorname {Cyc} (2)=\{\pm 1\}}
이 값은
M
{\displaystyle M}
전순서 에 의존하지 않지만, 물론
V
(
Γ
)
{\displaystyle \operatorname {V} (\Gamma )}
전순서 에는 의존한다.
다음이 주어졌다고 하자.
그래프
Γ
{\displaystyle \Gamma }
Γ
{\displaystyle \Gamma }
D
{\displaystyle D}
이제,
V
(
Γ
)
{\displaystyle \operatorname {V} (\Gamma )}
Γ
{\displaystyle \Gamma }
완벽 부합
M
{\displaystyle M}
M
′
{\displaystyle M'}
sgn
D
(
M
)
=
sgn
D
(
M
′
)
{\displaystyle \operatorname {sgn} _{D}(M)=\operatorname {sgn} _{D}(M')}
이라면,
D
{\displaystyle D}
Γ
{\displaystyle \Gamma }
파프 방향 이라고 한다.
보다 일반적으로, 다음이 주어졌다고 하자.
다음이 주어졌다고 하자.
유한 그래프
Γ
{\displaystyle \Gamma }
Γ
{\displaystyle \Gamma }
D
1
,
…
,
D
k
{\displaystyle D_{1},\dotsc ,D_{k}}
유리수
α
1
,
…
,
α
k
{\displaystyle \alpha _{1},\dotsc ,\alpha _{k}}
만약
V
(
Γ
)
{\displaystyle \operatorname {V} (\Gamma )}
전순서 를 부여하였을 때, 임의의 완벽 부합
M
⊆
E
(
Γ
)
{\displaystyle M\subseteq \operatorname {E} (\Gamma )}
α
1
sgn
D
1
(
M
)
+
⋯
+
α
k
sgn
D
k
(
M
)
=
1
{\displaystyle \alpha _{1}\operatorname {sgn} _{D_{1}}(M)+\dotsb +\alpha _{k}\operatorname {sgn} _{D_{k}}(M)=1}
이라면,
(
D
i
,
α
i
)
1
≤
i
≤
k
{\displaystyle (D_{i},\alpha _{i})_{1\leq i\leq k}}
를
Γ
{\displaystyle \Gamma }
k
{\displaystyle k}
파프 방향 이라고 한다.
유한 그래프
Γ
{\displaystyle \Gamma }
k
{\displaystyle k}
(
D
i
,
α
i
)
1
≤
i
≤
k
{\displaystyle (D_{i},\alpha _{i})_{1\leq i\leq k}}
Γ
{\displaystyle \Gamma }
완벽 부합 의 수
Z
Γ
(
1
,
0
)
{\displaystyle \operatorname {Z} _{\Gamma }(1,0)}
은 다음과 같다.
Z
Γ
(
1
,
0
)
=
|
∑
i
=
1
k
α
i
Pf
(
Inc
(
Γ
,
D
i
)
)
|
{\displaystyle \operatorname {Z} _{\Gamma }(1,0)=\left|\sum _{i=1}^{k}\alpha _{i}\operatorname {Pf} \left(\operatorname {Inc} (\Gamma ,D_{i})\right)\right|}
여기서
Pf
(
−
)
{\displaystyle \operatorname {Pf} (-)}
반대칭 행렬 의 파피안 이다.
Inc
(
Γ
,
D
)
{\displaystyle \operatorname {Inc} (\Gamma ,D)}
유향 그래프
(
Γ
,
D
)
{\displaystyle (\Gamma ,D)}
인접 행렬 이다. 즉, 다음과 같다.
⟨
u
|
Inc
(
Γ
,
D
)
|
v
⟩
=
{
1
(
u
,
v
)
∈
D
−
1
(
v
,
u
)
∈
D
0
(
u
,
v
)
,
(
v
,
u
)
∉
D
(
u
,
v
∈
V
(
Γ
)
)
{\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 ))}
다음이 주어졌다고 하자.
유한 유향 그래프
(
Γ
,
D
)
{\displaystyle (\Gamma ,D)}
콤팩트 유향 곡면
Σ
≅
(
T
2
)
#
g
{\displaystyle \Sigma \cong (\mathbb {T} ^{2})^{\#g}}
g
∈
N
{\displaystyle g\in \mathbb {N} }
매장
Γ
↪
Σ
{\displaystyle \Gamma \hookrightarrow \Sigma }
(
Σ
,
Γ
)
{\displaystyle (\Sigma ,\Gamma )}
CW 복합체 를 이룬다. (즉,
Γ
∖
Σ
{\displaystyle \Gamma \setminus \Sigma }
열린 공 들의 분리합집합 이다.) 그렇다면, 만약 다음 조건이 성립한다면,
D
{\displaystyle D}
카스텔레인 방향 (Kasteleyn方向, 영어 : Kasteleyn orientation )이라고 한다.
(
Σ
,
Γ
)
{\displaystyle (\Sigma ,\Gamma )}
C
⊆
Γ
{\displaystyle C\subseteq \Gamma }
D
{\displaystyle D}
(
Σ
,
Γ
)
{\displaystyle (\Sigma ,\Gamma )}
Σ
{\displaystyle \Sigma }
세타 지표 , 즉 스핀 구조 와 표준적으로 일대일 대응 한다. 이에 따라,
(
Σ
,
Γ
)
{\displaystyle (\Sigma ,\Gamma )}
4
g
{\displaystyle 4^{g}}
α
i
=
±
2
−
g
{\displaystyle \alpha _{i}=\pm 2^{-g}}
계수를 부여할 경우 이들은
4
g
{\displaystyle 4^{g}}
특히,
g
=
0
{\displaystyle g=0}
평면 그래프 위의 카스텔레인 방향은 (1-)파프 방향을 이룬다. 이에 따라, 모든 평면 그래프 는 파프 방향을 갖는다.
피터르 빌럼 카스텔레인(네덜란드어 : Pieter Willem Kasteleyn , 1924~1996)이 도입하였다. “파프 방향”이라는 용어는 요한 프리드리히 파프 의 이름을 딴 것이다. 파프는 파피안 을 도입하였는데, 파프 방향의 부호 인접 행렬 의 파피안 으로 완벽 부합 의 수를 계산할 수 있기 때문에 이와 같은 이름이 붙었다.
