Tutte 多項式入門

-概要-

最近 Tutte 多項式が面白いと思ったのでこれについて書きます. 今回はTutte 多項式の定義とその気持ちについて簡単に述べた後, Tutte 多項式についての予想の一つである Merino-Welsh 予想[1]について書きます.

1. 連結グラフの全域木の個数

連結グラフ G=(V, E) があるときにGが含む全域木の個数を t(G) と表すことにします. Gの辺 e={x, y} (eは自己ループでないとする)に対して G から e を削除して得られるグラフを G-e と書き, G から e を 縮約して得られるグラフを G/e と書きます.

図1 : G/e において xy は一つの頂点で, xy と b の間には二重辺が存在します.

辺e に対して Gの全域木は

1. e を含むもの
2. e を含まないもの

に分類できます. 図2から分かるように, 1の全域木の個数は t(G/e) と等しく, 2の全域木は t(G-e) と等しいはずです.

図2. 全域木の対応関係

　従って

t(G) = t(G-e) + t(G/e)

が成り立ちます. eが自己ループの場合は削除しても全域木の個数は変わらないので

t(G) = t(G-e).

eが橋の場合は t(G-e)=0 となるので

t(G) = t(G/e).

どのようなGに対してもこの漸化式を繰り返し適用していくと G は辺を含まず頂点が一つしかないようなグラフになりますが, このように G が singleton の場合は

t(G) = 1.

2. 彩色の総数

　グラフの彩色とは, 頂点に色を塗ることです. ただし辺でつながった二つの頂点は同じ色で塗ってはいけません.  ここではGを q 色で塗るときに何通りの塗り方があるか？ について考えます. この値を P(q;G) と表すことにします. Gのq色による彩色をq-彩色と呼ぶことにします. 先ほどと同様に P(q;G), P(q:G-e), P(q:G/e) の関係について調べて見ます.

　G の辺 e={x, y} (eは自己ループでないとする) に対して, G-e の任意のq-彩色は

1. x と y が同じ色になっている彩色
2. x と y が異なる色になっている彩色

に分類できます.

図3. 彩色の対応

　図3 より, 1の彩色は G の彩色に対応していて, 2の彩色は G/e の彩色に対応していることが分かるので, 

P(q;G-e) = P(q;G)+P(q;G/e)

すなわち

P(q;G) = P(q;G-e) - P(q;G/e)

が成り立つことが分かります. eが自己ループの場合は削除してもPに影響がないので,

P(q;G) = P(q;G-e).

Gに辺がない場合は n を G の頂点数として, P(q;G) = q^n となります. このPは e の選ぶ順番によらずqに関するある多項式となっていて, 彩色多項式と呼ばれています.

3. Tutte 多項式

　ここまではグラフの縮約と削除にまつわる様々な量があることを見てきました. これらを一般化した概念が Tutte 多項式 です. Tutte 多項式はグラフGに対して定義される二変数多項式になっていて, T(x,y; G) と表します.

   定義 (Tutte Polynomial)   

Gが辺を持つグラフならば, e を Gの辺 とします.

• T(x,y; G) := 1                                     (Gが辺を含まない)
• T(x,y; G) := xT(x,y; G-e)                      (Gが自己ループ)
• T(x,y; G) := yT(x,y; G/e)                      (Gが橋)
• T(x,y; G) := T(x,y; G-e) + T(x,y; G/e)     (その他)

　この定義を見ると確かにこれまで見てきた概念を一般化したかのような気がしてきます. このT も e を選ぶ順番によって異なる多項式が出てくるような気もしますが実はそのようなことはなく, well-defined です. 実際にx=y=1 とすると, T(1,1; G) = t(G) となります. また, 

P(q;G) = (-1)^{n-k(G)} q^{k(G)} T(1-q,0; G)

となります. (ここでk(G)はGの連結成分の個数)

　様々な値がTutte 多項式で表されるため, 組合せ論のみならず様々な応用があります.

4. Merino-Welsh 予想

グラフ理論における(多分有名ではない)予想の一つである Merino-Welsh 予想 について導入します. 結論から言うと, Merino-Welsh 予想[1]とは以下の予想です.

   予想 (Merino and Welsh, 1999)   

橋と自己ループを含まないようなグラフG に対して

max{ T(2,0; G) , T(0,2; G) } >= T(1,1; G)

　Tutte 多項式の値の評価は一般には難しいです. (x, y) = (1, 1) の場合は全域木の個数になるので, 行列木定理によって n×n 程度の大きさの行列の行列式を計算するだけで求められるので難しくはないのですが, 後で言うように T(2,0; G) や T(0,2; G) はグラフの totally cyclic orientation や acyclic orientation の個数に対応していて, これらを数え上げることは#P-困難であるため, 具体的な値を求めることは難しいと信じられています.

