파프 방향

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

파프 방향은 그래프의 완전 매칭 수를 계산하는 데 사용되는 그래프의 방향이다. 파프 방향은 그래프의 파프의 부호를 정렬하여 절대값을 완전 매칭 수와 같게 만들며, FKT 알고리즘은 평면 그래프에 대해 이러한 방향을 찾는다. 파프 방향은 홀수 순환, 부합의 부호, 그리고 k-파프 방향과 같은 개념으로 정의된다. FKT 알고리즘은 평면 그래프의 평면 임베딩을 계산하고, 신장 트리를 구성하여 파프 방향을 찾는 방식으로 작동한다. 파프 방향은 통계 역학, 화학, 그리고 홀로그래픽 알고리즘과 같은 분야에 응용된다.

파프 방향

📚 더 읽어볼만한 페이지

평면 그래프 - 다듬은 정육면체
깎은 정육면체는 정육면체의 꼭짓점을 잘라 만든 다면체로, 6개의 정팔각형과 8개의 정삼각형으로 구성되고, 마름모 입방팔면체 등과 연관되며, 데카르트 좌표계와 트리보나치 수열로 꼭짓점 위치를 나타낼 수 있고, 키랄성 및 팔면체 대칭성을 가지며 여러 분야에 활용됩니다.
평면 그래프 - 정이십면체
정이십면체는 20개의 정삼각형 면으로 이루어진 볼록 정다면체로, 정반오각기둥 양쪽에 정오각뿔을 붙인 형태이며, 정십이면체와 쌍대 관계를 가지고 다양한 분야에서 활용된다.
그래프 이론 - 다이어그램
다이어그램은 2차원 기하학적 기호를 사용하여 정보를 시각적으로 표현하는 기술로, 과학, 공학, IT, 비즈니스 등 다양한 분야에서 활용되며 정보를 간략하게 나타내고 시각적 사고를 돕는다.
그래프 이론 - 쾨니히스베르크의 다리 문제
쾨니히스베르크의 다리 문제는 프레겔 강에 놓인 7개의 다리를 한 번씩만 건너 출발점으로 되돌아올 수 있는지 묻는 문제로, 오일러에 의해 그래프 이론적으로 분석되어 해결되었으며 그래프 이론의 탄생에 기여했다.
그래프 알고리즘 - 페이지랭크
페이지랭크는 래리 페이지와 세르게이 브린이 개발한 알고리즘으로, 하이퍼링크로 연결된 문서 집합에서 웹 페이지의 상대적 중요도를 측정하며, 링크를 투표로 간주하여 페이지 순위를 재귀적으로 결정하고, 구글 검색 엔진의 초기 핵심 알고리즘으로 활용되었으며, 다양한 분야에서 활용된다.
그래프 알고리즘 - 너비 우선 탐색
너비 우선 탐색은 그래프 탐색 알고리즘으로, 큐 자료구조를 사용하여 시작 노드에서 인접한 노드들을 우선적으로 탐색하며, 가중치가 없는 그래프에서 최단 경로를 찾는 데 유용하고 다양한 분야에 활용된다.

1. 개요
2. 정의
3. 성질
- 3.1. 완벽 부합의 수
- 3.2. 카스텔레인 방향
4. 역사
- 4.1. 한국의 연구 동향
5. 알고리즘
- 5.1. FKT 알고리즘
- 5.2. 일반화
6. 응용

2. 정의

그래프 $\Gamma$ 위의 유향 그래프 구조를 그래프의 방향(orientation^영어)이라고 한다. $\Gamma$ 의 방향은 부분 집합
: $D\subseteq\operatorname V(\Gamma)\times\operatorname V(\Gamma)$
: $\{\{u,v\}\colon (u,v)\in D\}=\operatorname E(\Gamma)$
로 표시된다.
그래프 G의 파프의 인접 행렬의 0이 아닌 모든 항은 완전 매칭에 해당한다. 따라서, 방향을 찾아 파프의 모든 항의 부호를 정렬할 수 있다면, 파프의 절대값은 G의 완전 매칭 수와 같다. FKT 알고리즘은 평면 그래프 G에 대해 이러한 작업을 수행하며, 이 알고리즘이 찾는 방향은 파프 방향이라고 한다.

