2017年3月26日日曜日

駆け足で学ぶ「グラフマイナー定理」

0. 概要


グラフマイナー定理とは

有限グラフの全体は, マイナー順序によってよい擬順序になっている (well-quasi-ordered)

という定理です.

...さてこれは何を言ってるんでしょうか. 本記事では現代のグラフ理論において最も重要な定理の一つであるグラフマイナー定理について、その中身と研究背景をグラフ理論の観点から可能な限りちゃんと書いていきたいと思います. なお本記事では「グラフ」とは単に有限グラフのことを指すこととします. また, 頂点にラベルは付いていないものとします.

 章の構成は以下です. グラフマイナー定理の凄さをアピールする記事なので, 研究背景の説明に重きをおいています. 内容を知りたい方は4章から読んでください.

  •  1~3章 : グラフマイナー定理の研究背景
  • 4章 : グラフマイナー定理の内容の説明
  • 5章 : 木に関するグラフマイナー定理

1. 平面グラフのマイナーによる特徴づけ


 グラフマイナー定理について説明する前にその研究動機について説明したいと思います.

 世の中には様々なグラフがありますが, その中でも平面グラフと呼ばれる種類のグラフがあり, これまで多くの研究がなされてきました. 平面グラフとはグラフを紙面上に辺を交差せずに描けるようなグラフのことを指します. 数学的には球への埋め込みを使って定義されます.

図1: 左のグラフは一見すると中央で辺が交差しているように見えますが,
右のように描くことにより交差せずに描けるので, このグラフは平面グラフです.


図2: 左のグラフは $K_5$, 右のグラフは $K_{3,3}$.
どちらのグラフも平面グラフではない.

 図1のグラフはどちらも「4つの頂点を持ち, どの頂点ペアも辺で結ばれているようなグラフ」です. このグラフを頂点数4の完全グラフと呼び, $K_4$と表記します. $K_4$は図1右のように描けば辺を交差させずに平面上に描くことが出来ます.
 一方で $K_5$ (図2左) はどうかというと, 実はどんなに頑張っても決して辺を交差させずに平面上に描くことは出来ません. また, 図2右のグラフは「上と下に三つずつ頂点をもち, 上の頂点と下の頂点のペアはどれも辺で結ばれている」グラフです. このグラフは上下に三つずつ頂点があるので $K_{3,3}$と表記します (完全二部グラフとも呼ばれます) このグラフも実は平面グラフでないことを証明することが出来ます. 証明は例えば高校数学の美しい物語に載っています.

 さて, 与えられたグラフが平面的であるかどうか をどうやって判定すれば良いでしょうか. 実はこの問題はグラフの頂点数 $n$ に対して $O(n)$時間で解くことが出来ます [1].

 そのアルゴリズムで使われている定理が Kuratowski の定理 です. この定理は平面グラフの特徴づけを与えている定理で, 次のようなものです:

定理 (Kuratowski, 1930)

グラフ$G$が平面グラフであることの必要十分条件は, $G$が$K_5$と$K_{3,3}$の細分を部分グラフとして含まないことである.



ここでグラフ$H$の細分とは, $H$の辺をいくつか指定して, それぞれの辺を任意の長さ(ただし1以上)のパスに置き換えて得られるグラフです. 具体的には次の図を見てください.

図3: $K_4$の細分の例です.
(上):太線で書かれた辺を長さ3のパスに置き換えています.
(下):選択する辺は複数本でもよく, 更にそれぞれ異なる長さのパスに置換しても良いです.

 グラフ$G$がグラフ$H$を部分グラフとして含む, というのは $E(G),\,E(H)$ をそれぞれ $G,\,H$ の辺集合としたときに, $E(H) \subseteq E(G)$ となることを言います. $G$から頂点と辺を何本か取り除くと $H$ が得られる, と言い換えることも出来ます.

 $K_5$の細分と$K_{3,3}$の細分を部分グラフとして含まない, というのは中々強い要請であることが分かります. 例えば, これらの細分を含むようなグラフは必ず次数3以上の頂点を4つ以上持つため, 「次数3以上の頂点が高々3つならば, そのグラフは平面グラフである」ということが証明できたりするわけです(*).

(*): グラフ $G$ が グラフ $H$ の細分を部分グラフとして含むとき, $G$ は $H$ を 位相的マイナーとして含む, と言うこともあります.

 また, Kuratowski の定理と似たような平面グラフの特徴づけの定理が次に示す Wagner の定理です.

定理 (Wagner, 1937)

グラフ$G$が平面グラフであることの必要十分条件は, $G$が$K_5$と$K_{3,3}$をマイナーとして含まないことである.



Kuratowski の定理と似ていますがこちらには「マイナー」という単語が出てきています.

グラフ $G$ がグラフ $H$ をマイナーとして含む, というのは, $G$ の適当な部分グラフ $F$ が存在して, $H$は$F$の有限回の縮約操作によって得られる, という意味です (図4).

図4: $G$ のある部分グラフ $F$ から縮約操作によって $H$ が得られている.
このとき $G$ は $H$ をマイナーとして含むという.


 縮約操作とは, 辺を一つ指定してその両端点にある頂点の一つの頂点に合体させる操作を指します. 自己ループや多重辺の生じうるものとします. 次の図を見てください.