5. Totally cyclic orientation

　まず orientation とは何かということについて述べます. orientation とは簡単に言うと辺の"向き"のことです. つまり, 無向グラフの各辺について, 左右どちらかの向きを付けると有向グラフが生成されますが, このときの各辺の"向き" のことを orientation と呼びます. (orient という言葉にはもともと「方向付ける」という意味があり, 数学の他の分野でも例えば球とかトーラスの面は orientable ですが, メビウスの輪のような図形やクラインの壷などは nonorientable と言ったりするようです. 詳しくはないですが)

　totally cyclic orientation とは グラフの orientation の中で, どの辺も何かしらの有向閉路に含まれているような orientation のことを言います.

図4. totally cyclic orientation の例. 

　図4右のorientation では辺5→6は 5→6→4→2→3→5 という有向閉路に含まれていて, 他の辺の何かしらの有向閉路に含まれていることが確認できるため, totally cyclic orientation となっています. 

　特にグラフG が橋 e を持つ場合, e にどのような向きを付けても e を含む閉路が存在しないので totally cyclic orientation は存在しないことがすぐ分かります.

　また totally cyclic orientation の個数は 縮約と削除に関して, Tutte多項式と同じような漸化式を満たすことが簡単に分かり, 実は T(2,0; G) と等しいことがいえます.

　実は元のグラフGが dense (辺が多い) なときは, totally cyclic orientation の個数は大きくなります. (Gに閉路が多く存在するので辺eに適当な向きをつけても有向閉路に含まれるチャンスが大きくなるから). 具体的には以下の定理が知られています[2].

  定理 (Thomassen, 2010)  

G=(V, E) を, |E| >= 4|V|-4 を満たすグラフとする (自己ループと橋は持たないとする). このとき,

T(1,1; G) < T(2,0; G)

6. Acyclic orientation

　最後に acyclic orientation について紹介します. acyclic とは "非閉路的" という意味で, acyclic orientation とは 「有向閉路を一つも含まないようなorientation」　のことです. 言い換えると 向きを付けたグラフがDAGとなるような orientation のことです. 例えば図4の左の図を見ると, 有向閉路を一つも含まないことが分かります. ゆえにこれは acyclic orientation となっています.

　特にグラフG が自己ループ e を持つ場合, e にどのような向きを付けても自分自身で有向閉路になってしまうため, Gに acyclic orientation は存在しないということが出来ます.

　また, acyclic orientation の個数も同様に Tutte 多項式と同じような漸化式を満たすことが分かり, 実は T(0,2; G) と等しいことがいえます.

　結果だけ紹介しますが, グラフがスパースの場合は acyclic orientation の値は一般的には大きくなり, 以下の定理が知られています[2].

  定理 (Thomassen, 2010)  

G=(V, E) を, |E| < 16|V|/15 を満たすグラフとする (自己ループと橋は持たないとする). このとき,

T(1,1; G) < T(0,2; G)

7. 分かっていること

　先ほど紹介した定理より, グラフが dense または sparse な場合については証明されていることが分かります. では平面グラフなどのように, 中くらいの辺密度を持つようなグラフについては何が言えているのでしょうか？

　結論から先に言うと, いまだに分かっていないことが多いです. 予想が証明されているのは(僕が調べた限りでは)

• 直並列グラフ [3]
• sparse な場合と dense な場合 [2]

です. 一方で特殊なグラフGに対して T(2,0; G) や T(0,2; G) の上界や下界を求めるという成果は色々あるようです. 

8. おわりに

　グラフの辺の縮約・削除についての面白い漸化式とその一般化であるTutte多項式 を見てきました. Tutte多項式の値の厳密な評価は一般には難しいと考えられていて, 様々な漸近的性質などは分かっています. しかしMerino-Welsh 予想に見られるような不等式は今だによく分かっていないのが現状です.

　実はもうちょっと一般化してマトロイドに対して Tutte 多項式 を定義することができます. これまで様々な研究があり, これに対しても Merino-Welsh 予想が考えられると思います.

　皆さんもぜひ、この予想に挑戦してみてはいかがでしょうか？？

9. 参考文献

[1] C. Merino, D.J.A. Welsh, Forests, colorings and acyclic orientations of the square lattice, Ann. Comb. 3 (2–4) (1999) 417–429.

[2] C. Thomassen. Spanning trees and orientations in graphs. Journal

of Combinatorics, 1(2):101–111, 2010.

[3] S. D. Noble and G. F. Royle. The Merino-Welsh conjecture holds for series-parallel graphs. European Journal of Combinatorics, 38:24–35, 2014.

Localization and centrality in networks

読んだ論文の内容について書いています。

論文のタイトルは Localization and centrality in networks で

