텃 다항식 - 오늘의AI위키

1. 개요

텃 다항식은 그래프 이론에서 사용되는 2변수 다항식으로, 그래프의 다양한 속성을 나타낸다. 그래프 G=(V,E)에 대해 다음과 같이 정의된다. T_G(x,y)=\sum\nolimits_{A\subseteq E} (x-1)^{k(A)-k(E)}(y-1)^{k(A)+|A|-|V|}. 텃 다항식은 색칠 다항식, 흐름 다항식, 존스 다항식, 신뢰도 다항식 등과 밀접한 관련이 있으며, 다양한 특수화를 통해 그래프의 여러 성질을 분석하는 데 활용된다. 텃 다항식은 삭제-축약 재귀식을 사용하여 계산할 수 있으며, 계산 복잡성은 특정 점에서의 값에 따라 달라진다. 윌리엄 토머스 텃에 의해 처음 도입되었으며, 매트로이드로 일반화되기도 했다.

이름	텃 다항식
분야	대수적 그래프 이론
발명가	윌리엄 토머스 텃
발견 시기	1940년대 후반

공식 정의	그래프 또는 행렬의 연결성을 대수적으로 표현하는 방법

변수	2개 (x, y)
응용 분야	그래프 채색 문제 아이스 모델 포츠 모델 매트로이드 이론

2. 정의

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

: $T_G(x,y)=\sum\nolimits_{A\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)=\sum\nolimits_{A\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)=\sum\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,\mathcal I)$ 의 텃 다항식은 다음과 같은 2변수 다항식 $T_E(x,y)\in\mathbb Z[x,y]$ 이다.

: $T_E(x,y)=\sum_{S\subseteq E}(x-1)^{\operatorname{rank}(E|S)}(y-1)^{|S|-\operatorname{rank}(S|\varnothing)}$

유한 그래프의 텃 다항식은 그 순환 매트로이드의 텃 다항식을 뜻한다.

=== 삭제-축약 재귀식 ===
텃 다항식은 삭제-축약 재귀식을 사용하여 정의할 수도 있다. 그래프 $G$ 의 에지 축약 $G/uv$ 는 정점 $u$ 와 $v$ 를 병합하고 에지 $uv$ 를 제거하여 얻은 그래프이며, 에지 $uv$ 가 단순히 제거된 그래프는 $G - uv$ 로 쓴다. 루프 또는 브리지가 아닌 모서리 e를 찾을 수 있는 한, 해당 모서리가 삭제될 때와 해당 모서리가 축약될 때 텃 다항식을 재귀적으로 계산하여 두 하위 결과를 더하여 그래프에 대한 전체 터트 다항식을 얻는다.

텃 다항식은 다음 재귀 관계에 의해 정의된다.

: $T_G= T_{G-e}+T_{G/e},$

여기서 $e$ 는 루프도 아니고 브리지도 아니다.

기본 사례는 $G$ 가 $i$ 개의 브리지와 $j$ 개의 루프를 포함하고 다른 에지가 없는 경우

: $T_G(x,y)= x^i y^j,$

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

2.1. 그래프의 텃 다항식

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

: $T_G(x,y)=\sum\nolimits_{A\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)=\sum\nolimits_{A\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)=\sum\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$ 이다.

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

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

: $T_E(x,y)=\sum_{S\subseteq E}(x-1)^{\operatorname{rank}(E|S)}(y-1)^$

👆

좌우로 밀어서 보기

,

여기서

k(A)

는 그래프

(V,A)

의 연결 요소의 수를 나타낸다.

휘트니 랭크 생성 함수는 다음과 같이 정의된다.

:

R_G(u,v)=\sum\nolimits_{A\subseteq E} u^{r(E)-r(A)} v^{|A|-r(A)}.

여기서

r(A)=|V|-k(A)

는

(V,A)

그래프의 랭크이다. 두 함수는 변수 변환을 통해 동일하며, 다음의 관계를 갖는다.

:

T_G(x,y)=R_G(x-1,y-1).

텃 다항식은 삭제-축약 재귀식을 사용하여 정의할 수 있다. 그래프

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,

2.3. 삭제-축약 재귀식