図5: 右のグラフが縮約後のグラフになります.

 すなわち, $G$ から頂点と辺を幾つか除いた後に辺の縮約を行うことによって $H$ が得られたとき, $G$ は $H$ をマイナーとして含む, ということになります.

 さて, Wagner の定理により, $G$が平面グラフであることの必要十分条件とは, $G$の適当な部分グラフ$H$が存在して, $H$に適当な縮約操作を繰り返してやると $K_5$ または $K_{3,3}$ が得られる, ということになります. このように 「グラフ $X$ をマイナーとして含まない」ようなグラフの族 $\mathcal{G}$ に対して $X$ を $\mathcal{G}$ の禁止マイナーと呼ぶこともあります. 今回で言えば, $K_5$ と $K_{3,3}$ は平面グラフの禁止マイナーということになります.


2. 四色定理 ~Wagnerのアプローチ, Hadwiger 予想~


 この章は少し蛇足気味です. 飛ばして読んでもかまいません. 当時のグラフ理論界では「四色問題」が大ブームでした. 四色問題とは次のような問題です:

四色問題 

平面グラフは4-彩色可能である.


 彩色とは, グラフの頂点に色を塗ることですが, 条件として隣接する頂点同士は異なる色で塗らなければなりません. グラフ $G$ が $k$ 色で彩色できる場合は, $G$ は $k$-彩色可能である と言ったりします. $k$ 色で彩色可能ならば $k+1$ 色で彩色することも明らかに可能なので, グラフ $G$ を彩色するのに必要な色の種類数を定義することができます. この値を 彩色数 と呼び, $\xi(G)$ と表します.

 Wagner は 平面グラフのマイナーによる特徴付けというアプローチから四色問題に取り組んでいました. 結論から言うと失敗するのですが, このときに「$K_5$ をマイナーとして含まないグラフはどのようなグラフか」という問題に対して Wagner の分解定理 と呼ばれる有名な定理を示しています.

 例えば, $K_2$ をマイナーとして含まないグラフというのは 「辺を含まないグラフ」であり, $K_3$ をマイナーとして含まないグラフというのは, 森 (閉路を含まないグラフ) となります.

 ここで重要なのは, これまでの結果として

  • $K_2$をマイナーとして含まないグラフは 1-彩色可能
  • $K_3$をマイナーとして含まないグラフは 2-彩色可能
  • $K_4$をマイナーとして含まないグラフは 3-彩色可能
  • $K_5$をマイナーとして含まないグラフは 4-彩色可能

 ということが示されたことです. では,

$K_{t+1}$ をマイナーとして含まないグラフは $t$-彩色可能 なのでしょうか?

この予想は Hadwiger 予想と呼ばれるもので, グラフ理論の最重要かつ最難な未解決問題といわれています. (今なお未解決です)


3. Wagner 予想


 2.で述べたように, Wagner は 四色問題を解決するために, 平面グラフをマイナー (縮約) という概念からアプローチしていました. その結果として, 平面グラフを二つの禁止マイナーによって特徴付けることに成功しました.

図6: 平面グラフを縮約しても平面グラフのままである.


ところで, 上の図から分かるように, 平面グラフは縮約操作に関して閉じているということが分かります. つまり平面グラフに対して縮約操作を行って得られたグラフもまた平面グラフです. 即ち平面グラフの全体はマイナーに関して閉じています.

 一般に, グラフ族 $\mathcal{G}$ に対して, 任意のグラフ $G \in \mathcal{G}$ に対して, $G$に縮約操作を行って得られるグラフもまた $\mathcal{G}$ に属するとき, $\mathcal{G}$ をマイナーに関して閉じている (minor closed) と言います.

 例えば $\mathcal{G}$ として「トーラスに埋め込むことの出来るグラフ全体」「射影平面に埋め込むことの出来るグラフ全体」などはマイナーに関して閉じています. これらのグラフは 禁止マイナーを使って特徴付けられるでしょうか? つまりマイナーに関して閉じているようなグラフ族 $\mathcal{G}$ 及び任意のグラフ $G$に対し,

$G \in \mathcal{G}$ であることと $G$ は $X_1,\,X_2,\,\ldots$ をマイナーとして含まない ことは必要十分条件である.

となるようなグラフの集合 ${\bf X} := X_1,\,X_2,\,\ldots$ をとることは可能なのでしょうか?

$X$が無限集合でも良い場合は明らかに, ${\bf X}$ を $\mathcal{G}$に含まれないグラフの全体 とすることによって条件を満たすことが出来ます. でも平面グラフの場合は, ${\bf X}=\{K_5,\,X_{3,3}\}$ と有限集合で取ることが出来ました.

実は先ほどの例で挙げた 「トーラスに埋め込むことの出来るグラフ全体」「射影平面に埋め込むことの出来るグラフ全体」は有限個の禁止マイナーで特徴付けられることが証明されています. そこで出てきたのが次のWagner 予想 です.


予想 (Wagner)

マイナーに関して閉じているようなグラフ族は, 有限個の禁止マイナーで特徴付けることが出来る.


この予想はグラフ理論の難しい未解決問題として知られていました. しかしSeymour と Robertson の二人が 1984年に「木分解」と呼ばれる斬新なテクニックを用いてこの予想を肯定的に解決しました. この二人が示したのが次に示す主張で, 現在ではこの主張を「グラフマイナー定理」と呼ばれます.


定理 (Seymour, Robertson, 2004)

グラフの全体はマイナー順序によって, よい擬順序付けられている.

そしてこの定理と Wagner 予想 が同値であるので, めでたく Wagner 予想が肯定的に解決された, ということになります.

この二人は1984年に Wagner 予想の解決を発表してから 2004年まで, 通算で500ページにもわかる長大な論文を20年もかけて書き上げました. こうして証明されたグラフマイナー定理から得られる系は沢山あり, グラフ理論のみならず組合せ最適化の分野にも影響を及ぼしました.

