파프 방향

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

정의[편집]

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

로 표시된다.

홀수 순환[편집]

다음이 주어졌다고 하자.

  • 유향 그래프
  • 속의 (꼭짓점과 변이 겹치지 않는) 짝수 길이의 순환

만약 를 (시계 방향 또는 반시계 방향으로) 순회(巡廻)할 때, 와 일치하는 방향으로 순회되는 변이 홀수 개라면, 즉

이라면, -홀수 순환(영어: -oddly oriented cycle)이라고 한다.

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

부합의 부호[편집]

다음이 주어졌다고 하자.

  • 유한 그래프
  • 의 방향
  • 완벽 부합
  • 위의 임의의 전순서. 이에 따라, 의 꼭짓점 집합이 이라고 여길 수 있다.

이제, 의 원소들이 (임의의 순서로)

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

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

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

파프 방향[편집]

다음이 주어졌다고 하자.

  • 그래프
  • 의 방향

이제, 위에 임의의 전순서를 부여하였을 때, 만약 위의 임의의 두 완벽 부합 , 에 대하여

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

보다 일반적으로, 다음이 주어졌다고 하자. 다음이 주어졌다고 하자.

  • 유한 그래프
  • 의 방향
  • 유리수

만약 에 임의의 전순서를 부여하였을 때, 임의의 완벽 부합 에 대하여,

이라면,

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

성질[편집]

완벽 부합의 수[편집]

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

은 다음과 같다.

여기서

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

카스텔레인 방향[편집]

다음이 주어졌다고 하자.

  • 유한 유향 그래프
  • 콤팩트 유향 곡면 . 그 종수가 라고 하자.
  • 매장 . 이에 따라, 는 유한 CW 복합체를 이룬다. (즉, 는 유한 개의 2차원 열린 공들의 분리합집합이다.)

그렇다면, 만약 다음 조건이 성립한다면, 카스텔레인 방향(Kasteleyn方向, 영어: Kasteleyn orientation)이라고 한다.

  • 의 임의의 2-세포의 경계 -홀수 순환이다.

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

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

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

역사[편집]

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

참고 문헌[편집]

외부 링크[편집]