Tutte多項式

前提知識: 全域木, 彩色多項式, 多重グラフ, 双対グラフ

グラフの不変量の多くは、辺 $e$ を除いたグラフ $G-e$ と、$e$ を縮めたグラフ $G/e$ の値から計算できる。全域木の個数 $\tau$ は $\tau(G)=\tau(G-e)+\tau(G/e)$ を満たし（全域木 の定理「削除と縮約の漸化式」）、彩色多項式は $P_G=P_{G-e}-P_{G/e}$ を満たす（彩色多項式 の定理「削除縮約の公式」）。Tutte 多項式 $T(G;x,y)$ は、こうした漸化式を最も一般的な形で記録する 2 変数の多項式である。橋（除くと連結成分が増える辺）では $x$ を、ループでは $y$ を掛け、それ以外の辺では $T(G-e)+T(G/e)$ と分ける。
この規則は、どの辺から順に使うかを決めていないので、答えが順序によらないこと（well-definedness）を示す必要がある。この記事では、辺の部分集合 $A$ 全体にわたる和
$$ \sum_{A\subset E}(x-1)^{r(E)-r(A)}(y-1)^{|A|-r(A)} $$
（ランク生成関数）が同じ規則を満たすことを示して、それを証明する。そのうえで、変数に値を代入すると、全域木の個数 $T(G;1,1)$、彩色多項式、流れ多項式（至る所 $0$ でない流れの個数）、信頼性多項式（辺がランダムに壊れても連結である確率）が得られることを証明する。最後に、平面グラフの双対グラフ $G^{*}$ について $T(G^{*};x,y)=T(G;y,x)$ を示す。

設定

この記事のグラフは、全域木 の記事の定義「ループを許す多重グラフと基本用語」のとおり、有限集合 $V\neq\emptyset$、有限集合 $E$、各辺 $e$ に端点の集合 $\partial(e)$（$V$ の 1 元または 2 元の部分集合）を対応させる写像の組 $G=(V,E,\partial)$ とする。ループと平行辺を許し、平行辺は区別する。辺の削除 $G-e$ と、ループでない辺の縮約 $G/e$ は、同じ記事の定義「辺の削除と縮約」による。縮約で平行辺やループが生じうる。
$A\subset E$ について、全域部分グラフ $(V,A)$ の連結成分の個数を $c(A)$ と書き、
$$ r(A):=|V|-c(A) $$
を $A$ の階数（rank）という。$c(G):=c(E)$ とする。辺を 1 本加えると連結成分は減らないか 1 つ減るだけなので、$A\subset B$ なら $r(A)\le r(B)$ であり、$r(A)\le|A|$ である。
ループでない辺 $e$ で $c(E\setminus\{e\})>c(E)$ となるものを橋という。このとき $e$ の両端は $(V,E\setminus\{e\})$ の異なる成分にあり、$c(E\setminus\{e\})=c(E)+1$ である。ループでも橋でもない辺を通常の辺という。

定義と well-definedness

$|A|-r(A)$ は $A$ の退化次数（nullity）とも呼ばれ、$(V,A)$ の独立な閉路の個数を表す。$r(E)-r(A)$ は $A$ に辺を足して $E$ の連結成分までつなぐのに必要な辺の本数である。

規則 2〜4 をどの辺の順に使って計算しても、結果は同じ多項式 $R(G;x,y)$ になる。これが削除縮約による定義の well-definedness の意味である。削除縮約による定義は EM08 Definition 2（p. 5）、ランク生成関数による表示は同 Definition 3（p. 6）にある。ランク生成関数は階数 $r$ だけで書けているので、同じ式でマトロイドの Tutte 多項式も定義される。
規則をくり返すと、最後には橋とループだけからなるグラフに行き着く。橋が $i$ 本、ループが $j$ 本だけのグラフでは、規則 2・3 をくり返して $T=x^iy^j$ である。どの段階でも係数は足し合わされるだけなので、$T(G;x,y)$ の係数はすべて $0$ 以上の整数である。これはランク生成関数の形（$x-1$、$y-1$ の冪の和）からは見えない性質である。

例

三角形と三重辺 $\Theta$ の多項式は $x$ と $y$ を入れ換えた形になっている。$\Theta$ は三角形の双対グラフ（双対グラフ の記事の例「双対グラフの例」の 2）であり、これは thm-tp-duality の最初の例である。

$K_4$ から 1 辺を除いたグラフの全域木が $8$ 個、$K_4$ の全域木が $16$ 個であることは、行列木定理 の例「4 頂点の例」と Cayleyの公式 に合う（thm-tp-counting）。$C_n$（$n\ge3$）では、1 辺を除くと道、縮めると $C_{n-1}$（$C_2$ は二重辺）なので、帰納法で $T(C_n)=x^{n-1}+x^{n-2}+\dots+x+y$ である。

特殊化

全域部分グラフの数え上げ

$c(A)=c(E)$ となる森 $A$ を、$G$ の極大全域森という。$G$ が連結なら、極大全域森は全域木にほかならない。

$\tau$ の削除縮約の漸化式（全域木）と、ループ・橋での振る舞い（ループはどの全域木にも入らず、橋はすべての全域木に入る）を合わせれば、prf-tp-well-defined と同じ帰納法で 1 の後半を導くこともできる（連結なグラフからループや通常の辺を除いても、橋や通常の辺を縮めても連結なグラフが残るので、帰納法は連結なグラフの中で進む）。行列式で $\tau(G)$ を計算する 行列木定理 は、$T(G;1,1)$ の値を多項式時間で与えている。連結なグラフについての 1〜4 は EM08 Theorem 3（p. 9）である。