4. グラフマイナー定理


 3章までがグラフマイナー定理の誕生の動機でしたが, 本章からはその内容について書いていきます.

4.1. マイナー順序


 数学においてはしばし「順序関係」という言葉が使われます. 一般には数の大小や単語の辞書式順序などの意味でよく使われると思いますが, 今回は グラフの順序 として, マイナー順序というのを考えます. 順序については こちらの記事 で用語の解説を書いています.

定義 (マイナー順序)

二つのグラフ $G,\,H$ に対し, $H$が$G$をマイナーとして含むとき, $G \preceq H$ と表す. この順序 $\preceq$ を マイナー順序と呼ぶ.

 全順序は以下の四つの公理を満たすような順序でした:
  1. $a \preceq a$. (反射律)
  2. $a \preceq b,\,b \preceq c$ ならば $a \preceq c$. (推移律)
  3. $a \preceq b$ かつ $b \preceq a$ ならば, $a=b$ (反対称律)
  4. 任意の $a,b$ に対して $a \preceq b$ もしくは $b \preceq a$ のどちらかが成り立つ (全順序律)

 しかしマイナー順序は全順序ではありません. 例えば $K_5$ と $K_{3,3}$ は一方が他方をマイナーとして含むようなことはないので, この順序では比較できません. このようなペアのことを 比較不能対 と呼ぶことにします. 有限グラフ上のマイナー順序は上に挙げた中で 1,2,3が成り立つので, この順序は半順序です. が, 今回では参考文献[2]に従って 擬順序 として考えることにします.

4.2. よい擬順序 (well-quasi-order)


 順序集合 $(X, \leq)$ で $\leq$ が擬順序 になっていて, 更に $X$ が無限集合であるようなものを考えます. 例えば $X$ として 平面グラフの全体, $\leq$ として マイナー順序 とするのが良いでしょう. $X$ 上の無限列 $(x_1,x_2,\ldots)$ を考えます. この列が よい列 (good) であるとは, あるインデックス $i<j$ が存在して $x_i \leq x_j$ となることをいいます. そして $X$ 上の任意の無限列が よい列 であるならば, $\leq$ は 良い擬順序 (well-quasi-order) といいます. また, 無限列 $(x_1,x_2,\ldots)$ が 反鎖 であるとは, この列に含まれる任意の二要素が比較不能であることをいいます.

 $(x_1,x_2,\ldots)$ が よい列 でないということは, 任意の $i<j$ に対して, $x_i > x_j$ もしくは $x_i$ と $x_j$ は比較不能 であるということです. 実は $\leq$ が $X$上で 良い擬順序であるための必要十分条件は, $X$は 狭義単調減少無限列 も  反鎖 も含まないことであるという定理が証明できます.

 少し例を挙げます.

  • $X=\mathbb{Z}$, $\leq$ を通常の整数の大小関係としましょう. このとき $X$ 上の無限列として $(-1,-2,\ldots)$ という狭義単調減少無限列がとれるため, $\leq$ は よい擬順序ではありません.
  • $X=\mathbb{N}$, $\leq$ を通常の自然数の大小関係としましょう. このとき $X$ 上の無限列 として 単調減少なものはとれません. もちろん $\leq$ は全順序なので, 反鎖も存在しません. 従って $\leq$ は $\mathbb{N}$ 上では良い擬順序になっています.


 これでグラフマイナー定理の言っていることが分かると思います. つまり $X$ をグラフの全体, $\leq$ をマイナー順序 として定義したときに, $\leq$ は $X$ 上で良い擬順序になっている, と言っています. 自然数の例と同様に, マイナーの順序で単調減少な無限列はとれないので, グラフマイナー定理を言い換えると「任意のグラフの無限列 $(G_1,G_2,\ldots)$ をもってきたときに, $G_j$ が $G_i$ をマイナーとして含む (すなわち $G_i \leq G_j$) なる $i<j$ が存在する」ということになるわけです.

5. 木に関するグラフマイナー定理


 $\mathcal{T}$ を 木の全体とします. 更に $T_1, T_2 \in \mathcal{T}$ に対し, $T_2$ が $T_1$ を位相的マイナーとして含む (即ち $T_2$ は $T_1$ の細分を部分グラフとして含む) ときに $T_1 \leq T_2$ として定義します. この章では 次の定理を紹介します.

定理 (Kruskal, 1960)

上で定義した $\leq$ は $\mathcal{T}$ 上でよい擬順序になっている.


 この定理はいわば「グラフマイナー定理の木ver」と見ることが出来ます. この証明は非常にトリッキーで面白いので, 興味がある方は是非調べて見てください[2].

 私自身はグラフマイナー定理の証明をちゃんと追ったわけではないのでいい加減なことは言えないのですが, その長大な証明の大筋は次のようなロジックに従っているとのことです[2].

  1. グラフに対してその木っぽさ (木幅) を定義する.
  2. 木幅が有限なグラフに対しては, 木ver のグラフマイナー定理の証明ロジックを何回か適用させる.
  3. 木幅が大きくなってしまうグラフに対しては, 木幅が大きいという構造上の特徴を用いてなんとかする.

 この中でグラフの木っぽさという概念が非常に有用なものなので, それについては後日書きたいと思います.

[1]: J. Hopcroft, R. E. Tarjan, "Efficient planarity testing", Journal of the Association for Computing Machinery, 21 (4): 549–568, 1974
[2]: R. Diestel, "Graph Theory", 2000

