파프 방향

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

 정의 
그래프  위의 유향 그래프 구조를 그래프의 방향()이라고 한다. 의 방향은 부분 집합

로 표시된다.

 홀수 순환 
다음이 주어졌다고 하자.
 유향 그래프 
  속의 (꼭짓점과 변이 겹치지 않는) 짝수 길이의 순환 
만약 를 (시계 방향 또는 반시계 방향으로) 순회(巡廻)할 때, 와 일치하는 방향으로 순회되는 변이 홀수 개라면, 즉

이라면, 를 -홀수 순환()이라고 한다.

(의 길이가 짝수이므로, 의 순회 방향은 상관이 없다.)

 부합의 부호 
다음이 주어졌다고 하자.
 유한 그래프 
 의 방향 
 의 완벽 부합 
  위의 임의의 전순서. 이에 따라, 의 꼭짓점 집합이 이라고 여길 수 있다.
이제, 의 원소들이 (임의의 순서로)

이라고 하자. 그렇다면, 의 -부호는 다음과 같다.

여기서 우변은 순열의 부호, 즉 군 준동형 이다.

이 값은 의 원소들의 전순서에 의존하지 않지만, 물론  위의 전순서에는 의존한다.

 파프 방향 
다음이 주어졌다고 하자.
 그래프 
 의 방향 
이제,  위에 임의의 전순서를 부여하였을 때, 만약  위의 임의의 두 완벽 부합 , 에 대하여

이라면, 를 의 파프 방향이라고 한다.

보다 일반적으로, 다음이 주어졌다고 하자.
다음이 주어졌다고 하자.
 유한 그래프 
 의 방향 
 유리수 
만약 에 임의의 전순서를 부여하였을 때, 임의의 완벽 부합 에 대하여,

이라면,

를  위의 -파프 방향이라고 한다.

 성질 
 완벽 부합의 수 
유한 그래프  위의 -파프 방향 이 주어졌다고 하자. 그렇다면, 의 완벽 부합의 수

은 다음과 같다.

여기서
 은 짝수 크기 반대칭 행렬의 파피안이다.
 는 유향 그래프 의 부호 인접 행렬이다. 즉, 다음과 같다.


 카스텔레인 방향 
다음이 주어졌다고 하자.
 유한 유향 그래프 
 콤팩트 유향 곡면 . 그 종수가 라고 하자.
 매장 . 이에 따라, 는 유한 CW 복합체를 이룬다. (즉, 는 유한 개의 2차원 열린 공들의 분리합집합이다.)
그렇다면, 만약 다음 조건이 성립한다면, 를 카스텔레인 방향(Kasteleyn方向, )이라고 한다.
 의 임의의 2-세포의 경계 은 -홀수 순환이다.

 위의 카스텔레인 방향들은  위의 세타 지표, 즉 스핀 구조와 표준적으로 일대일 대응한다. 이에 따라,  위에는 개의 카스텔레인 방향들이 존재하며, 이들에 적절한

계수를 부여할 경우 이들은 -파프 방향을 이룬다.

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

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

 참고 문헌 




 외부 링크 


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