텃 다항식은 삭제-축약 재귀식을 사용하여 정의할 수도 있다. 그래프 $G$ 의 에지 축약 $G/uv$ 는 정점 $u$ 와 $v$ 를 병합하고 에지 $uv$ 를 제거하여 얻은 그래프이며, 에지 $uv$ 가 단순히 제거된 그래프는 $G - uv$ 로 쓴다. 루프 또는 브리지가 아닌 모서리 e를 찾을 수 있는 한, 해당 모서리가 삭제될 때와 해당 모서리가 축약될 때 텃 다항식을 재귀적으로 계산하여 두 하위 결과를 더하여 그래프에 대한 전체 터트 다항식을 얻는다.

텃 다항식은 다음 재귀 관계에 의해 정의된다.

: $T_G= T_{G-e}+T_{G/e},$

여기서 $e$ 는 루프도 아니고 브리지도 아니다.

기본 사례는 $G$ 가 $i$ 개의 브리지와 $j$ 개의 루프를 포함하고 다른 에지가 없는 경우

: $T_G(x,y)= x^i y^j,$

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

삭제-축약 알고리즘의 실행 시간 t는 그래프의 정점 수 n과 모서리 수 m으로 표현할 수 있다.

: $t(n+m)= t(n+m-1) + t(n+m-2),$

이는 피보나치 수에 따라 확장되는 재귀 관계이며, $m=O(n)$ 인 희소 그래프의 경우 실행 시간은 $\exp(O(n))$ 이다. 차수가 k인 정규 그래프의 경우, 스패닝 트리의 수는 특정 공식에 의해 제한될 수 있으며, 삭제-축약 알고리즘은 이 경계의 다항식 인자 내에서 실행된다.

3. 성질

텃 다항식은 여러 유용한 성질을 갖는다.

매트로이드의 텃 다항식은 다음을 만족시킨다.
* $T_E(1,1)$ 은 $E$ 의 기저의 수이다.
* $T_E(2,1)$ 은 $E$ 의 독립 집합의 수이다.
* $T_E(1,2)$ 은 $E$ 의 부분 집합 가운데 폐포가 $E$ 전체인 것들의 수이다.
* $T_E(2,2)=2^$

👆

좌우로 밀어서 보기

은

E

의 모든 부분 집합의 수이다.

임의의 두 매트로이드

E

,

E'

에 대하여
:

T_{E\oplus E'}(x,y)=T_E(x,y)T_{E'}(x,y)

이며, 또한
:

T_{E^*}(x,y)=T_E(y,x)

이다.

텃 다항식은 연결된 성분으로 인수분해된다. 만약

G

가 서로소 그래프

H

와

H'

의 합집합이라면,

:

T_G= T_H \cdot T_{H'}

만약

G

가 평면 그래프이고

G^*

가 그 쌍대 그래프를 나타낸다면,

:

T_G(x,y)= T_{G^*} (y,x)

특히, 평면 그래프의 색상 다항식은 쌍대 그래프의 흐름 다항식이다. 텃은 이러한 함수들을 V-함수라고 지칭한다.

동형 그래프는 동일한 텃 다항식을 가지지만, 그 역은 성립하지 않는다. 예를 들어,

m

개의 변을 가진 모든 나무의 텃 다항식은

x^m

이다.

텃 다항식은 종종 행

i

와 열

j

에서

x^iy^j

의 계수

t_{ij}

를 나열하여 표 형식으로 제공된다. 예를 들어, 페테르센 그래프의 텃 다항식은 다음과 같다.

:

\begin{align}36 x &+ 120 x^2 + 180 x^3 + 170x^4+114x^5 + 56x^6 +21 x^7 + 6x^8 + x^9 \\&+ 36y +84 y^2 + 75 y^3 +35 y^4 + 9y^5+y^6 \\&+ 168xy + 240x^2y +170x^3y +70 x^4y + 12x^5 y \\&+ 171xy^2+105 x^2y^2 + 30x^3y^2 \\&+ 65xy^3 +15x^2y^3 \\&+10xy^4,\end{align}

다음 표로 나타낼 수 있다.

👆

좌우로 밀어서 보기

0	36	84	75	35	9	1
36	168	171	65	10
120	240	105	15
180	170	30
170	70
114	12
56
21
6
1

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

\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. 기본 성질

텃 다항식은 연결된 성분으로 인수분해된다. 만약 $G$ 가 서로소 그래프 $H$ 와 $H'$ 의 합집합이라면,

: $T_G= T_H \cdot T_{H'}$

만약 $G$ 가 평면 그래프이고 $G^*$ 가 그 쌍대 그래프를 나타낸다면,

: $T_G(x,y)= T_{G^*} (y,x)$

특히, 평면 그래프의 색상 다항식은 쌍대 그래프의 흐름 다항식이다. 텃은 이러한 함수들을 V-함수라고 지칭한다.

3.2. 그래프의 경우

연결 성분으로의 인수분해: 만약 $G$ 가 서로소 그래프 $H$ 와 $H'$ 의 합집합이라면, 다음이 성립한다.

: $T_G= T_H \cdot T_{H'}$

평면 그래프와 쌍대 그래프: 만약 $G$ 가 평면 그래프이고 $G^*$ 가 그 쌍대 그래프를 나타낸다면, 다음이 성립한다.

: $T_G(x,y)= T_{G^*} (y,x)$

특히, 평면 그래프의 색상 다항식은 쌍대 그래프의 흐름 다항식이다. 텃은 이러한 함수들을 V-함수라고 지칭한다.

4. 특수화

y=0

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

:

\chi_G(\lambda) = (-1)^{|V|-k(G)} \lambda^{k(G)} T_G(1-\lambda,0),

여기서

k(G)

는 G의 연결 요소의 수를 나타낸다.

정수 λ에 대해 색상 다항식

\chi_G(\lambda)

의 값은 λ 색상 집합을 사용하여 G의 정점 채색의 수와 같다.

\chi_G(\lambda)

가 색상 집합에 의존하지 않는다는 것은 분명하다. 덜 명확한 것은 그것이 정수 계수를 갖는 다항식의 λ에서의 평가라는 것이다. 이를 확인하기 위해 다음을 관찰한다.

# G에 n개의 정점이 있고 변이 없으면

\chi_G(\lambda) = \lambda^n

이다.
# G에 루프(정점을 자체에 연결하는 단일 변)가 포함되어 있으면

\chi_G(\lambda) = 0

이다.
# e가 루프가 아닌 변인 경우

::

\chi_G(\lambda) = \chi_{G - e}(\lambda) - \chi_{G/e}(\lambda).

위의 세 가지 조건은 변 삭제 및 축약의 시퀀스를 적용하여

\chi_G(\lambda)

를 계산할 수 있게 해준다. 그러나 삭제 및 축약의 다른 시퀀스가 동일한 값을 가져올 것이라는 보장은 없다. 이 보장은

\chi_G(\lambda)

가 재귀와 독립적으로 무언가를 계산한다는 사실에서 비롯된다. 특히,

:

T_G(2,0) = (-1)^

👆

좌우로 밀어서 보기

\chi_G(-1)

는 비순환 방향의 수를 제공한다.

쌍곡선

xy=1

을 따라 평면 그래프의 텃 다항식은 관련된 교호 매듭의 존스 다항식으로 특수화된다.

x=0

에서 텃 다항식은 조합론에서 연구되는 흐름 다항식으로 특수화된다. 연결된 무방향 그래프 G와 정수 k에 대해, 영-아닌 k-흐름은 G의 임의의 방향의 변에

1,2,\dots,k-1

의 "흐름" 값을 할당하여 각 정점에 들어오고 나가는 총 흐름이 모듈로 k로 합동하도록 하는 것이다. 흐름 다항식

C_G(k)

는 영-아닌 k-흐름의 수를 나타낸다. 이 값은 색 다항식과 밀접하게 관련되어 있으며, 실제로 G가 평면 그래프인 경우, G의 색 다항식은 그 쌍대 그래프

G^*

의 흐름 다항식과 동일하다.

> 정리 (Tutte).
>
>:

C_G(k)=k^{-1} \chi_{G^*}(k).

텃 다항식과의 관계는 다음과 같다.

:

C_G(k)= (-1)^{|E|-|V|+k(G)} T_G(0,1-k).

x=1

에서 텃 다항식은 네트워크 이론에서 연구되는 모든 터미널 신뢰도 다항식으로 특수화된다. 연결된 그래프 G에서 확률 p로 각 모서리를 제거하면, 이는 임의의 모서리 실패에 따른 네트워크를 모델링한다. 신뢰도 다항식은 p에 대한 다항식인 함수

R_G(p)

로, 모서리가 실패한 후 G의 모든 정점 쌍이 연결되어 있을 확률을 제공한다. 텃 다항식과의 관계는 다음과 같다.

:

R_G(p) = (1-p)^{|V|-k(G)} p^{|E|-|V|+k(G)} T_G \left (1, \tfrac{1}{p} \right).

Tutte 평면에 그려진 아이징 모델과 3- 및 4-상태 포츠 모델의 분할 함수.

쌍곡선

(x-1)(y-1)=q

에서 텃 다항식은

q

-상태 포츠 모형의 분할 함수로 특수화된다. 특히

q=2

인 경우, 아이징 모형의 분할 함수와 관련된다.

xy 평면에서 쌍곡선

H_2: \quad (x-1)(y-1)=2

를 정의하면, 텃 다항식은 통계 물리학에서 연구된 아이징 모형의 분할 함수

Z(\cdot)

로 특수화된다. 특히, 쌍곡선

H_2

를 따라 두 모델은 다음 방정식으로 관련된다:

:

Z(G) = 2\left(e^{-\alpha}\right)^{|E| - r(E)} \left(4 \sinh \alpha \right )^{r(E)}  T_G \left (\coth \alpha, e^{2 \alpha} \right).

여기서

(\coth \alpha - 1) \left(e^{2 \alpha} - 1 \right ) = 2

는 모든 복소수 α에 대해 성립한다.

일반적으로, 모든 양의 정수 q에 대해 쌍곡선

H_q: \quad (x-1)(y-1)=q

를 정의하면, 텃 다항식은 q-상태 포츠 모델의 분할 함수로 특수화된다. 포츠 모델 프레임워크에서 분석된 다양한 물리량은

H_q

의 특정 부분으로 변환된다.

👆

좌우로 밀어서 보기

포츠 모델과 Tutte 평면 간의 대응관계
\| Tutte 다항식
강자성	$H_q$ 의 양의 가지
반강자성	$y>0$ 인 $H_q$ 의 음의 가지
고온	$H_q$ 의 점근선 $y=1$
저온 강자성	$H_q$ 의 양의 가지, 점근선 $x=1$
영온 반강자성	그래프 q-채색, 즉 $x=1-q, y=0$

4.1. 색칠 다항식

y=0

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

:

\chi_G(\lambda) = (-1)^{|V|-k(G)} \lambda^{k(G)} T_G(1-\lambda,0),

여기서

k(G)

는 G의 연결 요소의 수를 나타낸다.

정수 λ에 대해 색상 다항식

\chi_G(\lambda)

의 값은 λ 색상 집합을 사용하여 G의 정점 채색의 수와 같다.

\chi_G(\lambda)

가 색상 집합에 의존하지 않는다는 것은 분명하다. 덜 명확한 것은 그것이 정수 계수를 갖는 다항식의 λ에서의 평가라는 것이다. 이를 확인하기 위해 다음을 관찰한다.
# G에 n개의 정점이 있고 변이 없으면

\chi_G(\lambda) = \lambda^n

이다.
# G에 루프(정점을 자체에 연결하는 단일 변)가 포함되어 있으면

\chi_G(\lambda) = 0

이다.
# e가 루프가 아닌 변인 경우

::

\chi_G(\lambda) = \chi_{G - e}(\lambda) - \chi_{G/e}(\lambda).

위의 세 가지 조건은 변 삭제 및 축약의 시퀀스를 적용하여

\chi_G(\lambda)

를 계산할 수 있게 해준다. 그러나 삭제 및 축약의 다른 시퀀스가 동일한 값을 가져올 것이라는 보장은 없다. 이 보장은

\chi_G(\lambda)

가 재귀와 독립적으로 무언가를 계산한다는 사실에서 비롯된다. 특히,

:

T_G(2,0) = (-1)^

👆

좌우로 밀어서 보기

\chi_G(-1)

는 비순환 방향의 수를 제공한다.

4.2. 존스 다항식

쌍곡선 $xy=1$ 을 따라 평면 그래프의 텃 다항식은 관련된 교호 매듭의 존스 다항식으로 특수화된다.

4.3. 흐름 다항식

x=0

에서 텃 다항식은 조합론에서 연구되는 흐름 다항식으로 특수화된다. 연결된 무방향 그래프 G와 정수 k에 대해, 영-아닌 k-흐름은 G의 임의의 방향의 변에

1,2,\dots,k-1

의 "흐름" 값을 할당하여 각 정점에 들어오고 나가는 총 흐름이 모듈로 k로 합동하도록 하는 것이다. 흐름 다항식

C_G(k)

는 영-아닌 k-흐름의 수를 나타낸다. 이 값은 색 다항식과 밀접하게 관련되어 있으며, 실제로 G가 평면 그래프인 경우, G의 색 다항식은 그 쌍대 그래프

G^*

의 흐름 다항식과 동일하다.

> 정리 (Tutte).
>
>:

C_G(k)=k^{-1} \chi_{G^*}(k).

텃 다항식과의 관계는 다음과 같다.

:

C_G(k)= (-1)^{|E|-|V|+k(G)} T_G(0,1-k).

4.4. 신뢰도 다항식

x=1

에서 텃 다항식은 네트워크 이론에서 연구되는 모든 터미널 신뢰도 다항식으로 특수화된다. 연결된 그래프 G에서 확률 p로 각 모서리를 제거하면, 이는 임의의 모서리 실패에 따른 네트워크를 모델링한다. 신뢰도 다항식은 p에 대한 다항식인 함수

R_G(p)

로, 모서리가 실패한 후 G의 모든 정점 쌍이 연결되어 있을 확률을 제공한다. 텃 다항식과의 관계는 다음과 같다.

:

R_G(p) = (1-p)^{|V|-k(G)} p^{|E|-|V|+k(G)} T_G \left (1, \tfrac{1}{p} \right).

4.5. 아이징 모형 및 포츠 모형

쌍곡선 $(x-1)(y-1)=q$ 에서 텃 다항식은 $q$ -상태 포츠 모형의 분할 함수로 특수화된다. 특히 $q=2$ 인 경우, 아이징 모형의 분할 함수와 관련된다.

xy 평면에서 쌍곡선

H_2: \quad (x-1)(y-1)=2

를 정의하면, 텃 다항식은 통계 물리학에서 연구된 아이징 모형의 분할 함수

Z(\cdot)

로 특수화된다. 특히, 쌍곡선

H_2

를 따라 두 모델은 다음 방정식으로 관련된다:

:

Z(G) = 2\left(e^{-\alpha}\right)^{|E| - r(E)} \left(4 \sinh \alpha \right )^{r(E)}  T_G \left (\coth \alpha, e^{2 \alpha} \right).

여기서

(\coth \alpha - 1) \left(e^{2 \alpha} - 1 \right ) = 2

는 모든 복소수 α에 대해 성립한다.

일반적으로, 모든 양의 정수 q에 대해 쌍곡선

H_q: \quad (x-1)(y-1)=q

를 정의하면, 텃 다항식은 q-상태 포츠 모델의 분할 함수로 특수화된다. 포츠 모델 프레임워크에서 분석된 다양한 물리량은

H_q

의 특정 부분으로 변환된다.

👆

좌우로 밀어서 보기

포츠 모델과 Tutte 평면 간의 대응관계
\| Tutte 다항식
강자성	$H_q$ 의 양의 가지
반강자성	$y>0$ 인 $H_q$ 의 음의 가지
고온	$H_q$ 의 점근선 $y=1$
저온 강자성	$H_q$ 의 양의 가지, 점근선 $x=1$
영온 반강자성	그래프 q-채색, 즉 $x=1-q, y=0$

5. 특정 점에서의 값

5.1. (1, 1)

$T_G(1,1)$ 은 신장 숲(사이클이 없고, 연결 요소의 수가 G와 같은 간선 부분 집합)의 수를 나타낸다. 그래프가 연결되어 있다면, $T_G(1,1)$ 은 신장 트리의 수를 나타낸다.

5.2. (2, 1)

숲의 개수는 $T_G(2,1)$ 로 계산되는 비순환적인 에지 부분 집합의 수를 나타낸다.

5.3. (1, 2)

$T_G(1,2)$ 는 G와 연결 요소의 수가 같은 신장 부분 그래프(가장자리 부분 집합)의 수를 계산한다.

5.4. (2, 0)

$T_G(2,0)$ 는 G의 비순환 방향의 수를 센다.

5.5. (0, 2)

$T_G(0,2)$ 는 그래프 G의 강하게 연결된 방향의 수를 계산한다.

5.6. (0, -2)

G가 4-정규 그래프일 때, $(-1)^{|V|+k(G)}T_G(0,-2)$ 는 G의 오일러 방향의 개수를 나타낸다. 여기서 $k(G)$ 는 G의 연결 요소의 수이다.

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에 위치시킨다. 유리수 좌표 $(x,y)$ 를 수용하기 위해, #P의 유리수 유사체를 정의할 수 있다.

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

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

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

터트 평면.실수 평면의 모든 점 (x,y)는 계산 문제 T_G(x,y)에 해당한다.빨간색 점에서는 문제가 다항 시간 안에 계산 가능하다.파란색 점에서는 문제가 일반적으로 #P-hard이지만, 평면 그래프에 대해서는 다항 시간 안에 계산 가능하다.흰색 영역의 모든 점에서는 문제가 이분 평면 그래프에 대해서도 #P-hard이다. — 터트 평면.
실수 평면의 모든 점 $(x,y)$ 는 계산 문제 $T_G(x,y)$ 에 해당한다.
빨간색 점에서는 문제가 다항 시간 안에 계산 가능하다.
파란색 점에서는 문제가 일반적으로 #P-hard이지만, 평면 그래프에 대해서는 다항 시간 안에 계산 가능하다.
흰색 영역의 모든 점에서는 문제가 이분 평면 그래프에 대해서도 #P-hard이다.

문제가 평면 그래프 클래스로 제한되는 경우, 쌍곡선

H_2

의 점 역시 다항 시간 내에 계산 가능하게 된다. 다른 모든 점은 이분 평면 그래프에 대해서도 #P-hard로 남는다. 평면 그래프에 대한 이분법에 관한 논문에서, Vertigan은 (결론에서) 정점 차수가 최대 3인 그래프로 더 제한할 때도 동일한 결과가 적용된다고 주장하며, 단, nowhere-zero Z₃-flows를 계산하고 다항 시간 내에 계산 가능한 점

T_G(0,-2)

는 예외이다.

이러한 결과에는 몇 가지 주목할 만한 특수한 경우가 포함된다. 예를 들어, 아이징 모형의 분배 함수를 계산하는 문제는 일반적으로 #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)가 존재한다. 밀집 그래프(dense graph)에 대해서는

x \ge 1, y \ge 1

인 영역에서 FPRAS가 존재한다.

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

6.1. 정확한 계산

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

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

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

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

문제가 평면 그래프 클래스로 제한되는 경우, 쌍곡선

H_2

의 점 역시 다항 시간 내에 계산 가능하게 된다. 다른 모든 점은 이분 평면 그래프에 대해서도 #P-hard로 남는다. 평면 그래프에 대한 이분법에 관한 논문에서, Vertigan은 (결론에서) 정점 차수가 최대 3인 그래프로 더 제한할 때도 동일한 결과가 적용된다고 주장하며, 단, nowhere-zero Z₃-flows를 계산하고 다항 시간 내에 계산 가능한 점

T_G(0,-2)

는 예외이다.

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

6.2. 근사 계산

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

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

7. 역사

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

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

8. 알고리즘

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

특정 경우, 가우스 소거법을 이용하여 텃 다항식을 다항 시간 내에 계산할 수 있다. 예를 들어, 연결 그래프의 신장 트리 개수(

T_G(1,1)

)는 키르히호프의 행렬-나무 정리를 통해 계산 가능하다. 또한, 평면 그래프의 경우 FKT 알고리즘을 사용하여 아이징 모델의 분배 함수를 효율적으로 계산할 수 있다.

마르코프 연쇄 몬테카를로 방법을 사용하면 텃 다항식의 근사값을 계산할 수 있다. 특히, 강자성 이징 모형의 분배 함수를 따르는 양의 가지(

H_2

)에 대해 임의로 좋은 근사치를 얻을 수 있다.