全順序・半順序・擬順序

概要


 数学では様々な順序を考えることがあります. 一番簡単な例で言うと実数の全体 $\mathbb{R}$ において, $x,y\in \mathbb{R}$に対し$y-x\geq 0$ を $x\leq y$と定義して順序集合$(\mathbb{R},\leq)$を考えることが多いです. 実数だけではなく, 例えばグラフ理論でも順序を考えたりすることがあります.
 本記事では, 順序の公理について述べ, 全順序・半順序・擬順序について一気に述べたのちに例を幾つか挙げたいと思います.

解説単語 : 擬順序(前順序), 半順序, 全順序


順序の定義


 集合 $E$ (有限でも無限でもよい) に対し, $R: E\times E \to \{0,1\}$ を 関係 と呼びます. 特に, $R(x,y)=1$となるときは $x R y$と書くことがあります. 例えば $E=\mathbb{R}$, 関係$R$ として 「$\leq$」 を考えるとこれは大小関係を表す関係になっています. また, 「$=$」 という関係も考えることが出来ます. これは等号の関係です. このように見ると, 関係というのは非常に抽象的なもので, 表現力が非常に高いものだということが分かると思います.

 関係 $R$ が, 集合 $E$ に対していわゆる「順序」を付与するような関係である(即ち大小関係を決定するような関係である)ならば, そのことを強調するために $R$を順序と呼び, $\leq$ などと記述します. そして組 $(E, \leq)$ のことを 順序集合と呼びます.

 順序 $\leq$ として, 次の性質を満たすものを考えましょう:

  1. 任意の $a \in E$ に対して $a \leq a$ (反射律)
  2. $a,b,c \in E$ が, $a\leq b$, $b \leq c$ ならば $a \leq c$である (推移律)
  3. $a,b \in E$ が $a \leq b$, $b \leq a$ ならば $a=b$ である (反対称律)
  4. 任意の $a,b\in E$ に対して $a \leq b$ もしくは $b \leq a$ のどちらかが必ず成り立つ (全順序律)
 例えば 実数における通常の順序を考えると1~4の全てを満たしていることが用意に分かります. このように, これら全ての条件を満たすような順序 $\leq$ を特に 全順序 (totally order) と呼び, 全順序$\leq$ に対して $(E, \leq)$ を 全順序集合 (partially ordered set) と呼びます. また, 1~3を満たすものは 半順序 (partially order) と呼び, 1と2を満たすものは 擬順序 (quasi order) と呼ばれます.
 まとめると
  • 全順序 : 1~4 を満たす
  • 半順序 : 1~3 を満たす
  • 擬順序 : 1~2 を満たす
です. 注意されたいのは, 全順序は半順序でもあり, 擬順序でもあるということです. 

 さて, これらの三つの順序の概念について, 幾つかの例を挙げながら見ていきましょう.


例(i). 集合の包含関係


 $U$を空でない集合とし, $E=2^U$ としましょう. 即ち $E$ は$U$の部分集合族です. このとき, $A, B\in E$ はそれぞれ$U$の部分集合となっています. そして $A \subseteq B$ ならば $A \leq B$ と定義しましょう. さて, $(E,\leq )$ はどんな順序集合になっているでしょうか?

 例として $U=\{1,2,3,4,5\}$ としてみます. $A = \{1,2,3\},\,B=\{1,2,3,4\}$ のときは $A \leq B$ となりますが, $A=\{1,2,3\},\,B=\{2,3,4\}$のときは $A\leq B$ でも $B \leq A$ でもありません. 順序の公理のうち, 4だけが満たされないので, この順序は半順序となります. ちなみに $A \leq B$ でも $B \leq A$ でもない組$(A,B)$ のことを 比較不能対 と呼びます.



例(ii). ビッグオー


 $E$ として, 自然数から正実数への関数の全体 としましょう. すなわち $E := \mathbb{N}^{\mathbb{R}_{>}}$ とします. そして, $f, g\in E$ に対して, $f(n)=O(g(n))$ のときに $f\leq g$ と定義します.
 即ち, ある $m \in \mathbb{N}$ 及び 定数 $c>0$ が存在して, 任意の $n \geq m$ に対して $f(n) \leq c \cdot g(n)$ が成り立つ, というときに $f \leq g$ と書くのです.

 オーダーによって定められたこの関係$\leq$ は,
  1. $f(n) = O(f(n))$ より, $f \leq f$ (反射律)
  2. $f(n) = O(g(n)),\,g(n)=O(h(n))$ ならば, それぞれの定数を$m_1,c_1,m_2,c_2$ としたときに $m=max(m_1,m_2)$, $c=c_1 \cdot c_2$ ととれば, 任意の $n \geq m$ に対し $f(n) \leq c_1 \cdot g(n) \leq c_1 c_2 \cdot h(n)$ となるので, $f \leq h$ (推移律)
 となるので, 擬順序となっています. 更に, $f(n)=n^2,\,g(n)=n^2+1$ と定義すると, $f \neq g$ でありしかも $f \leq g$ かつ $g \leq f$ となっているため, 条件3を満たしません. 即ちこれは 擬順序だが半順序でない例 になっているわけです.

例(iii). 確率変数


 確率空間 $(\Omega,\,\mathcal{F},\,P)$ 上の二つの確率変数 $X,Y:\Omega \to \mathbb{R}$ が

任意の $x \in \mathbb{R}$ に対して $\mathrm{Pr}(X \geq x) \leq \mathrm{Pr}(Y \geq x)$

