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個の成分をとってくれば、所望の重要度になっていることが知られています。この行列の疎性は元の行列の疎性と対して代わらないためにそれほど計算時間は問題にならないということが分かります。

全点間最短経路の計算をちょっとの工夫でちょっと速くする話

概要

最近研究で重みなし連結正則グラフの全点間の最短経路を求めることが多く、ちょっと工夫したらちょっとだけ早くなったのでそれについて簡単に書きます。

素朴な方法

一番素朴な方法としては幅優先探索があります。
全ての頂点から幅優先探索をして全点間の最短経路を全て計算する方法です。

アルゴリズム

ところである点から幅優先探索を行うと図のように三角形みたいな図が出てくると思います。



　　　　　　　　　　　　　　

　幅優先探索をやっているとキューに頂点を取り出しては突っ込んでを繰り返して最短距離を計算していくわけですが、よく考えるとこの図の最下層にいる頂点たちはキューから取り出されてもその後何もせずに放り投げられてしまうことになります。したがって、キューに突っ込んだ頂点の個数がグラフの頂点数とちょうど等しくなったらキューを空にして幅優先を終了し、別の頂点からまた幅優先する」というアルゴリズムでちょっとだけ計算が速くなることが期待されます。
　考え方としては簡単でセコイように見えますが、グラフの形状によっては紫の部分の頂点がすごく多かったりすることがあるので、密なグラフに対してはそこそこ高速になるんじゃないかと期待できることと思われます。

数値実験

ということで幾つかの種類のグラフに対し「全点間最短経路長」を計算する以下に示す２つのプログラムを用意し、比較しました。
A. 素朴な幅優先探索
B. 上に述べた工夫をしたもの

用意したグラフは次のモデルによって生成されたグラフです。
1. Erdős–Rényi model (最も代表的なランダムグラフのモデル)
2. Configuration Model (ランダム正則グラフの代表的なモデル)

　　　　　　　　　　　

Erdős–Rényi modelによって生成されたグラフに対するプログラムの実行時間の比較です。
横軸はモデルのパラメータpの値で、右に行くほど辺の本数が多くなっています。頂点数は10000で固定しています。 縦軸は実行時間で、単位は[ms]です。紫の線が素朴な方法(A)で、緑の線が工夫したもの(B)です。


Configuration Modelによって生成されたグラフでの比較です。横軸は頂点の次数を表しているため、右に行くほど線形で辺の本数が増えていきます。縦軸は先ほどと同様に実行時間で単位は[ms]です。頂点数は10000です。なお、１番目の実験で生成したグラフよりも辺数は圧倒的に少ないためこちらの方が実行時間はかなり短くなっています。紫が素朴な方法で、緑が工夫した方法です。


二つの結果を見ると、意外とこの工夫によって早くなることが分かると思います。

考察・まとめ

・ 空間計算量を変えずにちょっとした工夫でBFSを早くするという話でした。

・ 恐らく緑の方では実行時間はグラフの直径によって大きく左右されるのでほぼ横ばいみたいな感じになっていると思います。
・ 直径をDだとすると、#{ 最短距離がDとなるような頂点ペア } が多いほど工夫が効果的になると思います。
・ したがって例えばグラフが木だったりするとぜんぜん効果がないと思います。

・ 実データとかでは実験してないのでその辺を含めてもうちょっと調べてみたいと思います。
・ さすがにこれくらいの工夫は誰か思いついてるでしょ...

摩訶不思議系魔法ランキング

それでも色々数学について勉強していると何かと「ホンマかそれ」と思うような, まさに「魔法」のような定理やアルゴリズムに出会い数学って面白く奥深いなぁと感じることがあると思います. そこで僕が今まで出会ってきた「魔法」の中で非常に印象の深かったものの中で深夜にパッと思いついた分だけ列挙していきます. タイトルにランキングとありますがランキングではありません. 列挙です. 多分グラフ理論についてが多いです.

理論部門

・貪欲法が上手くいく ⇔ マトロイド

　「行列のようなもの」という意味をもつマトロイドは, 有限集合Eとある三つの公理を満たすEの部分集合族Fによって(E, F)の形として定義されます. 三つの公理とは

(M1): 空集合 ∈ F
(M2): AがBの部分集合, かつB∈F ならば, A∈F
(M3): Fの要素A, Bが|A| < |B|ならば, e∈ B-A が存在し, A∪{e} ∈ F とできる.

ここでFの各要素はEの部分集合になっていて, Fの各要素のことを独立集合と言ったりします. また, 独立集合のうち集合の包含関係に関して極大であるようなものを基と呼びます.
　たとえば行列Aを持ってきたときにAを列ベクトルが集まったものとみなし, この列ベクトルの集合をEとし, 「線形独立である列ベクトルの集合」を独立集合とみなしたとき(E, F)はマトロイドになっています. 他にも, グラフGを持ってきたときにその辺集合をEとし, 「閉路をなさないようなEの部分集合」を独立集合とみなしたときのM=(E, F)もマトロイドとなっています. このときGの全域森(Gが連結なら全域木)はマトロイドMの基となっています.
　集合Eとその部分集合Fが(M1)と(M2)を満たしており, さらにEの重み関数 w: E→R があるとします. ここで(E, F)にはFの極大な要素が存在するのでこれを基と定義します. またEの任意の部分集合Xに対して, w(X) = Σw(e) (e∈X) と定義します. このとき次の最小化問題を考えます.

min: w(X)
s.t. Xは(E,F)の基である.

