텃 다항식

2. 정의

무방향 그래프 $G=(V,E)$의 텃 다항식은 다음과 같이 정의된다.

:$T\_G(x,y)=\backslash sum\backslash nolimits\_\{A\backslash subseteq\; E\}\; (x-1)^\{k(A)-k(E)\}(y-1)^\{k(A)+|A|-|V|\},$

여기서 $k(A)$는 그래프 $(V,A)$의 연결 요소의 수이다.

휘트니 랭크 생성 함수를 이용하여 정의할 수도 있다. $r(A)=|V|-k(A)$를 그래프 $(V,A)$의 랭크로 정의하면, 휘트니 랭크 생성 함수는 다음과 같다.

:$R\_G(u,v)=\backslash sum\backslash nolimits\_\{A\backslash subseteq\; E\}\; u^\{r(E)-r(A)\}\; v^\{|A|-r(A)\}.$

텃 다항식은 다음 변수 변환을 통해 휘트니 랭크 생성 함수와 동치이다.

:$T\_G(x,y)=R\_G(x-1,y-1).$

연결된 그래프 $G$에 대해, 텃 다항식을 다음과 같이 표현할 수 있다.

:$T\_G(x,y)=\backslash sum\backslash nolimits\_\{i,j\}\; t\_\{ij\}\; x^iy^j,$

여기서 $t\_\{ij\}$는 ''내부 활동''이 $i$이고 ''외부 활동''이 $j$인 스패닝 트리의 수이다.

텃 다항식은 삭제-축약 재귀식을 사용하여 정의될 수 있다. 그래프 $G$의 에지 축약 $G/uv$는 정점 $u$와 $v$를 병합하고 에지 $uv$를 제거하여 얻은 그래프이다. 에지 $uv$가 단순히 제거된 그래프는 $G\; -\; uv$로 쓴다. 그러면 텃 다항식은 다음의 재귀 관계를 만족한다.

:$T\_G=\; T\_\{G-e\}+T\_\{G/e\},$

여기서 $e$는 루프도 아니고 브리지도 아니다. 만약 $G$가 $i$개의 브리지와 $j$개의 루프를 포함하고 다른 에지가 없다면,

:$T\_G(x,y)=\; x^i\; y^j$

이다. 특히, $G$에 에지가 없으면 $T\_G=1$이다.

=== 매트로이드의 텃 다항식 ===

유한 매트로이드 $(E,\backslash mathcal\; I)$의 텃 다항식은 다음과 같은 2변수 다항식 $T\_E(x,y)\backslash in\backslash mathbb\; Z[x,y]$이다.

:$T\_E(x,y)=\backslash sum\_\{S\backslash subseteq\; E\}(x-1)^\{\backslash operatorname\{rank\}(E|S)\}(y-1)^$

2. 1. 그래프의 텃 다항식

2. 2. 매트로이드의 텃 다항식

또 다른 예로, 정팔면체 그래프의 텃 다항식은 다음과 같다.

:$\backslash begin\{align\}$

&12\,{y}^{2}{x}^{2}+11\,x+11\,y+40\,{y}^{3}+32\,{

y}^{2}+46\,yx+24\,x{y}^{3}+52\,x{y}^{2} \\

&+25\,{x}^{2}+29\,{y}^{4}+15\,{y

}^{5}+5\,{y}^{6}+6\,{y}^{4}x \\

&+39\,y{x}^{2}+20\,{x}^{3}+{y}^{7}+8\,y{x}^

{3}+7\,{x}^{4}+{x}^{5}

\end{align}

3. 1. 기본 성질

3. 2. 그래프의 경우

4. 특수화

$y=0$에서 텃 다항식은 색칠 다항식으로 특수화된다.

:$\backslash chi\_G(\backslash lambda)\; =\; (-1)^\{|V|-k(G)\}\; \backslash lambda^\{k(G)\}\; T\_G(1-\backslash lambda,0),$

여기서 $k(G)$는 ''G''의 연결 요소의 수를 나타낸다.

정수 λ에 대해 색상 다항식 $\backslash chi\_G(\backslash lambda)$의 값은 λ 색상 집합을 사용하여 ''G''의 정점 채색의 수와 같다. $\backslash chi\_G(\backslash lambda)$가 색상 집합에 의존하지 않는다는 것은 분명하다. 덜 명확한 것은 그것이 정수 계수를 갖는 다항식의 λ에서의 평가라는 것이다. 이를 확인하기 위해 다음을 관찰한다.

# ''G''에 ''n''개의 정점이 있고 변이 없으면 $\backslash chi\_G(\backslash lambda)\; =\; \backslash lambda^n$이다.

# ''G''에 루프(정점을 자체에 연결하는 단일 변)가 포함되어 있으면 $\backslash chi\_G(\backslash lambda)\; =\; 0$이다.

# ''e''가 루프가 아닌 변인 경우

