텃 다항식

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

정의

유한 매트로이드 $(E,ℐ)$의 텃 다항식은 다음과 같은 2변수 다항식

$T_E(x,y)\in \mathbb{Z}[x,y]$

이다.

$T_E(x,y)=\sum _{S\subseteq E}(x-1{)}^{\mathrm{rank}(E|S)}(y-1{)}^{|S|-\mathrm{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^{\prime }$에 대하여

$T_{E\oplus E^{\prime }}(x,y)=T_E(x,y)T_{E^{\prime }}(x,y)$

이며, 또한

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

이다.

그래프의 경우

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

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

여기서

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

역사

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

외부 링크

• 틀:Eom
• 틀:매스월드