-概要-
最近 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の全域木は
- e を含むもの
- 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-彩色は
- x と y が同じ色になっている彩色
- 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 のことを言います.
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.
0 件のコメント:
コメントを投稿