を満たすとき, $X \leq Y$ と定義します. (ちなみにこのとき $Y$ は $X$ を支配する (dominate) と言います)

 気持ちとしては 「$X\geq x$ となる確率よりも $Y \geq x$ となる確率の方が高い」ということなので, 「$X$ よりも $Y$ の方が 大きい値をとりやすい」ということになります. 例えば「表の出る確率が0.5 のコインを $n$ 回投げて, 表が出た回数」を $X$, 「表の出る確率が 0.7 のコインを $n$ 回投げて, 表が出た回数」を $Y$ とすると, 明らかに$Y$のコインの方が表が出やすいので, 直感的には $X \leq Y$ な気がしてきます. (実際にこれは確率論で使われる「カップリング」と呼ばれるテクニックを用いて鮮やかに示すことが出来ます)

  1. $\mathrm{Pr}(X \geq x) = \mathrm{Pr}(X \geq x)$ なので, $X \leq X$.
  2. 任意の$x,y\in \mathbb{R}$ に対して, $\mathrm{Pr}(X \geq x) \leq \mathrm{Pr}(Y \geq x)$, $\mathrm{Pr}(X \geq y) \geq \mathrm{Pr}(Y \geq y)$ ならば, 任意の$z \in \mathbb{R}$に対して $\mathrm{Pr}(X \geq z) \leq \mathrm{Pr}(Y \geq z) \leq \mathrm{Pr}(Z \geq z)$ となるので, 推移律も成り立ちます.
 一方で, 例えば「確率0.5で表が出るコインを $2n$ 回投げたとき, 前半の$n$回の中で表が出た回数を $X$, 後半の$n$回の中で表が出た回数を $Y$」としてみると, $X$と$Y$は同じ分布に従うので$X \leq Y$かつ$Y \leq X$なのですが, 確率変数としては異なるので, $X \neq Y$です(*).

(*): 「確率変数として異なる」という部分を細かく議論します. 確率変数とは $\Omega$ から 実数 への$\mathcal{F}$-可測写像なので, $X=Y$ ということは 任意の $\omega \in \Omega$ に対して$X(\omega)=Y(\omega)$ ということを意味しています. 今回のコイントスの例では標本集合$\Omega$を $\Omega = \{0,1\}^{2n}$ として, σ-集合体を $\mathcal{F}=2^{\Omega}$ として, 確率測度$P$を$\Omega$上の一様分布とします. (つまり任意の $\omega \in \Omega$ に対し $P(\omega)=1/2^{2n}$). そして $\omega = \{\omega_1,\omega_2,\ldots,\omega_{2n}\}\in \{0,1\}^{2n}$ に対して, $X(\omega)=\omega_1+\omega_2+\cdots+\omega_n$, $Y(\omega)=\omega_{n+1}+\omega_{n+2}+\cdots+\omega_{2n}$ と定義します. すると $X, Y$ はコイントスの例と同じ分布に従うような確率変数となっていて, 明らかに $X\neq Y$ となっています.


例(iv). 有向グラフ


 有向グラフ $G$ 上の 2頂点 $a,b$ で, $b$ から $a$ への有向パスが存在するとき, $a \leq b$ と定義します. 
  1. $a$ から $a$ へは長さ0のパスがあると見なすので, $a \leq a$ です.
  2. $a \leq b,\,b \leq c$ ならば, $c$ から $b$ をつたって $a$ にいたるパスがあるので, $a \leq c$ となります.
 従ってこの順序関係は 擬順序 となります. 更に, $G$ が DAG の場合は条件3も満たすので, 半順序となります. 更に$G$のトポロジカル順序が一意の場合は, 条件4も満たすので全順序となります.

2017年3月10日金曜日

有名な東大の問題



1998年の東大の後期入試の問題で、「大学入試史上で最も難しい問題」といわれているみたいですがグラフ理論の問題なので、解いてみることにします。

問題文にある二つの操作(白頂点の追加、辺の細分)をそれぞれ(I), (II)と記すことにします。

小さい例で試すと、
長さ$3n+2$のパスは生成できなくて、長さ$3n$もしくは$3n+1$のパスは生成できないっぽいので答えとしてはこれになることが簡単に予想できると思います。でも長さ$3n+2$のパスが生成できないことを示すのが難しいです。

少し考えて見ると, 長さ$3n+2$の白パスは、黒丸からスタートすれば生成できる、ということが分かります。
ここでいう「パス」とは一本になっているグラフのことで、色は何でも良いこととします。(細かいことですが、頂点にラベルは付いておらず、左右反転して得られるものは異なるパスであると約束します)

そこで、補題として
「黒丸から生成できるパス」の全体と「白丸から生成できるパス」の全体がdisjointであることを示せばよいことになります。(これが言えれば、黒丸から生成できるパスは白丸から生成できないことになるので証明が完了する)

この補題を示すために、パスに対して不変量を考えることにします。つまりパス$P$に対して, $f(P)$という値を考え、白丸から得られるパスの不変量$f(P_1)$と黒丸から得られるパスの不変量$f(P_2)$が、どんな$P_1,P_2$に対しても必ず$f(P_1)\neq f(P_2)$になるということが示すことが出来れば、白丸から得られてしかも同時に黒丸からも得られるようなパス$P$が存在しない、つまり補題が成り立つことが示せることになります。

細かい証明とかは省きますが、不変量として
$f(P)=(2^{m-1}\cdot x_1 + 2^{m-2}\cdot x_2 + \cdots + 2^0\cdot x_m + n)$ mod $3$.
というのを考えます。
ここで$n$はパス$P$の頂点数、$m$はパス$P$が含む黒頂点の個数、$x_i$はパスを横に並べて書いたときに右から$i$番目にある黒頂点の座標(1-indexで考えていて、例えば1番右なら1, 右から2番目なら2, $\ldots$)です。

