トゥッテ多項式

Tutte多項式 は、二色多項式またはTutte–Whitney 多項式とも呼ばれ、グラフ多項式です。これは2 変数の多項式であり、グラフ理論で重要な役割を果たします。これはすべての無向グラフ に対して定義され、グラフがどのように接続されているかに関する情報を含んでいます。これは と表記されます。 ${\displaystyle G}$${\displaystyle T_{G}}$

この多項式の重要性は、それに含まれる に関する情報に由来します。 もともとは代数グラフ理論において、グラフの色付けやゼロのないフローに関連する計数問題の一般化として研究されていましたが、結び目理論のジョーンズ多項式や統計物理学のポッツモデルの分割関数など、他の科学からのいくつかの有名な特殊化を含んでいます。 また、理論計算機科学におけるいくつかの中心的な計算問題の源でもあります。 ${\displaystyle G}$

Tutte 多項式には、いくつかの同等の定義があります。これは、ホイットニーの階数多項式、Tutte 自身の二色多項式、および単純な変換によるFortuin–Kasteleyn のランダム クラスター モデルと本質的に同等です。これは、本質的には、指定されたサイズと接続コンポーネントのエッジ セットの数を生成する関数であり、マトロイドに直接一般化されます。また、削除–縮小再帰によって定義できる最も一般的なグラフ不変量でもあります。グラフ理論とマトロイド理論に関するいくつかの教科書では、これに 1 章を割いています。^{[1] [2] [3]}

定義。無向グラフの場合、Tutte多項式は次のように 定義される。${\displaystyle G=(V,E)}$

${\displaystyle T_{G}(x,y)=\sum \nolimits _{A\subseteq E}(x-1)^{k(A)-k(E)}(y-1)^{k(A)+|A|-|V|},}$

ここで、 はグラフの連結成分の数を表します。この定義では、 が明確に定義されており、およびの多項式であることは明らかです。${\displaystyle k(A)}$${\displaystyle (V,A)}$${\displaystyle T_{G}}$${\displaystyle x}$${\displaystyle y}$

同じ定義は、グラフのランクを とすることで、わずかに異なる表記法で与えることができる。この場合、ホイットニーランク生成関数は次のように定義される。 ${\displaystyle r(A)=|V|-k(A)}$${\displaystyle (V,A)}$

${\displaystyle R_{G}(u,v)=\sum \nolimits _{A\subseteq E}u^{r(E)-r(A)}v^{|A|-r(A)}.}$

2 つの関数は、変数を単純に変更すると同等になります。

${\displaystyle T_{G}(x,y)=R_{G}(x-1,y-1).}$

タットの二色多項式 は、別の単純な変換の結果です。 ${\displaystyle Q_{G}}$

${\displaystyle T_{G}(x,y)=(x-1)^{-k(G)}Q_{G}(x-1,y-1).}$

タットの元の定義は同等だが、簡単には述べられない。連結については次のように設定する。 ${\displaystyle T_{G}}$${\displaystyle G}$

${\displaystyle T_{G}(x,y)=\sum \nolimits _{i,j}t_{ij}x^{i}y^{j},}$

ここで、 は内部アクティビティと外部アクティビティの全域木の数を表します。 ${\displaystyle t_{ij}}$ ${\displaystyle i}$ ${\displaystyle j}$

3番目の定義は、削除と縮小の繰り返しを使用します。グラフの辺の縮小は 、頂点とをマージして辺を削除することによって得られるグラフです。辺が削除されただけのグラフについては と書きます。すると、Tutte多項式は繰り返し関係によって定義されます。 ${\displaystyle G/uv}$${\displaystyle G}$${\displaystyle u}$${\displaystyle v}$${\displaystyle uv}$${\displaystyle G-uv}$${\displaystyle uv}$

${\displaystyle T_{G}=T_{G-e}+T_{G/e},}$

ループでもブリッジでもない場合には、基本ケースで ${\displaystyle e}$

${\displaystyle T_{G}(x,y)=x^{i}y^{j},}$

ブリッジとループが含まれ、他のエッジがない場合。特に、エッジが含まれない場合。 ${\displaystyle G}$${\displaystyle i}$${\displaystyle j}$${\displaystyle T_{G}=1}$${\displaystyle G}$