::$\backslash chi\_G(\backslash lambda)\; =\; \backslash chi\_\{G\; -\; e\}(\backslash lambda)\; -\; \backslash chi\_\{G/e\}(\backslash lambda).$

위의 세 가지 조건은 변 삭제 및 축약의 시퀀스를 적용하여 $\backslash chi\_G(\backslash lambda)$를 계산할 수 있게 해준다. 그러나 삭제 및 축약의 다른 시퀀스가 동일한 값을 가져올 것이라는 보장은 없다. 이 보장은 $\backslash chi\_G(\backslash lambda)$가 재귀와 독립적으로 무언가를 계산한다는 사실에서 비롯된다. 특히,

:$T\_G(2,0)\; =\; (-1)^$

4. 1. 색칠 다항식

5. 특정 점에서의 값

5. 1. (1, 1)

5. 2. (2, 1)

5. 3. (1, 2)

5. 4. (2, 0)

5. 5. (0, 2)

5. 6. (0, -2)

6. 계산 복잡도

여러 계산 문제는 텃 다항식과 관련되어 있다. 가장 간단한 문제는 다음과 같다.

;'''입력: 그래프 $G$'''

;'''출력: $T\_G$의 계수'''

특히, 이 출력은 ''G''의 3-채색 수를 세는 것과 동일한 $T\_G(-2,0)$의 값을 계산할 수 있게 한다. 이 마지막 문제는 #P-완전이며, 심지어 평면 그래프의 집합으로 제한해도 마찬가지이므로, 주어진 그래프에 대한 텃 다항식의 계수를 계산하는 문제는 평면 그래프의 경우에도 #P-어려움이다.

훨씬 더 많은 관심이 텃$(x,y)$라고 불리는 문제군에 쏠리고 있으며, 이는 모든 복소수 쌍 $(x,y)$에 대해 정의된다.

;입력: 그래프 $G$

;출력: $T\_G(x,y)$의 값

이러한 문제의 난이도는 좌표 $(x,y)$에 따라 달라진다.

== 정확한 계산 ==

''x''와 ''y''가 모두 음이 아닌 정수이면, 문제 $T\_G(x,y)$는 #P에 속한다. 일반적인 정수 쌍의 경우, 텃 다항식은 음의 항을 포함하며, 이는 문제를 뺄셈 하에서 #P의 닫힌 꼴인 복잡도 클래스 GapP에 위치시킨다.^[24] 유리수 좌표 $(x,y)$를 수용하기 위해, #P의 유리수 유사체를 정의할 수 있다.^[24]

$T\_G(x,y)$를 정확하게 계산하는 계산 복잡성은 모든 $x,\; y\; \backslash in\; \backslash mathbb\{C\}$에 대해 두 클래스 중 하나로 분류된다. 문제는 다음 쌍을 제외하고는 #P-hard이다.

:$\backslash left\; \backslash \{\; (1,1),\; (-1,-1),\; (0,-1),\; (-1,0),\; (i,-i),\; (-i,i),\; \backslash left(j,j^2\; \backslash right),\; \backslash left(j^2,j\; \backslash right)\; \backslash right\; \backslash \},\; \backslash qquad\; j\; =\; e^\{\backslash frac\{2\; \backslash pi\; i\}\{3\}\}.$

이 경우에는 다항 시간 내에 계산 가능하다.^[25]

[[File:Tractable points of the Tutte polynomial in the real plane.svg|thumb|300px|right|

터트 평면.

실수 평면의 모든 점 $(x,y)$는 계산 문제 $T\_G(x,y)$에 해당한다.

빨간색 점에서는 문제가 다항 시간 안에 계산 가능하다.

파란색 점에서는 문제가 일반적으로 #P-hard이지만, 평면 그래프에 대해서는 다항 시간 안에 계산 가능하다.

흰색 영역의 모든 점에서는 문제가 이분 평면 그래프에 대해서도 #P-hard이다.

]]

문제가 평면 그래프 클래스로 제한되는 경우, 쌍곡선 $H\_2$의 점 역시 다항 시간 내에 계산 가능하게 된다. 다른 모든 점은 이분 평면 그래프에 대해서도 #P-hard로 남는다.^[26] 평면 그래프에 대한 이분법에 관한 논문에서, Vertigan은 (결론에서) 정점 차수가 최대 3인 그래프로 더 제한할 때도 동일한 결과가 적용된다고 주장하며, 단, nowhere-zero '''Z'''₃-flows를 계산하고 다항 시간 내에 계산 가능한 점 $T\_G(0,-2)$는 예외이다.^[27]

