텃 다항식

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

 정의 
유한 매트로이드 의 텃 다항식은 다음과 같은 2변수 다항식

이다.

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

 성질 
매트로이드의 텃 다항식은 다음을 만족시킨다.
 은 의 기저의 수이다.
 은 의 독립 집합의 수이다.
 은 의 부분 집합 가운데 폐포가  전체인 것들의 수이다.
 은 의 모든 부분 집합의 수이다.
또한, 임의의 두 매트로이드 , 에 대하여

이며, 또한

이다.

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

여기서
 은 연결 성분의 집합이며, 은 그 집합의 크기, 즉 연결 성분의 수이다.

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

 외부 링크 



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