Editing: 파프 방향

EDIT MODE

# 파프 방향

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

그래프 
  
    
      
        Γ
      
    
    {\displaystyle \Gamma }

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/4cfde86a3f7ec967af9955d0988592f0693d2b19)

위의 유향 그래프 구조를 그래프의 방향(영어: orientation)이라고 한다. 
  
    
      
        Γ
      
    
    {\displaystyle \Gamma }

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/4cfde86a3f7ec967af9955d0988592f0693d2b19)

의 방향은 부분 집합

로 표시된다.

다음이 주어졌다고 하자.

만약 
  
    
      
        C
      
    
    {\displaystyle C}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029)

를 (시계 방향 또는 반시계 방향으로) 순회(巡廻)할 때, 
  
    
      
        D
      
    
    {\displaystyle D}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/f34a0c600395e5d4345287e21fb26efd386990e6)

와 일치하는 방향으로 순회되는 변이 홀수 개라면, 즉

이라면, 
  
    
      
        C
      
    
    {\displaystyle C}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029)

를 
  
    
      
        D
      
    
    {\displaystyle D}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/f34a0c600395e5d4345287e21fb26efd386990e6)

-홀수 순환(D</math>-oddly oriented cycle"}},"i":0}}]}'>영어: 
  
    
      
        D
      
    
    {\displaystyle D}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/f34a0c600395e5d4345287e21fb26efd386990e6)

-oddly oriented cycle)이라고 한다.

(
  
    
      
        C
      
    
    {\displaystyle C}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029)

의 길이가 짝수이므로, 
  
    
      
        C
      
    
    {\displaystyle C}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029)

의 순회 방향은 상관이 없다.)

다음이 주어졌다고 하자.

이제, 
  
    
      
        M
      
    
    {\displaystyle M}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd)

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

이라고 하자. 그렇다면, 
  
    
      
        M
      
    
    {\displaystyle M}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd)

의 
  
    
      
        D
      
    
    {\displaystyle D}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/f34a0c600395e5d4345287e21fb26efd386990e6)

-부호는 다음과 같다.

여기서 우변은 순열의 부호, 즉 군 준동형 
  
    
      
        sgn
        :
        Sym
        ⁡
        (
        n
        )
        →
        Cyc
        ⁡
        (
        2
        )
        =
        {
        ±
        1
        }
      
    
    {\displaystyle \operatorname {sgn} \colon \operatorname {Sym} (n)\to \operatorname {Cyc} (2)=\{\pm 1\}}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/4196b5c6179ad3e37117fce7013735606e77247a)

이다.

이 값은 
  
    
      
        M
      
    
    {\displaystyle M}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd)

의 원소들의 전순서에 의존하지 않지만, 물론 
  
    
      
        V
        ⁡
        (
        Γ
        )
      
    
    {\displaystyle \operatorname {V} (\Gamma )}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/2834ee9df258babf8fe9cba6c6cf765d8e537949)

위의 전순서에는 의존한다.

다음이 주어졌다고 하자.

이제, 
  
    
      
        V
        ⁡
        (
        Γ
        )
      
    
    {\displaystyle \operatorname {V} (\Gamma )}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/2834ee9df258babf8fe9cba6c6cf765d8e537949)

위에 임의의 전순서를 부여하였을 때, 만약 
  
    
      
        Γ
      
    
    {\displaystyle \Gamma }

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/4cfde86a3f7ec967af9955d0988592f0693d2b19)

위의 임의의 두 완벽 부합 
  
    
      
        M
      
    
    {\displaystyle M}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd)

, 
  
    
      
        
          M
          ′
        
      
    
    {\displaystyle M'}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a3b2ef3304c46b5e7859eec0b1bc057c8eb3f75)

에 대하여

이라면, 
  
    
      
        D
      
    
    {\displaystyle D}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/f34a0c600395e5d4345287e21fb26efd386990e6)

를 
  
    
      
        Γ
      
    
    {\displaystyle \Gamma }

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/4cfde86a3f7ec967af9955d0988592f0693d2b19)

의 파프 방향이라고 한다.

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

만약 
  
    
      
        V
        ⁡
        (
        Γ
        )
      
    
    {\displaystyle \operatorname {V} (\Gamma )}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/2834ee9df258babf8fe9cba6c6cf765d8e537949)

에 임의의 전순서를 부여하였을 때, 임의의 완벽 부합 
  
    
      
        M
        ⊆
        E
        ⁡
        (
        Γ
        )
      
    
    {\displaystyle M\subseteq \operatorname {E} (\Gamma )}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/8e079541f91d62dc5a3f372e99c906c15d227fce)

에 대하여,

이라면,

를 
  
    
      
        Γ
      
    
    {\displaystyle \Gamma }

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/4cfde86a3f7ec967af9955d0988592f0693d2b19)

위의 
  
    
      
        k
      
    
    {\displaystyle k}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)

-파프 방향이라고 한다.

유한 그래프 
  
    
      
        Γ
      
    
    {\displaystyle \Gamma }

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/4cfde86a3f7ec967af9955d0988592f0693d2b19)

위의 
  
    
      
        k
      
    
    {\displaystyle k}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)

-파프 방향 
  
    
      
        (
        
          D
          
            i
          
        
        ,
        
          α
          
            i
          
        
        
          )
          
            1
            ≤
            i
            ≤
            k
          
        
      
    
    {\displaystyle (D_{i},\alpha _{i})_{1\leq i\leq k}}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/d15eccecce6d04b990dd95b270f985bd586eec23)

이 주어졌다고 하자. 그렇다면, 
  
    
      
        Γ
      
    
    {\displaystyle \Gamma }

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/4cfde86a3f7ec967af9955d0988592f0693d2b19)

의 완벽 부합의 수

은 다음과 같다.

여기서

다음이 주어졌다고 하자.

그렇다면, 만약 다음 조건이 성립한다면, 
  
    
      
        D
      
    
    {\displaystyle D}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/f34a0c600395e5d4345287e21fb26efd386990e6)

를 카스텔레인 방향(Kasteleyn方向, 영어: Kasteleyn orientation)이라고 한다.

(
        Σ
        ,
        Γ
        )
      
    
    {\displaystyle (\Sigma ,\Gamma )}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d06cbe727effaa72a28061284c61c287a027666)

위의 카스텔레인 방향들은 
  
    
      
        Σ
      
    
    {\displaystyle \Sigma }

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/9e1f558f53cda207614abdf90162266c70bc5c1e)

위의 세타 지표, 즉 스핀 구조와 표준적으로 일대일 대응한다. 이에 따라, 
  
    
      
        (
        Σ
        ,
        Γ
        )
      
    
    {\displaystyle (\Sigma ,\Gamma )}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d06cbe727effaa72a28061284c61c287a027666)

위에는 
  
    
      
        
          4
          
            g
          
        
      
    
    {\displaystyle 4^{g}}

![image](https://wikimedia.org/api/rest_v1/media/math/render/svg/d9a4351fa04ea6348e1825eb7db81eb66f9790c4)

개의 카스텔레인 방향들이 존재하며, 이들에 적절한

계수를 부여할 경우 이들은 
  
    
      
        
          4
          
            g

Cancel