이러한 결과에는 몇 가지 주목할 만한 특수한 경우가 포함된다. 예를 들어, 아이징 모형의 분배 함수를 계산하는 문제는 일반적으로 #P-hard이지만, Onsager와 Fisher의 유명한 알고리즘은 평면 격자에 대해 이를 해결한다. 또한, 존스 다항식을 계산하는 것은 #P-hard이다. 마지막으로, 평면 그래프의 4색칠 수를 계산하는 것은 사색 정리에 의해 결정 문제가 자명함에도 불구하고 #P-complete이다. 반대로, 평면 그래프의 3색칠 수를 계산하는 것이 파시모니어스 환원을 통해 결정 문제가 NP-complete로 알려져 있기 때문에 #P-complete임을 아는 것은 쉽다.

== 근사 계산 ==

$(x-1)(y-1)=2$의 양의 가지에 대해서는 FPRAS (fully polynomial-time randomized approximation scheme)가 존재한다.^[28] 밀집 그래프(dense graph)에 대해서는 $x\; \backslash ge\; 1,\; y\; \backslash ge\; 1$인 영역에서 FPRAS가 존재한다.^[28]

정확한 계산만큼 상황이 잘 이해되지는 않지만, 평면의 넓은 영역이 근사하기 어렵다는 것이 알려져 있다.^[24]

6. 1. 정확한 계산

6. 2. 근사 계산

7. 역사

윌리엄 토머스 텃이 케임브리지 트리니티 칼리지 학부 시절 삭제-축약 공식에 대한 연구를 바탕으로 텃 다항식을 도입하였다.^[6] 텃은 완전 사각형과 신장 트리에 관심을 가졌고, 삭제-축약 재귀를 만족하는 그래프 불변량을 연구했다. 텃은 처음에 이 다항식을 ''W-함수''라 불렀고, 구성 요소에 곱해지는 경우 ''V-함수''라고 불렀다. 이후 "두 변수 다항식을 얻었는데, 여기서 변수 중 하나를 0으로 설정하고 부호를 조정함으로써 색상 다항식 또는 플로우 다항식을 얻을 수 있었다"고 하며, 이 함수를 ''이색체(dichromate)''라고 불렀으나, 일반적으로 "텃 다항식"으로 굳어졌다.^[6] 텃은 하슬러 휘트니가 유사한 계수를 알고 사용했기에 이러한 명칭이 불공정할 수 있다고 언급했다.^[6] 헨리 크래포가 텃 다항식을 매트로이드로 일반화하였다.^[8]

대수적 그래프 이론 연구 외에도, 1952년 통계 역학에서 포츠 모형의 분할 함수 연구가 진행되었다.^[8] 포츠 모형의 일반화인 무작위 클러스터 모델에 대한 포르투인과 카스테레인의 연구는 텃 다항식과의 관계를 보여주었다.^[9][8]

8. 알고리즘

삭제-축약 알고리즘은 텃 다항식을 계산하는 기본적인 재귀 알고리즘이다.^[18] 이 알고리즘은 주어진 그래프에서 루프나 브리지가 아닌 모서리 ''e''를 선택하여 삭제하거나 축약하는 방식으로 작동한다. 삭제된 그래프와 축약된 그래프 각각에 대해 텃 다항식을 재귀적으로 계산한 후, 두 결과를 더하여 전체 그래프의 텃 다항식을 얻는다.^[18] 이 알고리즘의 실행 시간은 그래프의 정점 수 ''n''과 모서리 수 ''m''에 대해 지수적( $O\; \backslash left\; (1.6180^\{n+m\}\; \backslash right\; )$ )이다.^[18] 하지만, 희소 그래프나 정규 그래프와 같이 특정 조건을 만족하는 그래프에 대해서는 실행 시간이 개선될 수 있다.^[19][20]

특정 경우, 가우스 소거법을 이용하여 텃 다항식을 다항 시간 내에 계산할 수 있다. 예를 들어, 연결 그래프의 신장 트리 개수($T\_G(1,1)$)는 키르히호프의 행렬-나무 정리를 통해 계산 가능하다. 또한, 평면 그래프의 경우 FKT 알고리즘을 사용하여 아이징 모델의 분배 함수를 효율적으로 계산할 수 있다.

마르코프 연쇄 몬테카를로 방법을 사용하면 텃 다항식의 근사값을 계산할 수 있다. 특히, 강자성 이징 모형의 분배 함수를 따르는 양의 가지($H\_2$)에 대해 임의로 좋은 근사치를 얻을 수 있다.^[23]

참조

_[1] 논문
_[2] 논문
_[3] 논문
_[4] 논문
_[5] 논문
_[6] 논문
_[7] 문서 Welsh
_[8] 논문
_[9] 논문
_[10] 논문
_[11] 논문
_[12] 논문
_[13] 논문
_[14] 논문
_[15] 논문
_[16] 논문
_[17] 논문
_[18] 논문
_[19] 논문
_[20] 논문
_[21] 논문
_[22] 논문
_[23] 논문
_[24] 논문
_[25] 논문
_[26] 논문
_[27] 논문
_[28] 논문
_[29] 논문