彩色多項式

ループを許すグラフ $G$ と正の整数 $k$ について、写像 $\varphi\colon V\to\{1,\dots,k\}$ で、どの辺の両端も異なる色になるものの個数を $P(G;k)$ と書く。ループがあれば $P(G;k)=0$ であり、平行辺は条件を変えない。$G$ が単純グラフなら、$P(G;k)$ は 彩色多項式 の $P_G(k)$ である。

たとえば $K_3$ では $(-1)^2k\,\bigl((1-k)^2+(1-k)\bigr)=k(k-1)(k-2)$、$m$ 辺の木では $(-1)^mk(1-k)^m=k(k-1)^m$ で、彩色多項式 の例「基本的なグラフの彩色多項式」と一致する。ループがあると $T$ は因子 $y$ をもつので $y=0$ で $0$ になり、$P=0$ と合う。彩色多項式 の削除縮約の公式 $P_G=P_{G-e}-P_{G/e}$ は、通常の辺については、$T$ の規則 4 を $x=1-k$、$y=0$ で書き直したものにあたる。lem-tp-whitney と thm-tp-chromatic は EM08 Theorem 10（p. 13）と Theorem 12（p. 14）である。

流れ多項式

$\Gamma$ を位数 $k$ の有限アーベル群とし、$G$ の各辺に向きを付けて、辺 $e$ の始点を $i(e)$、終点を $t(e)$ とする（ループでは $i(e)=t(e)$）。写像 $f\colon E\to\Gamma$ が、すべての頂点 $v$ で
$$ \sum_{t(e)=v}f(e)=\sum_{i(e)=v}f(e) $$
（入ってくる量と出ていく量が等しい）を満たすとき、$f$ を $\Gamma$-流れ という。ループは両辺に同じ量を加えるので条件に影響しない。どの辺でも $f(e)\neq0$ である $\Gamma$-流れを至る所 $0$ でない流れといい、その個数を $F(G;\Gamma)$ と書く。辺 $e$ の向きを逆にして $f(e)$ を $-f(e)$ に替えると一対一に対応するので、$F(G;\Gamma)$ は向きの付け方によらない。

$K_3$ では $(-1)^{3-2}(0+0+1-k)=k-1$ である。三角形の流れは向きをそろえると 3 辺で同じ値をとるので、$0$ でない値の選び方 $k-1$ 通りと一致する。橋があれば規則 3 により $T$ は $x$ で割り切れるので $T(0,y)=0$ であり、橋のあるグラフ（たとえば木）には至る所 $0$ でない流れがない。$K_4$ では $(k-1)(k-2)(k-3)$ になり、$\mathbb Z/4\mathbb Z$ でも $\mathbb Z/2\mathbb Z\times\mathbb Z/2\mathbb Z$ でも $6$ 個である。thm-tp-flow は EM08 Theorem 14（p. 16）で、同書は削除縮約による証明の概略を述べている。

信頼性多項式

$0\le p\le1$ とし、$G$ の各辺が独立に確率 $p$ で残り、確率 $1-p$ で壊れるとする。残った辺の集合を $A$ とするとき、$c(A)=c(G)$ となる確率（$G$ が連結なら、残った辺で $G$ が連結のままである確率）
$$ \mathrm{Rel}(G;p):=\sum_{c(A)=c(G)}p^{|A|}(1-p)^{|E|-|A|} $$
を $G$ の信頼性多項式（reliability polynomial）という。

$K_3$ では $(1-p)p^2\bigl(2+\frac1{1-p}\bigr)=3p^2-2p^3$ で、3 辺がすべて残るか、ちょうど 1 辺だけ壊れる確率 $p^3+3p^2(1-p)$ に等しい。連結なグラフについての thm-tp-reliability は EM08 Definition 8（p. 19）と Theorem 17（p. 20）である。

平面グラフの双対性

平面グラフ図と双対グラフの約束は 双対グラフ の記事のとおりとする。$G$ は平面に描いた有限単純グラフ（平面グラフ図）、$G^{*}$ はその双対グラフで、頂点は $G$ の面、辺は $G$ の各辺 $e$ に 1 本ずつ置いた $e^{*}$ である。$G^{*}$ はループや平行辺をもちうるが、Tutte 多項式はそれらを許すグラフで定義されている。$G^{*}$ は連結である（同じ記事の系「双対グラフの連結性」）。

1 は 双対グラフ の系「全域木の補集合は双対の全域木」からも分かる。2 は、面の彩色（地図の塗り分け）と流れが双対の関係にあることを述べている。たとえば $K_4$ は自己双対（双対グラフ の例の 3）で、表の $T(K_4)$ は $x$ と $y$ について対称であり、$P(K_4;k)=k(k-1)(k-2)(k-3)=k\,F(K_4;k)$ となる。thm-tp-duality は EM08 Proposition 2（p. 6）で、同書は階数の関係を確かめれば従うと述べている。

反例の表

関連項目

• 前提: 全域木, 多重グラフ, 包除原理, 森
• 特殊化: 彩色多項式, 行列木定理, Cayleyの公式
• 比較: 双対グラフ, 平面グラフ, マトロイド
• 発展: Heron–Rota–Welsh予想, 四色定理