텃 다항식 문서 원본 보기

{{위키데이터 속성 추적}}
[[그래프 이론]]과 [[매트로이드 이론]]에서 '''텃 다항식'''(Tutte多項式, {{llang|en|Tutte polynomial}})은 [[유한 그래프]] 및 유한 [[매트로이드]]에 대응되는 2변수 정수 계수 [[다항식]]이다. 그래프 및 매트로이드의 다양한 성질들을 텃 다항식의 특별한 값으로 얻을 수 있다.

== 정의 ==
유한 매트로이드 <math>(E,\mathcal I)</math>의 텃 다항식은 다음과 같은 2변수 다항식
:<math>T_E(x,y)\in\mathbb Z[x,y]</math>
이다.
:<math>T_E(x,y)=\sum_{S\subseteq E}(x-1)^{\operatorname{rank}(E|S)}(y-1)^{|S|-\operatorname{rank}(S|\varnothing)}</math>

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

== 성질 ==
매트로이드의 텃 다항식은 다음을 만족시킨다.
* <math>T_E(1,1)</math>은 <math>E</math>의 기저의 수이다.
* <math>T_E(2,1)</math>은 <math>E</math>의 독립 집합의 수이다.
* <math>T_E(1,2)</math>은 <math>E</math>의 [[부분 집합]] 가운데 폐포가 <math>E</math> 전체인 것들의 수이다.
* <math>T_E(2,2)=2^{|E|}</math>은 <math>E</math>의 모든 [[부분 집합]]의 수이다.
또한, 임의의 두 매트로이드 <math>E</math>, <math>E'</math>에 대하여
:<math>T_{E\oplus E'}(x,y)=T_E(x,y)T_{E'}(x,y)</math>
이며, 또한
:<math>T_{E^*}(x,y)=T_E(y,x)</math>
이다.

=== 그래프의 경우 ===
[[유한 그래프]] <math>\Gamma</math>의 순환 매트로이드의 텃 다항식은 다음과 같다.
:<math>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)| }</math>
여기서
* <math>\operatorname{Conn}(-)</math>은 [[연결 성분]]의 집합이며, <math>|\operatorname{Conn}(-)|</math>은 그 [[집합의 크기]], 즉 [[연결 성분]]의 수이다.

== 역사 ==
[[윌리엄 토머스 텃]]이 도입하였다.

== 외부 링크 ==
* {{eom|title=Tutte polynomial}}
* {{매스월드|id=TuttePolynomial|title=Tutte polynomial}}

{{전거 통제}}

[[분류:계산 문제]]
[[분류:그래프 이론]]
[[분류:다항식]]
[[분류:매트로이드 이론]]