ローリングハッシュみたいな形の式をしていますが、この不変量を考えると
$P$が白丸から生成されるときは必ず $f(P)\in \{0,1\}$
$P$が黒丸から生成されるときは必ず $f(P) = 2$
となること分かり、証明が完了します。

不変量となっていることの証明は、操作(I), (II)それぞれの逆操作を考えて帰納法を使えばいけます。

2017年2月2日木曜日

The Unfounded Moore Graph

Abstract

 グラフ理論で60年くらい前から研究されてきている "Degree Diameter Problem" という問題があります. 本記事ではこれについて簡単な説明を与えます. そしてこの問題の最適解の一つである "Moore Graph" について書いていきます. しかし今現在もなお, とある Moore Graph は今もなお見つかっておらず, 存在しないのではないかとさえ言われています. (存在性の否定も肯定も2017年2月2日現在未解決です). 
 未だにみつかっていない Moore Graph の存在性はいわばパズルのようなものであり, 電車の暇な時に考えてると時間を簡単につぶせるような, 面白い問題だと思ってます. 
 この記事では特に事前知識を仮定しません. グラフ理論やアルゴリズムの基本的な用語(幅優先探索, 次数, 最短経路) が分かっていれば誰でも理解できると思います. この記事を読んでチャレンジしてみようという気が起きる方が少しでも増えてくれたら嬉しいです.

Introduction

 連結な無向グラフ $G=(V,E)$ が与えられたとき, $D:=\max_{s,t\in V} \mathrm{dist}(s,t)$ を $G$ の直径と呼びます. ここで $\mathrm{dist}(s,t)$ は二頂点間の最短経路長と定義します.
言い換えると, どの二頂点を選んでも $D$ ステップあれば必ず互いに到達できるような $D$ のうち最小の値が直径といえるわけです. 直径 $L$ の円 $C$ を考えるときに, 任意の二点 $x,y\in C$ に対し, $|x-y| \leq L$ となるわけなので, いわゆる円に対する直径のアナロジーとしても自然な定義だと思います.

 少し余談になりますが, しばしば直径が小さいということが話題になることがあります. 特に有名なのが複雑ネットワークの「スモールワールド性」です. これは Facebook や 論文のcitation が構成するネットワークを考えるとその直径が小さいということを意味しています. なぜ直径が小さくなるのか?といった疑問に対し, 複雑ネットワークを生成するようなモデル(有名なものとしてBAモデルがあります)を考え, そのモデルによって生成されたグラフの直径を考察する, というような研究が多くあります.

 さて, 今回も小直径なグラフの話題になります. 頂点数 $n$ のグラフ $G$ のうち, 直径が最小のものを見つけよ, という問題を考えます, 考えるまでもないことですが, $G$ を $n$ 頂点の完全グラフとすれば明らかに $D=1$ で最小となるので, 自明な答えが得られます.

 一方で, 「各頂点の次数が $d$ 以下」 という制約条件を付加することにより, 問題は格段と難しくなります. この問題は Order Degree Problem と呼ばれる問題で, 非常に難しい問題であることが知られていて, NIIがこの問題に関するコンペティションを年一回開いています(Graph Golf). このコンペティションでは, $n,d$ が与えられるので, 出来るだけ直径が小さいグラフを作れというようなコンテストです. 詳細はページを見てください.

一方で, 「各頂点の次数は $d$ 以下」 かつ 「直径が$D$以下」 となるようなグラフのうち, 頂点数が最大のものを求めよ, という問題も考えられると思います. この問題は Degree Diameter Problem と呼ばれ, こちらの問題も難しいとされているのですが, 実はグラフ理論ではこの問題は有名問題で, 色んな研究があります.


Moore Bound


Edward F. Moore


 それらの研究の中でも最も基本的なワードの一つが "Moore Bound" です. Moore とは Edward F. Moore のことで, オートマトンの分野で知られている「エデンの園定理」を示した人物です.

 例として直径2, 各頂点の次数が3であるようなグラフ $G$ の持ちうる頂点数の上界について見ていきます. $G$の頂点 $r$ を任意に一つ選び, $r$を始点として幅優先探索を行うことを考えます. $G$ の直径は2なので, 幅優先探索は深さが高々2までしか探索しないので, 次のような図が出てくるはずです.


 したがって, 次数の制約から, 頂点数を最大にしようとすると次のようなグラフを考えることになります:

BFS-tree


 これ以上頂点を多くしようとすると, 直径または次数の制約どちらかが破られてしまうので, 直径2次数3のグラフの頂点数は高々10であるということが分かると思います. 即ちこの10という値は頂点数の上界を与えています.
 このように考えると, 直径 $D$ , 次数 $d$ であるようなグラフの持ちうる頂点数の上界は

$1+d+d(d-1)+d(d-1)^2+\cdots+d(d-1)^{D-1}$.

で与えられます. この上界は Moore Bound と呼ばれます.

Moore Graph

ここで, Moore Bound はタイトなのかという疑問が自然に生じてきます. Moore Boundの導出の際に頂点 $r$ を一つ固定して幅優先探索を考えていましたが, どの頂点を始点にしても同じBFS木が生成されるようなグラフでなければならないので, タイトであるかどうかは非自明な問題となってきます. 実は上の例で紹介した $D=2, d=3$ ではこの上界を達成する (即ち頂点数10)ようなグラフが存在します. 次の図で示すグラフが該当します:

Petersen Graph

 実際, 各頂点の次数は3に等しく, しかもどの二頂点を選んでも二歩以内に互いに到達することが出来ることが確認できると思います. この図に示したグラフは Petersen Graph と呼ばれる非常に有名なグラフで, $D=2, d=3$の場合はこのグラフのみが Moore Bound を達成するグラフであることが示せます. (即ち, uniqueです) このように, Moore Bound と等しい頂点数を持つようなグラフのことを Moore Graph と呼びます.

When do Moore Graphs exist?

$D \geq 2$ のときにMoore Graph が存在するかどうかという問題について, 結果から言うと

  • $D>2$のときは存在しない.
  • $D=2$ かつ $d\neq 2,3,7,57$ のときは存在しない.
ことが示されます. 2番目の事実は隣接行列の固有値を考えることで示すことが出来ます[1].

2番目の事実ついて, $D=2$の場合:
です. $d=57$のときは "Moore graph が存在するかもしれない" という可能性はあるのですが, 未だに見つかっておらず, その存在性は2017年2月2日現在でも未解決問題です.

また一方で, Moore bound に近い頂点数を持つようなグラフを構成するという研究も存在します. これらの分野では, グラフのCartesian product などを考えて構成していくというもので, 僕はあまり詳しくはないのですが, Algebraic Graph Theory などの分野だと思っています. 詳しくは[1]にあります.

面白い事実としては, 頂点数$n$が次数$d$に対して $n=d^2$となるようなグラフの中で直径が2であるようなものは, $d=2$を除いて他には存在しないという定理が知られています[2]. しかし$n=d^2+1$の場合はMoore Graph そのものなので, いかにMoore Graph が珍しいグラフであるかが分かると思います.

Some Characteristics of the UNFOUNDED Moore Graph


頂点数を$n$, 次数を$d$とし, $n=d^2+1$のケースを考えます.
Moore graph の満たす性質を幾つか挙げていきます.

- No Triangles, No squares

三角形と四角形を含まない. $\iff$ Moore graph である $\iff$ 直径が2である.

を示すことが出来ます.
証明は簡単で, 三角形や四角形を含むグラフに対し, その三角形(または四角形)に含まれる頂点を一つ選んで $r$ とし, $r$を始点として幅優先探索を行うと, 次の図のようになります.
橙色の頂点は四角形

 すると$n \leq d^2$となってしまうので矛盾します. 逆向きも簡単に示すことが出来ます.

- Equation for Adjacency Matrix


次に, Moore graph の隣接行列を $A$ と書くと, 次の方程式が成り立ちます:

$A^2+A = (d-1)I + J$.

 ここで $I$ は単位行列, $J$ は全ての成分が1の行列です. これも簡単に分かります. 
 $A^2$ の $ij$成分は 頂点$i$ から 頂点$j$ への長さ2のウォーク(同じ頂点を通っても良い)の個数になります. 三角形も四角形もないとき, $i \neq j$ ならば, $A_{ij}$ と $A^2_{ij}$ はどちらか一方のみが 1 となり, もう一方は 0 となります. 更に, $i=j$ならば, $A_{ii}=d$ となるので, 上に示した方程式が成り立つということになります.

 しかも, この性質を使えば$A$の固有値も求めることが出来ます. 今, $A$の固有値 $\lambda$ に対応する固有ベクトルを $x$ とすると,

$(A^2+A)x = (\lambda^2 + \lambda) x$

となるので, $x$ は $\lambda^2+\lambda$に対応する固有ベクトルになっています.
したがって, $(d-1)I+J$の固有値を求めると, そこから $\lambda$ を求めていくことが出来ます.

- Vertex Transitivity

 日本語で頂点推移性と呼ばれます. 結論から言うと, $d=2,3,7$の現在知られている Moore graph はどれも頂点推移性を満たしているのですが, もし$d=57$の Moore graph が存在するならば, そのグラフは頂点推移性は満たさない, ということが知られています.

 頂点推移性を定義するためにはまずグラフの自己同型群を定義しなければなりません。グラフ$G$の自己同型群$\mathrm{Aut}(G)$とは, $G$の自己同型写像の全体及び写像の合成による群のことです. $f:V(G) \to V(G)$が$G$の自己同型写像であるとは, $f$が全単射かつ

$\{x,y\} \in E(G) \iff \{f(x),f(y)\} \in E(G)$

を満たすことを言います. 直感的に言えば, 自己同型写像とは隣接関係を保存するような頂点上のpermutation (置換) であるということが出来ます.

 グラフ$G$が頂点推移性を満たすというのは, 任意の二頂点$u,v \in V(G)$に対し, $f(u)=v$となるような$f \in \mathrm{Aut}(G)$が存在することを言います.

 例えば $G$ として長さ 5 のサイクル ($V(G)=\{0,1,2,3,4\}$, $E(G)=\{01,12,23,34,40\}$) を考えると, 頂点のラベルを時計周りに一個ずつずらす ($f(v)=(v+1) \mathrm{mod} 5$) ような置換は自己同型写像になっていることが分かります. また, 任意の頂点を二個, 例えば0と3を選んだとすると, $f(v)=(v+3) \mathrm{mod} 5$ ととれば $f$ は $f(0)=3$ となるような自己同型写像になっているので, このサイクルは頂点推移性を満たすことが分かります.

Conclusion

 Moore graph について紹介しました. 特に$d=57$の場合における Moore graph の存在性についての問題は長い間未解決問題になっています. この問題は次のように言い換えることが出来ます.