この問題に対して,
「Eの要素をw(e)の値でソートし順番に付け加えて基になるようにする」という貪欲法が最適解を得るための必要十分条件が
(E, F)がマトロイドである.
というのです.
たとえばこのグラフの最小全域木問題に対するクラスカル法がこれに該当します. 他にもマッチングとかもマトロイドと絡んできて面白いのですが, 個人的には(E, F)に対する組合せ最適化問題で貪欲法がうまくいくための必要十分条件がマトロイドである, という事実が結構驚きでした. 実はこの事実はWhitneyにより「マトロイド」という単語が初めて出てくるよりもちょっと前に証明されていたようです.

・バーゼル問題

その昔, オイラーによって解かれた非常に有名な数学の問題です. 調和級数は発散しますが, 平方数の逆数を足していくとπが出てくるというのは当時高校生だった僕にとってはかなり衝撃的だった記憶があります. 一回証明をパラっと読んだくらいで全然詳しくないですが, 僕が数学にのめりこんだきっかけの一つです.

・ランダム正則グラフにおける三角形の個数

ランダムグラフ理論というのはある性質を満たすグラフが存在するときに使われたのが最初でした. 具体的には「Erdős–Rényi の定理」が最も有名です.

<Erdős–Rényiの定理>
　任意の整数k>0 に対して, girth(最小の閉路の長さ)と染色数がkより大きいグラフが存在する.

　この定理で使われたランダムグラフG(n,p)というのは, まず頂点をn個持ってきて「各頂点ペアに対して独立に確率pで辺をひくかどうか決める」ことによって生成されます. これによって生成されたランダムグラフはnとpをパラメータにもちますが, ランダムグラフの界隈ではnを無限に飛ばしたときの挙動について調べることが多いようです.
　しかし, たとえばランダムな正則グラフ(各頂点の次数が等しいグラフ)を作りたいみたいなことがあるかもしれません. また, ほとんど全ての正則グラフが満たすようななにか面白い性質はないだろうか, という理論的興味があります.
　Reg(n, d)で頂点数n, 次数dの正則グラフの全体を表すこととします. このときReg(n, d)の要素を一様ランダムに一つグラフをとってきたときに, そのグラフに含まれる三角形の個数は平均(d-1)^3/6のポアソン分布に従う
　ということが分かっています. なんでポアソン分布が出てくるのかというと, 二項分布を近似しているからです. 一般にk角形の個数は平均(d-1)^k/2k のポアソン分布に従うようです.
　「そもそもどうやって正則グラフを一様サンプリングするの？」という疑問が出てきますが実はこのサンプリング自体も研究テーマになっていて, FOCSというすごい国際会議に出てたランダム正則グラフの高速なサンプリングアルゴリズムについての論文が載っていました. 最も有名なサンプリングの方法としては「paring model」「switch」という手法があります.

・グラフ上のランダムウォークの定常分布への収束速度

グラフ上でのランダムウォークをマルコフ過程と見なし, 定常分布へどれくらいのスピードで収束していくかという議論があるのですがこれはグラフのラプラシアンの第二固有値と深く関わってくる、というものです.
　そもそもグラフのラプラシアンの固有値の集合のことをそのグラフのスペクトルと呼ぶらしいのですが, このスペクトルについての理論として「グラフスペクトル理論」というのが存在します. たとえばグラフ連結成分の個数はスペクトルの中の0の個数と等しい,「正規化されたラプラシアン」のスペクトルを使ってあるグラフが二部グラフであるための必要十分条件を与えることができる, などといったことがあります.

アルゴリズム部門

・xor swap

え、なんでこれだけでswapできるの！！？え！？！？？！

・ワーシャルフロイド法

　え、なんでこんな簡単なコードで全点対最短経路を求められるの！！？え！？！？？！
　なんとなくですがワーシャルフロイド法の正当性の証明は考えるとためになるような気がします.

・Tseitin transformation

任意の論理式を, その論理式のSAT性を保ったままCNFに変換するというものです. しかし変数は若干増えるため, 元の論理式と得られたCNFは同値ではありません. 詳しくは以前の記事で説明しています. 初めて知ったときは素直に「頭良いなぁ」と思いました.

位相空間と可測空間の対比

前までは位相空間や可測空間と聞くとどうしても「オェ...」ってなってしまっていたのですが、最近になってザリスキー位相やマルチンゲールについて学んでいくうちにどうしてもこれらの単語について知っておかねばならなくなったので少し勉強しました.

「位相空間」の定義と「可測空間」の定義は意外と似ているので対比して紹介しようと思います. 参考文献として Real and Complex Analysis (著: Walter Rudin) を挙げます.

以下, 位相空間に関する諸定義をT, 可測空間に関する定義をMと表すこととします.

T: 非空な集合Xに対し, O ⊆ 2^X が以下の条件を満たすとき, これら二つの組 (X, O) を「位相空間」と呼ぶ.
(1): ∅, X ∈ O.
(2): A1, ..., An ∈ O ならば (Aiの有限個の積) ∈ O.
(3): 各λ∈Λに対し, A_λ ∈ O ならば, U A_λ ∈ O

M: 非空な集合Xに対し, F ⊆ 2^X が以下の条件を満たすとき, これら二つの組 (X, F) を「可測空間」と呼ぶ.

(1): X ∈ F.

(2): A ∈ O ならば (Aの補集合) ∈ F.

(3): A1, ..., An ∈ O ならば (Aiの有限個の和) ∈ F.

	位相空間	(X,O)	可測空間	(X,F)
	位相	O	σ-代数	F
	開集合	Oの要素	可測集合	Fの要素
	連続写像	開集合の逆像が開集合	可測関数	開集合の逆像が可測集合

ここで, 可測関数とは可測空間から位相空間への写像のうち, 表中の性質を満たすもののことを言います.

このように見てくるとなんかスッキリした形になりますね.