파프 방향

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

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

1. 개요

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

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이 아닌 모든 항은 완전 매칭에 해당한다.^[9] 따라서, 방향을 찾아 파프의 모든 항의 부호를 정렬할 수 있다면, 파프의 절대값은 ''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''이다.^[9] 1967년, Kasteleyn은 평면 그래프가 효율적으로 계산 가능한 파프 방향을 갖는다는 것을 증명했다. 구체적으로, 평면 그래프 ''G''에 대해, ''H''를 ''G''의 방향 버전으로 정의하고, 평면 임베딩의 모든 면에 대해 시계 방향으로 홀수 개의 모서리가 방향을 갖도록 한다. 그러면 ''H''는 ''G''의 파프 방향이다.

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

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

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

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

보다 일반적인 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. 파프 방향

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

보다 일반적인 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이 아닌 모든 항은 완전 매칭에 해당한다.^[9] 따라서, 방향을 찾아 파프의 모든 항의 부호를 정렬할 수 있다면, 파프의 절대값은 ''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''이다.^[9] 1967년, Kasteleyn은 평면 그래프가 효율적으로 계산 가능한 파프 방향을 갖는다는 것을 증명했다. 구체적으로, 평면 그래프 ''G''에 대해, ''H''를 ''G''의 방향 버전으로 정의하고, 평면 임베딩의 모든 면에 대해 시계 방향으로 홀수 개의 모서리가 방향을 갖도록 한다. 그러면 ''H''는 ''G''의 파프 방향이다.

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

:

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

이며, 여기서 det(''A'')는 ''A''의 행렬식이다. 이 결과는 아서 케일리에 의한 것이다.^[10] 행렬식은 효율적으로 계산 가능하므로 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. 역사

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

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

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

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

4. 1. 한국의 연구 동향

5. 알고리즘

5. 1. FKT 알고리즘

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

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

# ''G''의 평면 그래프 임베딩을 계산한다.

# 입력 그래프 ''G''의 신장 트리 ''T''₁을 계산한다.

# ''T''₁에도 있는 ''G''의 각 가장자리에 임의의 방향을 부여한다.

# 평면 임베딩을 사용하여 ''G''의 쌍대 그래프와 동일한 정점 집합을 가진 (무방향) 그래프 ''T''₂를 생성한다.

# ''G''의 해당 면이 ''G''에서 ''T''₁에 없는 가장자리를 공유하는 경우 두 정점 사이에 ''T''₂에 가장자리를 생성한다. (''T''₂는 트리이다.)

# ''T''₂의 각 잎 ''v''에 대해 (루트도 아닌 경우):

## ''e''를 아직 방향이 지정되지 않은, ''v''에 해당하는 면에 있는 ''G''의 유일한 가장자리로 한다.

## 시계 방향으로 방향이 지정된 가장자리의 수가 홀수가 되도록 ''e''에 방향을 부여한다.

## ''T''₂에서 ''v''를 제거한다.

# 행렬식의 제곱근인 ''G''의 인접 행렬의 파프의 절대값을 반환한다.

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

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

5. 2. 일반화

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

일반적으로 완전 매칭을 계산하는 복잡성은 그래프 마이너에 대해 닫힌 그래프의 패밀리에 대해 특징지어졌다. 모든 얕은 소용돌이 격자를 포함하지 않는 마이너 닫힌 패밀리의 경우, 이 계산 문제는 다항식으로 풀 수 있는 '얕은 소용돌이 격자'라는 그래프 패밀리가 있다. 그러나

K_8

-마이너-프리 그래프와 같이 모든 얕은 소용돌이 격자를 포함하는 마이너 닫힌 패밀리의 경우 완전 매칭을 계산하는 문제는 #P-완전이다.^[12] 일반 그래프에서 완전 매칭의 수를 계산하는 것은 #P-완전이므로, FP, 즉 P의 함수 버전이 #P와 같지 않는 한, 입력 그래프에 대한 제한이 필요하다. 호소야 지수라고 알려진 매칭을 계산하는 것은 평면 그래프의 경우에도 #P-완전이다.^[13]

6. 응용

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

참조

_[1] 간행물 Accidental Algorithms https://www.american[...] 2008-01
_[2] 서적 Exactly Solved Models in Statistical Mechanics http://tpsrv.anu.edu[...] Dover Publications
_[3] 학회 Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP IEEE
_[4] 논문 What is a Dimer? https://www.ams.org/[...]
_[5] 논문 The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice
_[6] 논문 Dimer problem in statistical mechanics-an exact result
_[7] 논문 Dimer Statistics and Phase Transitions
_[8] 서적 Graph Theory and Theoretical Physics Academic Press
_[9] 학회 A survey of Pfaffian orientations of graphs http://people.math.g[...] European Mathematical Society
_[10] 논문 Sur les determinants gauches
_[11] 논문 NC algorithms for computing the number of perfect matchings in K_3,3-free graphs and related problems
_[12] 논문 Killing a vortex
_[13] 논문 Two-dimensional monomer-dimer systems are computationally intractable
_[14] 논문 Holographic algorithms http://people-aws.se[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com