텃 다항식

그래프 이론과 매트로이드 이론에서 텃 다항식(Tutte多項式, 영어: Tutte polynomial)은 유한 그래프 및 유한 매트로이드에 대응되는 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)^{|S|-\operatorname {rank} (S|\varnothing )}$

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

성질

매트로이드의 텃 다항식은 다음을 만족시킨다.

• $T_{E}(1,1)$은 $E$의 기저의 수이다.
• $T_{E}(2,1)$은 $E$의 독립 집합의 수이다.
• $T_{E}(1,2)$은 $E$의 부분 집합 가운데 폐포가 $E$ 전체인 것들의 수이다.
• $T_{E}(2,2)=2^{|E|}$은 $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)$

이다.

그래프의 경우

유한 그래프 $\Gamma$의 순환 매트로이드의 텃 다항식은 다음과 같다.

$T_{\Gamma }(x,y)=\sum _{S\subseteq \operatorname {E} (\Gamma )}(x-1)^{|\operatorname {Conn} (S)|-|\operatorname {Conn} (\Gamma )|}(y-1)^{|\operatorname {Conn} (S)|+|A|-|\operatorname {V} (\Gamma )|}$

여기서

• $\operatorname {Conn} (-)$은 연결 성분의 집합이며, $|\operatorname {Conn} (-)|$은 그 집합의 크기, 즉 연결 성분의 수이다.

역사

윌리엄 토머스 텃이 도입하였다.

외부 링크

• “Tutte polynomial”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Tutte polynomial”. 《Wolfram MathWorld》 (영어). Wolfram Research.