フォーチュインとカステリン（1972）による統計力学のランダムクラスターモデルは、さらに別の同等の定義を提供している。 ^[4]パーティション合計

${\displaystyle Z_{G}(q,w)=\sum \nolimits _{F\subseteq E}q^{k(F)}w^{|F|}}$

は変換^[5]の下では${\displaystyle T_{G}}$

${\displaystyle T_{G}(x,y)=(x-1)^{-k(E)}(y-1)^{-|V|}\cdot Z_{G}{\Big (}(x-1)(y-1),\;y-1{\Big )}.}$

タット多項式は連結成分に分解されます。が互いに素なグラフの和集合 である場合、${\displaystyle G}$${\displaystyle H}$${\displaystyle H'}$

${\displaystyle T_{G}=T_{H}\cdot T_{H'}}$

が平面グラフであり、その双対グラフを表す場合、 ${\displaystyle G}$${\displaystyle G^{*}}$

${\displaystyle T_{G}(x,y)=T_{G^{*}}(y,x)}$

特に、平面グラフの彩色多項式はその双対のフロー多項式である。タットはこのような関数をV関数と呼んでいる。^[6]

同型グラフは同じ Tutte 多項式を持ちますが、その逆は成り立ちません。たとえば、エッジ上のすべてのツリーの Tutte 多項式は です。 ${\displaystyle m}$${\displaystyle x^{m}}$

タット多項式は、行と列に係数を列挙した表形式で表されることが多い。たとえば、ピーターセングラフのタット多項式は、 ${\displaystyle t_{ij}}$${\displaystyle x^{i}y^{j}}$${\displaystyle i}$${\displaystyle j}$

${\displaystyle {\begin{aligned}36x&+120x^{2}+180x^{3}+170x^{4}+114x^{5}+56x^{6}+21x^{7}+6x^{8}+x^{9}\\&+36y+84y^{2}+75y^{3}+35y^{4}+9y^{5}+y^{6}\\&+168xy+240x^{2}y+170x^{3}y+70x^{4}y+12x^{5}y\\&+171xy^{2}+105x^{2}y^{2}+30x^{3}y^{2}\\&+65xy^{3}+15x^{2}y^{3}\\&+10xy^{4},\end{aligned}}}$

次の表に示します。

他の例として、八面体グラフのTutte多項式は次のように表される。

${\displaystyle {\begin{aligned}&12\,{y}^{2}{x}^{2}+11\,x+11\,y+40\,{y}^{3}+32\,{y}^{2}+46\,yx+24\,x{y}^{3}+52\,x{y}^{2}\\&+25\,{x}^{2}+29\,{y}^{4}+15\,{y}^{5}+5\,{y}^{6}+6\,{y}^{4}x\\&+39\,y{x}^{2}+20\,{x}^{3}+{y}^{7}+8\,y{x}^{3}+7\,{x}^{4}+{x}^{5}\end{aligned}}}$

WT タットの削除–短縮公式への関心は、ケンブリッジ大学トリニティ・カレッジの学部生時代に始まり、元々は完全な長方形と全域木に触発されたものでした。彼は研究でこの公式を頻繁に適用し、「同型性に対して不変で、同様の再帰公式を持つグラフの興味深い関数が他にもあるのではないかと考えました。」^[6] RM フォスターはすでに彩色多項式がそのような関数の 1 つであることに気付いており、タットはさらに多くのことを発見し始めました。削除–短縮再帰を満たすグラフ不変量を彼が最初に使用した用語はW 関数で、成分に対して乗法的な場合はV 関数でした。タットは、「W 関数を操作しているうちに、2 変数多項式が得られました。この多項式から、変数の 1 つを 0 に設定し、符号を調整することで、彩色多項式またはフロー多項式のいずれかを取得できました」と書いています。^[6] Tutte はこの関数を2 変数への彩色多項式の一般化とみなして二色関数と呼んだが、通常は Tutte 多項式と呼ばれる。Tutte の言葉を借りれば、「これは、類似の係数を知っていて、それを 2 つの変数に付ける手間をかけずに使用したHassler Whitneyに対して不公平かもしれない」。(「二色関数」と「二色多項式」という用語はTutte が別の論文で導入したが、わずかに異なるだけであり、「顕著な混乱」 ^{[7]がある。) Tutte 多項式のマトロイドへの一般化は}Crapoによって初めて発表されたが、Tutte の論文にはすでに登場している。^[8]

代数的グラフ理論の研究とは独立して、ポッツは1952年に統計力学における特定のモデルの分割関数の研究を始めた。ポッツモデルの一般化であるランダムクラスターモデルに関するフォーチュインとカステレイン^[9]の研究は、タット多項式^{[8]との関係を示す統一的な表現を提供した。}

平面上のさまざまな点や線において、Tutte 多項式は、数学や物理学のさまざまな分野で独自に研究されてきた量に評価されます。Tutte 多項式の魅力の一部は、これらの量を分析するための統一的なフレームワークを提供することにあります。 ${\displaystyle (x,y)}$

では、Tutte多項式は彩色多項式に特化します。^{[疑わしい–議論する]}${\displaystyle y=0}$

${\displaystyle \chi _{G}(\lambda )=(-1)^{|V|-k(G)}\lambda ^{k(G)}T_{G}(1-\lambda ,0),}$

ここで、Gの連結成分の数を表します。 ${\displaystyle k(G)}$

整数 λ の場合、彩色多項式の値は、λ 色のセットを使用したGの頂点彩色の数に等しくなります。が色のセットに依存しないことは明らかです。 あまり明確でないのは、それが整数係数を持つ多項式の λ での評価であるということです。 これを確認するには、次のことに留意してください。 ${\displaystyle \chi _{G}(\lambda )}$${\displaystyle \chi _{G}(\lambda )}$

1. Gにn 個の頂点があり、辺がない場合は、 .${\displaystyle \chi _{G}(\lambda )=\lambda ^{n}}$
2. G にループ (頂点をそれ自身に接続する単一の辺) が含まれている場合、 .${\displaystyle \chi _{G}(\lambda )=0}$
3. eがループではない辺である場合、

${\displaystyle \chi _{G}(\lambda )=\chi _{G-e}(\lambda )-\chi _{G/e}(\lambda ).}$

上記の 3 つの条件により、一連の辺削除と縮小を適用することで を計算することができますが、削除と縮小の異なるシーケンスで同じ値が得られるという保証はありません。この保証は、再帰とは無関係に が何かを数えるという事実から来ています。特に、 ${\displaystyle \chi _{G}(\lambda )}$${\displaystyle \chi _{G}(\lambda )}$

${\displaystyle T_{G}(2,0)=(-1)^{|V|}\chi _{G}(-1)}$

非巡回方向の数を与えます。

双曲線に沿って、平面グラフの Tutte 多項式は、関連する交代結び目のJones 多項式に特化します。^{[疑わしい–議論する]}${\displaystyle xy=1}$

${\displaystyle T_{G}(2,1)}$フォレストの数、つまり非巡回エッジサブセットの数を数えます。

${\displaystyle T_{G}(1,1)}$スパニングフォレスト（サイクルのないエッジサブセットで、 Gと同じ数の連結コンポーネント）の数をカウントします。グラフが連結されている場合は、スパニングツリーの数をカウントします。 ${\displaystyle T_{G}(1,1)}$

${\displaystyle T_{G}(1,2)}$スパニングサブグラフ（ Gと同じ数の連結成分を持つエッジサブセット）の数を数えます。

${\displaystyle T_{G}(2,0)}$Gの非巡回方向の数を数える。^[10]

${\displaystyle T_{G}(0,2)}$Gの強く連結した方向の数を数える。^[11]

${\displaystyle T_{G}(2,2)}$はグラフGの辺の数である数です。 ${\displaystyle 2^{|E|}}$${\displaystyle |E|}$

Gが4正則グラフであれば 、

${\displaystyle (-1)^{|V|+k(G)}T_{G}(0,-2)}$

Gのオイラー方向の数を数える。ここではGの連結成分の数である。^[10]${\displaystyle k(G)}$

Gがm  ×  nの グリッドグラフである場合、幅4m、高さ4nの長方形をTテトロミノで敷き詰める方法の数を数えます。^{[12] [13]}${\displaystyle 2T_{G}(3,3)}$

G が平面グラフである場合、はGの中間グラフの重み付きオイラー方向の合計に等しくなります。ここで、方向の重みは、方向の鞍点の数（つまり、接続辺が「イン、アウト、イン、アウト」の順に循環的に順序付けられている頂点の数）の2倍です。^[14]${\displaystyle 2T_{G}(3,3)}$

xy平面上の双曲線を定義します。

${\displaystyle H_{2}:\quad (x-1)(y-1)=2,}$

タット多項式は統計物理学で研究されているイジングモデルの分配関数に特化している。^{[疑わしい–議論する]}具体的には、双曲線に沿って、2つは次の式で関連している：^[15]${\displaystyle Z(\cdot ),}$${\displaystyle H_{2}}$

${\displaystyle Z(G)=2\left(e^{-\alpha }\right)^{|E|-r(E)}\left(4\sinh \alpha \right)^{r(E)}T_{G}\left(\coth \alpha ,e^{2\alpha }\right).}$

特に、

${\displaystyle (\coth \alpha -1)\left(e^{2\alpha }-1\right)=2}$

すべての複素αに対して。

より一般的には、任意の正の整数qに対して双曲線を定義します。

${\displaystyle H_{q}:\quad (x-1)(y-1)=q,}$

すると、Tutte 多項式はq状態Potts モデルの分割関数に特化します。^{[疑わしい–議論する]} Potts モデルの枠組みで分析されるさまざまな物理量は、の特定の部分に変換されます。 ${\displaystyle H_{q}}$

では、Tutte 多項式は組合せ論で研究されるフロー多項式に特化します。^{[疑わしい–議論する]}連結かつ無向グラフGと整数kについて、どこにもゼロがないkフローは、各頂点に出入りするフローの合計がk を法として合同になるように、Gの任意の向きのエッジに「フロー」値を割り当てることです。フロー多項式は、どこにもゼロがないkフローの数を表します。この値は彩色多項式と密接に関連しています。実際、G が平面グラフである場合、 Gの彩色多項式は、次の意味で その双対グラフのフロー多項式と同等です。${\displaystyle x=0}$${\displaystyle 1,2,\dots ,k-1}$${\displaystyle C_{G}(k)}$ ${\displaystyle G^{*}}$

定理（トゥッテ）。

${\displaystyle C_{G}(k)=k^{-1}\chi _{G^{*}}(k).}$

Tutte多項式への接続は次のように与えられます。

${\displaystyle C_{G}(k)=(-1)^{|E|-|V|+k(G)}T_{G}(0,1-k).}$

では、Tutte 多項式はネットワーク理論で研究されている全端子信頼性多項式に特化しています。^{[疑わしい–議論する]}連結グラフGでは、すべての辺を確率pで削除します。これは、ランダムな辺障害が発生するネットワークをモデル化します。信頼性多項式は関数、つまりpの多項式で、辺障害が発生した後もGのすべての頂点ペアが接続されたままである確率を与えます。Tutte 多項式との関連は次のように表されます。 ${\displaystyle x=1}$${\displaystyle R_{G}(p)}$

${\displaystyle R_{G}(p)=(1-p)^{|V|-k(G)}p^{|E|-|V|+k(G)}T_{G}\left(1,{\tfrac {1}{p}}\right).}$

タットはまた、グラフの 二色多項式である、彩色多項式のより近い2変数一般化も定義した。これは

${\displaystyle Q_{G}(u,v)=\sum \nolimits _{A\subseteq E}u^{k(A)}v^{|A|-|V|+k(A)},}$

ここで、は全域グラフ（V、A ）の連結成分の数である。これは、コランクヌル多項式と次の式で 関係している。${\displaystyle k(A)}$

${\displaystyle Q_{G}(u,v)=u^{k(G)}\,R_{G}(u,v).}$

二色多項式はマトロイドに一般化できません。なぜなら、k ( A )はマトロイドの特性ではないからです。同じマトロイドを持つ異なるグラフは、接続されたコンポーネントの数が異なる場合があります。

有向4正則グラフのマーティン多項式は1977年にピエール・マーティンによって定義された。^[17]彼は、Gが平面グラフでその有向中位グラフである場合、 ${\displaystyle m_{\vec {G}}(x)}$${\displaystyle {\vec {G}}}$${\displaystyle {\vec {G}}_{m}}$

${\displaystyle T_{G}(x,x)=m_{{\vec {G}}_{m}}(x).}$

タット多項式の削除-縮小再帰、

${\displaystyle T_{G}(x,y)=T_{G\setminus e}(x,y)+T_{G/e}(x,y),\qquad e{\text{ not a loop nor a bridge.}}}$

は、与えられたグラフに対してこれを計算するための再帰アルゴリズムを直ちに生成します。ループでもブリッジでもないエッジe が見つかる限り、そのエッジが削除されたとき、およびそのエッジが縮小されたときの Tutte 多項式を再帰的に計算します。次に、2 つのサブ結果を加算して、グラフの全体的な Tutte 多項式を取得します。

基本ケースは単項式であり、mはブリッジの数、n はループの数です。 ${\displaystyle x^{m}y^{n}}$

多項式係数の範囲内で、このアルゴリズムの実行時間tはグラフの 頂点数nと辺数mで表すことができる。

${\displaystyle t(n+m)=t(n+m-1)+t(n+m-2),}$

フィボナッチ数列に比例する再帰関係の解^[18]

${\displaystyle t(n+m)=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n+m}=O\left(1.6180^{n+m}\right).}$

この解析は、入力グラフの全域木の数の多項式係数以内で改善することができる。 ^[19]この実行時間を持つスパースグラフの場合、 k次の正規グラフの場合、全域木の数は次のように制限される。 ${\displaystyle \tau (G)}$${\displaystyle m=O(n)}$${\displaystyle \exp(O(n))}$

${\displaystyle \tau (G)=O\left(\nu _{k}^{n}n^{-1}\log n\right),}$

どこ

${\displaystyle \nu _{k}={\frac {(k-1)^{k-1}}{(k^{2}-2k)^{{\frac {k}{2}}-1}}}.}$

したがって、削除縮約アルゴリズムはこの境界の多項式因子内で実行される。例えば：^[20]

${\displaystyle \nu _{5}\approx 4.4066.}$

実際には、グラフ同型性テストは再帰呼び出しを回避するために使用されます。このアプローチは、非常に疎で多くの対称性を示すグラフに適しています。アルゴリズムのパフォーマンスは、エッジeを選択するために使用されるヒューリスティックに依存します。^{[19] [21] [22]}

いくつかの限定された例では、タット多項式は多項式時間で計算できます。これは、ガウス消去法が行列演算の行列式とパフィアンを効率的に計算するためです。これらのアルゴリズム自体は、代数グラフ理論と統計力学からの重要な結果です。

${\displaystyle T_{G}(1,1)}$は連結グラフの全域木の数に等しい。これは、 Gのラプラシアン行列の最大主部分行列の行列式として多項式時間で計算可能であり、代数グラフ理論の初期の結果であるキルヒホッフの行列木定理として知られている。同様に、における自転車空間の次元は、ガウスの消去法によって多項式時間で計算できる。 ${\displaystyle \tau (G)}$${\displaystyle T_{G}(-1,-1)}$

平面グラフの場合、イジングモデルの分割関数、つまり双曲線におけるタット多項式は、パフィアンとして表現でき、FKTアルゴリズムを介して効率的に計算できます。このアイデアは、平面格子モデルの二量体被覆の数を計算するために、Fisher、Kasteleyn、およびTemperleyによって開発されました。 ${\displaystyle H_{2}}$

マルコフ連鎖モンテカルロ法を使用すると、Tutte 多項式は、 の正の枝、つまり強磁性 Ising モデルの分割関数に沿って任意に近似できます。これは、Ising モデルとグラフ内のマッチングを数える問題との密接な関係を利用しています。Jerrum と Sinclair ^[23]によるこの有名な結果の背後にあるアイデアは、入力グラフのマッチングを状態とするマルコフ連鎖を設定することです。遷移は、エッジをランダムに選択し、それに応じてマッチングを変更することによって定義されます。結果として得られるマルコフ連鎖は急速に混合され、「十分にランダムな」マッチングにつながります。これは、ランダム サンプリングを使用して分割関数を回復するために使用できます。結果として得られるアルゴリズムは、完全な多項式時間ランダム化近似スキーム(fpras) です。 ${\displaystyle H_{2}}$

タット多項式にはいくつかの計算上の問題が伴う。最も単純なものは

入力: グラフ${\displaystyle G}$

出力: 係数${\displaystyle T_{G}}$

特に、出力により、Gの 3 色塗りの数を数えることと同等の評価が可能になります。この後者の問題は、平面グラフの族に制限された場合でも#P 完全であるため、与えられたグラフの Tutte 多項式の係数を計算する問題は、平面グラフであっても #P 困難です。 ${\displaystyle T_{G}(-2,0)}$

すべての複素対に対して定義されるTutte と呼ばれる一連の問題に、より多くの注目が集まっています。 ${\displaystyle (x,y)}$${\displaystyle (x,y)}$

入力: グラフ${\displaystyle G}$

出力:${\displaystyle T_{G}(x,y)}$

これらの問題の難しさは座標によって異なります。 ${\displaystyle (x,y)}$

xとyが両方とも非負の整数である場合、問題は#Pに属します。一般的な整数ペアの場合、Tutte 多項式には負の項が含まれるため、問題はGapP という複雑性クラス、つまり減算における#Pの閉包に分類されます。有理座標に対応するために、 #Pの有理座標類似体を定義することができます。^[24]${\displaystyle T_{G}(x,y)}$${\displaystyle (x,y)}$

任意の について を正確に計算する計算量は、2つのクラスのいずれかに分類されます。が双曲線上にあるか、 の点の1つでない 限り、この問題は#P困難です。${\displaystyle T_{G}(x,y)}$${\displaystyle x,y\in \mathbb {C} }$${\displaystyle (x,y)}$${\displaystyle H_{1}}$

${\displaystyle \left\{(1,1),(-1,-1),(0,-1),(-1,0),(i,-i),(-i,i),\left(j,j^{2}\right),\left(j^{2},j\right)\right\},\qquad j=e^{\frac {2\pi i}{3}}.}$

この場合、多項式時間で計算可能である。^[25]問題が平面グラフのクラスに制限されると、双曲線上の点も多項式時間で計算可能になる。他のすべての点は、二部平面グラフであっても #P 困難のままである。^[26]平面グラフの二分法に関する論文で、Vertigan は（結論で）頂点次数が最大 3 のグラフにさらに制限した場合、点を除いて同じ結果が成り立つと主張している。点 は、どこでもゼロではないZ ₃フローを数え、多項式時間で計算可能である。^[27]${\displaystyle H_{2}}$${\displaystyle T_{G}(0,-2)}$

これらの結果には、注目すべき特殊なケースがいくつか含まれています。たとえば、イジングモデルの分割関数を計算する問題は、オンサガーとフィッシャーの有名なアルゴリズムが平面格子に対してそれを解決しているにもかかわらず、一般に #P 困難です。また、ジョーンズ多項式の計算は #P 困難です。最後に、平面グラフの 4 色彩数の計算は、決定問題が4 色定理によって自明であるにもかかわらず、#P 完全です。対照的に、平面グラフの 3 色彩数の計算は #P 完全であることが簡単にわかります。これは、決定問題が簡約化によって NP 完全であることがわかっているためです。

どの点に良い近似アルゴリズムがあるのか​​という問題は、非常によく研究されてきた。多項式時間で正確に計算できる点を除けば、 について知られている唯一の近似アルゴリズムは、 JerrumとSinclairのFPRASであり、これはy > 0の「イジング」双曲線上の点に有効である。入力グラフが次数の密なインスタンスに制限されている場合、x ≥ 1、y ≥ 1の場合にはFPRASが存在する。 ^[28]${\displaystyle T_{G}(x,y)}$${\displaystyle H_{2}}$${\displaystyle \Omega (n)}$

正確な計算ほど状況はよく理解されていないものの、平面の広い領域を近似することは困難であることが知られています。^[24]

• ボロバス-リオルダン多項式
• トゥット・グロタンディーク不変量とは、トゥット多項式の評価である。

• 「Tutte 多項式」、数学百科事典、EMS プレス、2001 [1994]
• ワイスタイン、エリック W.「トゥッテ多項式」。マスワールド。
• PlanetMath彩色多項式
• スティーブン・R・パガーノ: マトロイドと符号付きグラフ
• サンドラ・キンガン: マトロイド理論。多くのリンク。
• Gary Haggard、David J. Pearce、Gordon RoyleによるTutte多項式、Chromatic多項式、Flow多項式を計算するコード: [1]