G = (V, E)를 인접 행렬 A를 갖는 무방향 그래프라고 정의하고, PM(n)을 n개 요소를 쌍으로 분할하는 집합으로 정의하면, G의 완전 매칭 수는 다음과 같다.
: $\operatorname{PerfMatch}(G) = \sum_{M \in PM(|V|)} \prod_{(i,j) \in M} A_{i j}.$
n x n 행렬 A에 대한 파프는 다음과 같다.
: $\operatorname{pf}(A) = \sum_{M \in PM(n)} \operatorname{sgn}(M) \prod_{(i,j) \in M} A_{i j},$
여기서 sgn(M)은 M의 순열의 패리티이다. G의 파프 방향은 pf(B) = PerfMatch(G)인 인접 행렬 B를 가진 방향 그래프 H이다. 1967년, Kasteleyn은 평면 그래프가 효율적으로 계산 가능한 파프 방향을 갖는다는 것을 증명했다. 구체적으로, 평면 그래프 G에 대해, H를 G의 방향 버전으로 정의하고, 평면 임베딩의 모든 면에 대해 시계 방향으로 홀수 개의 모서리가 방향을 갖도록 한다. 그러면 H는 G의 파프 방향이다.

모든 비대칭 행렬 A에 대해,
: $\operatorname{pf}(A)^2 = \det(A),$
이며, 여기서 det(A)는 A의 행렬식이다. 이 결과는 아서 케일리에 의한 것이다. 행렬식은 효율적으로 계산 가능하므로 PerfMatch(G)도 효율적으로 계산 가능하다.

그래프의 방향 중, 임의의 두 완벽 부합의 부호가 같은 방향을 파프 방향이라고 정의한다.

보다 일반적인 k-파프 방향의 정의는 다음과 같다.

* 유한 그래프 $\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$ -파프 방향이라고 한다.

2.1. 홀수 순환

유향 그래프에서 짝수 길이의 순환 $C=(v_0,v_1,\dotsc,v_{2n-1},v_{2n}=v_0)$ 을 순회할 때, 방향과 일치하는 변의 개수가 홀수인 경우를 홀수 순환이라고 한다. 즉,
: $2\nmid|\{i\in\mathbb Z/(2n)\colon (v_i,v_{i+1})\in D\}|$
이라면, $C$ 를 $D$ -홀수 순환( $D$ -oddly oriented cycle^영어)이라고 한다. 순환의 길이가 짝수이므로, 순회 방향은 상관이 없다.

2.2. 부합의 부호

유한 그래프 $\Gamma$ 의 방향 $D\subseteq\operatorname V(\Gamma)^2$ 와 완벽 부합 $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)$ 위의 전순서에는 의존한다.

2.3. 파프 방향

그래프의 방향 중, 임의의 두 완벽 부합의 부호가 같은 방향을 파프 방향이라고 정의한다.

보다 일반적인 k-파프 방향의 정의는 다음과 같다.

* 유한 그래프 $\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$ -파프 방향이라고 한다.

그래프 G의 파프의 인접 행렬의 0이 아닌 모든 항은 완전 매칭에 해당한다. 따라서, 방향을 찾아 파프의 모든 항의 부호를 정렬할 수 있다면, 파프의 절대값은 G의 완전 매칭 수와 같다. FKT 알고리즘은 평면 그래프 G에 대해 이러한 작업을 수행하며, 이 알고리즘이 찾는 방향은 파프 방향이라고 한다.

G = (V, E)를 인접 행렬 A를 갖는 무방향 그래프라고 정의하고, PM(n)을 n개 요소를 쌍으로 분할하는 집합으로 정의하면, G의 완전 매칭 수는 다음과 같다.

: $\operatorname{PerfMatch}(G) = \sum_{M \in PM(|V|)} \prod_{(i,j) \in M} A_{i j}.$

n x n 행렬 A에 대한 파프는 다음과 같다.

