Tutte polynomial: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Tutte polynomial''' --- полином Татта. If <math>G</math> has an empty edge set, then we set the ''' Tutte polynomial''' <math>t(G;x,y)</math> or <ma…»)
 
(нет различий)

Текущая версия от 17:57, 16 августа 2011

Tutte polynomial --- полином Татта.

If [math]\displaystyle{ G }[/math] has an empty edge set, then we set the Tutte polynomial [math]\displaystyle{ t(G;x,y) }[/math] or [math]\displaystyle{ t(G) }[/math] of [math]\displaystyle{ G }[/math] to be 1. Otherwise we have for any [math]\displaystyle{ e \in E(G) }[/math]

(R1) [math]\displaystyle{ t(G) = t(G\setminus e) + t(G/e) }[/math], if [math]\displaystyle{ e }[/math] is not a loop or a bridge,

(R2) [math]\displaystyle{ t(G) = xt(G\setminus e) }[/math], if [math]\displaystyle{ e }[/math] is a bridge,

(R3) [math]\displaystyle{ t(G) = yt(G\setminus e) }[/math], if [math]\displaystyle{ e }[/math] is a loop.

Here [math]\displaystyle{ (G/e) }[/math] is the contraction of the edge [math]\displaystyle{ e }[/math].