「頂点数3250 (=$57^2+1$), 次数57 のグラフのうち, 三角形も四角形も含まないようなものが存在するか否か」

こう考えるとパズルのような問題で面白いと思います.

 しかしこのパズルのような問題でも, グラフ理論では長い間 (今なお) 未解決問題として知られているのです. ぜひ, 挑戦してみてはいかがでしょうか.

References

  • [1] M. Miller and Jozef Siran : "Moore Graphs and Beyond : A survey of the Degree/Diameter Problem", The Electronic Journal of Combinatorics, 2013
Moore Graph に関するサーベイ論文で, 有向グラフバージョン, 二部グラフバージョンなど, 様々な関連問題のほかにも, キレイ(何らかの群や代数的操作によって生成されるよう)なグラフのつくり方なども載っていて非常に網羅的で良いサーベイ論文だと思います.

  • [2] P. Erdos, S. Fajtolowicz and A. J. Hoffman : "Maximum Degree in Graphs of Diameter 2", Networks 10 (1980) 87-90
$n=d^2$かつ直径2 であるようなグラフは, 長さ4の閉路を除いて他に存在しないという定理を証明した論文です. 証明にはグラフの隣接行列の固有値を用いた議論が使われています.

2017年1月7日土曜日

条件付期待値のキモチ

条件付期待値についてなんとなくつかめてきた気がしたので備忘録がてら書きます. 勉強中なので些細なところで間違えてるかもしれません. (逐次修正していく)

*今回は確率変数は全て標本空間から実数への関数だとします.

条件付確率というのはP(A | B)で,
P(A | B) := P(A ∩ B) / P(B)
として定義されます.
これをもとにして条件付期待値 E(X | A) は
E(X | A) := Σx P(X=x | A)
などと定義され, これはよく慣れ親しんだものだと思います.

しかし測度論的な条件付期待値は違う定義をされていて, 慣れるには中々時間のかかるものだと思います.
例えば, 古典的な定義によると条件付期待値は E(X | A) などと書いたときは X は確率変数で A は事象のはずです. また E(X | A) はデータ型として見ると実数です.
しかしながら測度論的な定義では E(X | G) などと書き, この場合は X は確率変数, G はσ-集合体 となっていて, しかも E(X | G) 自体はG-可測な確率変数になっています.

Gは事象の集合であり, 古典的な定義と絡めて述べると, (誤解を恐れずに書くと)
ω∈A∈G に対し, E(X | G)(ω) = E(X | A) が成り立つので, 古典的な定義と齟齬は生じないこととなっています.

本記事では測度論的な条件付期待値の定義を述べるとともに, 単純な例を紹介したいと思います.


定義

確率空間 (Ω, F, P) 及び 事象A ∈ F  と 確率変数 X に対し,

E[X ; A] := E[X・1_A]

とします. つまり事象A における測度 P での X のルベーグ積分です.
今, G F  を の部分σ-集合体とします.
G が与えられたときの X の条件付期待値 E[X | G] とは, 以下の条件を満たす G-可測  な確率変数です.
  • 全てのA ∈ G に対し,  E[X ; A] = E[Y ; A]
このような確率変数の存在性はラドン-ニコディムの定理から保証されます. しかもこの定理によるとE[X | G] の存在は一意です.

* ここでいう一意とは, P のへの制限を P|G  と書いたときに, (確率測度としてのP|G)測度0の点を除いた部分で考えています. 即ち, P|G(X=Y) = 1 となるような二つの確率変数 X と Y は同一視しています.

* PのGへの制限 P|とは, 全てのA∈G に対して, P|G(A) = P(A) を満たす確率測度 P|G : Ω→G のことです.

可測であるということ

最も重要な部分は E[X | G] が G-可測であるという点です.

確率変数 X が G-可測であるとは, 全ての B ∈ B(R) に対し, 逆像 X^{-1}(B) ∈ G であることを言います. ここでB(R) は実数上のボレル集合体です.

直感的な説明ですが, GF  であるとき, G-可測ならば-可測である, が成り立ちます.
従って, G-可測であるという条件は -可測であるという条件よりも強いことを要請しているわけです.

例えば, 確率変数 X が G= {φ, Ω } に対し G-可測 であったならば, 集合X(Ω) は一点集合, 即ちX=定数 でなければなりません. なぜならば X(Ω) ⊇ { a, b } とすると, X^{-1}({a}), X^{-1}({b}) がそれぞれ背反であり, 非空であるため G-可測であることに反するからです.

また, 確率変数 X が G-可測であったならば, E[X | G] = X となります. なぜならば, E[X | G] = X とおくと期待値の条件を明らかに満たすからです. (ラドン-ニコディムの定理より, 期待値の条件を満たす確率変数Zを見つければ測度0の点を除いてZ=E[X | G] となります).


  • Ω = [0,1]
  • F = B([0,1])
  • P : ルベーグ測度
とし, 確率変数 X を



を分布関数として持つようなものとします.
  • ={φ, Ω } の場合:
E[ X | G] は G-可測なので, 定数である. 期待値に関する条件より,



  • G={φ, Ω, [0, 1/2), [1/2, 1] } の場合:

また, 可測性の条件より, E[X | G](ω) は [0,1/2), [1/2, 1] それぞれにおいて定数となっているため,


となる.


Gが更に元が多くなり複雑になっていくと, E[X | G]も複雑な形になっていき, 次第に X に近づいていく, ということになります.

言ってみれば E[X | G]は Xを G-可測な確率変数で近似していると見ることもできます.