: $\operatorname{pf}(A) = \sum_{M \in PM(n)} \operatorname{sgn}(M) \prod_{(i,j) \in M} A_{i j},$

여기서 sgn(M)은 M의 순열의 패리티이다. G의 파프 방향은 pf(B) = PerfMatch(G)인 인접 행렬 B를 가진 방향 그래프 H이다. 1967년, Kasteleyn은 평면 그래프가 효율적으로 계산 가능한 파프 방향을 갖는다는 것을 증명했다. 구체적으로, 평면 그래프 G에 대해, H를 G의 방향 버전으로 정의하고, 평면 임베딩의 모든 면에 대해 시계 방향으로 홀수 개의 모서리가 방향을 갖도록 한다. 그러면 H는 G의 파프 방향이다.

모든 비대칭 행렬 A에 대해,

: $\operatorname{pf}(A)^2 = \det(A),$

이며, 여기서 det(A)는 A의 행렬식이다. 이 결과는 아서 케일리에 의한 것이다. 행렬식은 효율적으로 계산 가능하므로 PerfMatch(G)도 효율적으로 계산 가능하다.

3. 성질

3.1. 완벽 부합의 수

유한 그래프 $\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))$

3.2. 카스텔레인 방향

유한 유향 그래프 $(\Gamma,D)$와 콤팩트 유향 곡면 $\Sigma\cong(\mathbb T^2)^{\#g}$ (종수 $g\in\mathbb N$)가 주어졌다고 하자. 매장 $\Gamma\hookrightarrow \Sigma$에 따라, $(\Sigma,\Gamma)$는 유한 CW 복합체를 이룬다. (즉, $\Gamma\setminus\Sigma$는 유한 개의 2차원 열린 공들의 분리합집합이다.)

만약 $(\Sigma,\Gamma)$의 임의의 2-세포의 경계 $C\subseteq\Gamma$가 $D$-홀수 순환일 경우, $D$를 카스텔레인 방향(Kasteleyn orientation^영어)이라고 한다.

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

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

4. 역사

요한 프리드리히 파프의 이름을 딴 "파프 방향"이라는 용어는 파피안을 도입한 파프의 업적에서 유래되었다. 파프 방향은 부호 인접 행렬의 파피안으로 완벽 부합의 수를 계산할 수 있게 해준다.

평면 완전 매칭을 세는 문제는 통계 역학과 화학에서 비롯되었으며, 특히 이원자 분자가 표면에 흡착되어 단일 층을 형성할 때 가능한 배열 방법의 수를 계산하는 문제와 관련이 있다. 이 문제의 해결에는 분배 함수가 중요한 역할을 하지만, 분배 함수를 직접 계산하는 것은 실용적이지 않다. 따라서, 1960년대 초반에는 "정확하게 풀 수 있다"는 개념이 엄격하게 정의되지 않았으나, 1965년 다항 시간 개념의 도입과 함께 컴퓨터 과학에서 엄격한 정의가 제공되었다. 1979년에는 #P-난해성 개념이 정의되면서 "정확하게 풀 수 없는" 계수 문제에 대한 표기법이 확립되었다.

이합체 모델은 두 개의 원자로 구성된 중합체의 결합을 설명하며, 그래프의 이합체 덮개 수를 계산하는 문제로 이어진다. 얼음 형태의 물 분자(H₂O) 결합 모델은 각 꼭짓점에서 들어오고 나가는 방향이 모두 같을 수 없는 방향성 있는 3-정규 그래프로 표현되며, 가능한 가장자리 방향의 수를 계산하는 문제도 파프 방향과 관련된다.

1961년, 피터르 빌럼 카스텔레인(Pieter Willem Kasteleyn, 1924~1996)과 네빌 템퍼리 및 마이클 피셔는 독립적으로 m × n 직사각형의 도미노 타일링 수를 계산하는 방법을 발견했다. 이는 m × n 격자 그래프에서 완전 매칭 수를 세는 것과 동일하다. 카스텔레인은 1967년에 이 결과를 모든 평면 그래프로 일반화했다.

4.1. 한국의 연구 동향

5. 알고리즘

5.1. FKT 알고리즘

파프의 인접 행렬의 0이 아닌 모든 항이 완전 매칭에 해당한다는 주요 통찰력을 바탕으로, FKT 알고리즘은 평면 그래프 G에 대해 파프 방향을 찾아 파프의 절대값이 G의 완전 매칭 수와 같도록 한다.

FKT 알고리즘은 다음과 같이 작동한다.

# G의 평면 그래프 임베딩을 계산한다.
# 입력 그래프 G의 신장 트리 T₁을 계산한다.
# T₁에도 있는 G의 각 가장자리에 임의의 방향을 부여한다.
# 평면 임베딩을 사용하여 G의 쌍대 그래프와 동일한 정점 집합을 가진 (무방향) 그래프 T₂를 생성한다.
# G의 해당 면이 G에서 T₁에 없는 가장자리를 공유하는 경우 두 정점 사이에 T₂에 가장자리를 생성한다. (T₂는 트리이다.)
# T₂의 각 잎 v에 대해 (루트도 아닌 경우):
## e를 아직 방향이 지정되지 않은, v에 해당하는 면에 있는 G의 유일한 가장자리로 한다.
## 시계 방향으로 방향이 지정된 가장자리의 수가 홀수가 되도록 e에 방향을 부여한다.
## T₂에서 v를 제거한다.
# 행렬식의 제곱근인 G의 인접 행렬의 파프의 절대값을 반환한다.

1967년, Kasteleyn은 평면 그래프가 효율적으로 계산 가능한 파프 방향을 갖는다는 것을 증명했다. 평면 그래프 G에 대해, H를 G의 방향 버전으로 정의하고, 평면 임베딩의 모든 면에 대해 시계 방향으로 홀수 개의 모서리가 방향을 갖도록 하면, H는 G의 파프 방향이 된다.

아서 케일리에 따르면, 모든 비대칭 행렬 A에 대해, \operatorname{pf}(A)^2 = \det(A)가 성립하며, 여기서 det(A)는 A의 행렬식이다. 행렬식은 효율적으로 계산 가능하므로 PerfMatch(G)도 효율적으로 계산 가능하다.

5.2. 일반화

비제이 바지라니는 FKT 알고리즘을 K_3,3에 위상동형인 부분 그래프를 포함하지 않는 그래프로 일반화했다. 쿠라토프스키 정리에 따르면, 유한 그래프는 K₅ (5개의 꼭짓점을 가진 완전 그래프) 또는 K_3,3 (크기가 3인 두 개의 파티션에 대한 완전 이분 그래프)에 위상동형인 부분 그래프를 포함하지 않을 때 평면 그래프이다.

일반적으로 완전 매칭을 계산하는 복잡성은 그래프 마이너에 대해 닫힌 그래프의 패밀리에 대해 특징지어졌다. 모든 얕은 소용돌이 격자를 포함하지 않는 마이너 닫힌 패밀리의 경우, 이 계산 문제는 다항식으로 풀 수 있는 '얕은 소용돌이 격자'라는 그래프 패밀리가 있다. 그러나 $K_8$ -마이너-프리 그래프와 같이 모든 얕은 소용돌이 격자를 포함하는 마이너 닫힌 패밀리의 경우 완전 매칭을 계산하는 문제는 #P-완전이다. 일반 그래프에서 완전 매칭의 수를 계산하는 것은 #P-완전이므로, FP, 즉 P의 함수 버전이 #P와 같지 않는 한, 입력 그래프에 대한 제한이 필요하다. 호소야 지수라고 알려진 매칭을 계산하는 것은 평면 그래프의 경우에도 #P-완전이다.

6. 응용

FKT 알고리즘은 매치게이트를 통해 평면 그래프에 대한 홀로그래픽 알고리즘에서 광범위하게 사용되어 왔다. 예를 들어, 위에 언급된 얼음 모형의 평면 버전은 기술적으로 #PL-3-NAE-SAT (NAE는 "not all equal"을 의미)라고 불린다. Valiant는 매치게이트를 사용하는 이 문제에 대한 다항 시간 알고리즘을 찾았다.