タッテ多項式

Tutte多項式は連結成分に因数分解されます。${\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)}$

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

同型グラフは同じタット多項式を持つが、その逆は成り立たない。例えば、すべての木のタット多項式は${\displaystyle m}$エッジは${\displaystyle x^{m}}$。

タット多項式は、係数を一覧表形式で示すことが多い。$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}\\&+1 68xy+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}}}$

以下の表で示されます。

別の例として、正八面体グラフのタット多項式は次のように表される。

${\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}}}$

で${\displaystyle y=0}$タッテ多項式は彩色多項式に特化され、

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

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

整数λの場合、彩色多項式の値は${\displaystyle \chi _{G}(\lambda )}$λ は、λ 色の集合を使用してGの頂点を彩色する数に等しい。${\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 ).}$

上記の３つの条件により、計算が可能になります。${\displaystyle \chi _{G}(\lambda )}$一連のエッジ削除と縮約を適用することによって実現されますが、異なる削除と縮約のシーケンスが同じ値になるという保証はありません。保証は、${\displaystyle \chi _{G}(\lambda )}$繰り返しとは無関係に何かを数える。特に、

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

非巡回的な向きの数を示します。

双曲線に沿って${\displaystyle xy=1}$平面グラフのタット多項式は、関連する交代結び目のジョーンズ多項式に特化する。

xy平面における双曲線を定義する。

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

Tutte多項式は分割関数に特化しており、${\displaystyle Z(\cdot ),}$統計物理学で研究されているイジングモデルについて。具体的には、双曲線に沿って${\displaystyle H_{2}}$この2つは次の式で関連付けられています: ^{[ 15 ]}

${\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}}$。

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

定理（トゥッテ）。

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

トゥッテ多項式との関連性は次のように表される。

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

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

${\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)},}$

どこ${\displaystyle k(A)}$は、全域部分グラフ ( V , A ) の連結成分の数です。これは、次の式でコランク零多項式と関連付けられます。

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

二色多項式はマトロイドには一般化されません。なぜなら、k ( A )はマトロイドの性質ではないからです。同じマトロイドを持つ異なるグラフでも、連結成分の数は異なる場合があります。

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

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

Tutte多項式の削除縮約漸化式、

${\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 多項式を取得します。

基本ケースは単項式です${\displaystyle x^{m}y^{n}}$ここで、 mは橋の数、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).}$

解析は、その数の多項式係数の範囲内で改善できる。${\displaystyle \tau (G)}$入力グラフの全域木。 ^{[ 19 ]}疎グラフの場合${\displaystyle m=O(n)}$この実行時間は${\displaystyle \exp(O(n))}$次数kの正則グラフの場合、全域木の数は次のように制限できます。

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

平面グラフの場合、イジングモデルの分配関数、すなわち双曲線上のタット多項式は${\displaystyle H_{2}}$はパフィアンとして表現でき、FKTアルゴリズムによって効率的に計算できます。このアイデアは、平面格子モデルのダイマーカバーの数を計算するために、Fisher、Kasteleyn、およびTemperleyによって開発されました。

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

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

正確に計算する計算複雑度${\displaystyle T_{G}(x,y)}$どのような場合でも、2 つのクラスのいずれかに分類されます。${\displaystyle x,y\in \mathbb {C} }$問題は、以下の条件を満たさない限り#P困難です。${\displaystyle (x,y)}$双曲線上に位置する${\displaystyle H_{1}}$またはポイントの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 ]}問題が平面グラフのクラスに限定されている場合、双曲線上の点は${\displaystyle H_{2}}$も多項式時間で計算可能になる。他のすべての点は、二部平面グラフの場合でも#P-困難のままである。^{[ 26 ]}平面グラフの二分法に関する論文で、Vertiganは（結論で）頂点次数が最大3のグラフにさらに制限した場合でも、点を除いて同じ結果が成り立つと主張している。${\displaystyle T_{G}(0,-2)}$これは、どこにもゼロがないZ ₃フローをカウントし、多項式時間で計算可能です。^{[ 27 ]}

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

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

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