http://journals.aps.org/pre/abstract/10.1103/PhysRevE.90.052808

にあります。

Physical Reviewという物理学の中で最も権威ある学術雑誌の2014年の論文です。

内容をかいつまんで要約すると

　グラフの各頂点の重要度(centrality)として、そのグラフの隣接行列の第一固有値に対応する固有ベクトルを用いる手法がある。しかしこの指標には局所性(localization transition)という問題点があり、例えばハブとなるような頂点があるとその頂点の重要度が集中しすぎてしまい、他の頂点をまともに評価できないという問題点がある。現実にあるいわゆるソーシャルネットワークのような、次数がべき乗則に従うようなネットワークにもこの問題が発生してしまうため、隣接行列の固有ベクトルを用いた評価は適当ではない。

　この問題点を解決するために、グラフの nonbacktracking matrix の第一固有ベクトルを用いた手法を提案し、これが上手くいくことについて考察した。

というものです。

固有値による重要度の評価

　グラフの各頂点の重要度(centrality)をどのようにして決めるかという問題は例えばページランクとかそういうものに応用が利くので考えたくなる題材です。頂点数を n とし、頂点 i  の重要度を



とおき、特に頂点の重要度を成分として持つn次元ベクトルを単に  と表記することにします。

　最も簡単な評価はその頂点の次数を重要度として採用するというものです。これは「沢山の友達とつながっている人の方が影響力が大きい」という観察に基づいたものです。

　この評価では「どの友達も同じくらいの影響力を持っている」という仮定があります。しかし実際は「友達の中に偉い人がいるような人の方が影響力が高い」と見なせるというのが自然だと思います。「東大生と友達だよ」よりも「オバマと友達だよ」って言われた方がインパクトがあるってものです。 この観察を考慮すると、重要度の定義を



とするのが適当と思われます。ここで A は隣接行列、λは適当な定数を意味します。 つまり友人の重要度の和をスカラー倍を自分の重要度とするわけです。この式をベクトルの形で書くと




となりまさに v は固有ベクトルとなるわけです。ペロン・フロベニウスの定理より、隣接行列Aは全ての成分が非負なので第一固有値は非負となり、対応する固有ベクトルで全要素が非負であるものが存在するためこの固有ベクトルをもって v とする、ということです。

問題点

　隣接行列の固有ベクトルを用いた評価は、次数が極端に大きい頂点が少しだけあるようなグラフに対しては、次数が大きい頂点ら(局所的な部分)に重要度が集中してしまいます。その結果、その他の頂点の評価がおざなりになってしまい、比較しにくくなってしまうという欠点があります。

　この現象を感覚的に説明します。

　この図では次数5の頂点が一つだけ存在します。この頂点の重要度は大きくなります。周りにある頂点は真ん中の頂点の重要度を足されるので、重要度が大きくなります。また、真ん中の頂点は近傍の重要度を足すので重要度はかなり大きくなることが予想されます。つまり真ん中の頂点は自分の重要度が近傍に影響した後、その影響が反射してまた自分の重要度が大きくなるわけです。これを繰り返した結果、真ん中の頂点の重要度は他の頂点に比べて極端に大きくなることになります。

　論文ではランダムグラフにハブを追加したようなモデルと次数がべき乗則に従うようなランダムグラフを考え、そのグラフの隣接行列の第一固有値と第二固有値に対応する固有ベクトルを解析し、隣接行列の固有ベクトルによる手法が上手くいかないことを説明しています。

　この問題は、重要度が行って戻ってくる(backtrack)することに起因します。従ってそうならない(nonbacktrack)ような関係式を考察すればよいのでは？ということになります。

nonbacktracking matrix

 グラフから抽出される行列は隣接行列やグラフラプラシアンのほかにも色々あり、その中の一つに nonbacktracking matrix というものがあります。無向グラフG=(V, E)に対してEの各辺を、行きと帰りの二つの向きをつけます。 このように向きつけられた辺はGに対しては全部で 2|E| 本ありますが、この 2|E| 本の向き付き辺が nonbacktracking matrix のインデックスになっています。 従って, Gのnonbacktracking matrix は 2|E| × 2|E| の行列となります。 式で書くと



となります。この行列の最大固有値に対応する固有ベクトルを計算し、各頂点に対してそれに入ってくる(incoming)な辺に対応する固有ベクトルの成分の和を重要度とする、というのが提案手法です。

　この固有値と固有ベクトルの計算は一見すると大変そうに見えるのですが、



という行列の第一固有値に対応する固有ベクトルを計算し、先頭のn個の成分をとってくれば、所望の重要度になっていることが知られています。この行列の疎性は元の行列の疎性と対して代わらないためにそれほど計算時間は問題にならないということが分かります。