2017年6月24日土曜日

多分, 読むとランダムグラフを勉強したくなる記事

0. 概要


本記事では
  • ランダムグラフ理論の動機と応用
  • ランダムグラフ理論のさわり
  • ランダムグラフの面白い定理
について書きます. 読むとランダムグラフ理論を勉強したくなります.

1. ランダムグラフ理論の動機と応用


ランダムグラフ理論の主な動機としては
  1. 「とある性質Pを満たすグラフが存在するか?」という問に対する肯定的な解決
  2. 現実のネットワークにおける様々な現象の理論的説明
歴史的には1が重要で、グラフ理論における有名問題「任意に大きい彩色数と内周(長さ最小の閉路)を持つグラフは存在するか?」をErdősらが解決した際に初めてランダムグラフを用いられました. ロジックとしては「性質Pを満たすグラフの存在性」という問に対し, Pr[ランダムに生成したグラフがPを満たす確率]$>0$であることを示すことにより, この問を肯定的に解決する, というものになります.

2は応用上重要だと思います. 現実世界のネットワーク(複雑ネットワーク)にはスモールワールド性, 高いクラスタ係数, 次数のベキ乗則といった様々な現象が観測されます. そこでWSモデル, BAモデルといった複雑ネットワークを模倣するランダムグラフのモデルを解析することによってこれらの現象の発生を理論的に説明出来るようになります.

また, ランダムグラフはグラフアルゴリズムのベンチマークとして用いられることがよくあります. しかしベンチマークとして用いる際, そのランダムグラフはどのような性質(高い確率で連結なのか, 直径が小さいかどうかなど)を持つかについて知っておかなければいけません. 例えば「小直径グラフに対してはたまたま速く動作してしまうアルゴリズム」のベンチマークとして「高い確率で小直径になってしまうランダムグラフ」を(小直径になるとは知らずに)ベンチマークとして用いて数値実験を行い「ランダムグラフで高速に動いたから大体のグラフでも動く」と結論づけてしまったら最悪です. このような事態を避けるためにも, ランダムグラフの性質についての知識や簡単な導出過程については知っておくべきでしょう.

2. ランダムグラフ理論のさわり


2.1. Erdos-Renyi (ER)モデル


 頂点数 $n$ のグラフを考えます. 各頂点ペア $u \neq v$に対し, 確率$p$で独立に辺を引きます. このグラフ生成モデルを Erdos-Renyi(ER)モデルと呼び, 生成したグラフを$G(n,p)$で表します.


 ERモデルはランダムグラフ理論で最も多くの研究結果があります. ERモデルは通常, パラメータ$p$を$p=p(n)$(つまり, $n$の関数)として, $n\to\infty$における$G(n,p)$の構造を解析します. グラフの性質$\mathcal{P}(例えば連結性, 平面性など)に対してPr[G(n,p)がPを満たす]$\to 1$ (as $n\to\infty$) ならば$G(n,p)$はほとんど確実に性質$\mathcal{P}$を満たすと言います. ランダムグラフ理論では$n$頂点のランダムグラフ(例えば$G(n,p)$)はどのような性質をほとんど確実に満たすのか, について解明している理論であると言い換えることも出来ます.

 本稿では,

  • $p=o(n^{-2})$(注*)ならば, $G(n,p)$はほとんど確実に辺を持たない.
  • $p=\omega(n^{-2})$(注**)ならば, $G(n,p)$はほとんど確実に辺を持つ.
  • $p\sim \alpha \cdot n^{-2}$(注***)ならば, $\mathrm{Pr}$[$G(n,p)$が辺を持つ]$\to 1-e^{\alpha/2}$.

を証明して, 最後に$G(n,p)$の他の面白い性質を簡単に紹介していくという流れになります.

(注*) $f,g:\mathbb{N} \to \mathbb{R}_{\geq 0}$に対し
$f(n)=o(g(n)) \, \iff \, \lim_{n\to\infty}\frac{f(n)}{g(n)}=0$

(注**) $f,g:\mathbb{N} \to \mathbb{R}_{\geq 0}$に対し
$f(n)=\omega(g(n)) \, \iff \, \lim_{n\to\infty}\frac{f(n)}{g(n)}=\infty$

(注***) $f,g:\mathbb{N} \to \mathbb{R}_{\geq 0}$に対し
$f(n)\sim g(n) \, \iff \, \lim_{n\to\infty}\frac{f(n)}{g(n)}=1 \,\iff\, f(n)=(1+o(1))g(n)$.


2.2. First Order Method



$X$を非負の値をとる確率変数とします. 任意の$a>0$に対して



が成り立ちます. この不等式をMarkovの不等式と呼びます.
$G(n,p)$の辺数$m$は非負整数値をとる確率変数なので,

.

$p=o(n^{-2})$ならば, $n^2p\to 0$ (as $n\to\infty$)より,

.

以上より, $p=o(n^{-2})$ならば$G(n,p)$はほとんど確実に辺をもたないことが示されました. 他にも, $Y=G(n,p)$が含む三角形(長さ3の閉路)の個数 と定義すると,

$\mathrm{Pr}$($G(n,p)$が三角形を含む)$=\mathrm{Pr}(Y\geq 1) \leq \mathrm{E}[Y] \sim n^3p^3/6 \to 0$ (as $n\to\infty$).

となるので, $p=o(n^{-1})$ならば$G(n,p)$はほとんど確実に三角形を含まない ことが示せました. このように, Markovの不等式を用いて「ない」ことを示す証明技法をFirst Order Methodと呼びます. なぜ "First" なのかというと, 確率変数の一次モーメント(期待値)を計算するからです.


2.3. Second Order Method



First Order MethodはMarkovの不等式を用いて「ない」ことを証明する技法でした. 一方でランダムグラフ理論では「ある」ことを証明する技法が知られています. それがSecond Order Methodです.

一般に, 平均と分散が有限となるような確率変数$X$に対してChebyshevの不等式と呼ばれる次の不等式が成り立ちます.

.

ここで, $t=\mathrm{E}[X]$を代入すると,


したがって

.

となります. この$X$が例えば「辺の本数」「三角形の個数」などを表すなら, この不等式は「辺が存在する確率」「三角形が存在する確率」の下界を与えることになります.
このように分散を使ってランダムグラフ内に「ある」ことを証明する技法を Second Order Method と呼びます. 分散$\mathrm{V}[X]$を計算するためには二次モーメント$\mathrm{E}[X^2]$を計算する必要があるため "Second" の名を冠しています.

また, $X$が非負整数値をとるとき, コーシーシュワルツの不等式を用いることで次のような不等式が示せます.


これらの不等式から共通して言えることは, $\mathrm{E}[X^2]\sim \mathrm{E}[X]^2$が示せたら$\mathrm{Pr}(X>0)\to 1$が示せるということです.

それでは, $p=\omega(n^{-2})$として, $G(n,p)$が辺をほとんど確実に持つ, 即ち $\mathrm{Pr}(m>0)\to 1$ を示しましょう. ($m=m(G(n,p))$は$G(n,p)$に含まれる辺の個数を表す確率変数). 最も肝心なのは, $m$は指示関数の和で書き表わせるということです. 即ち, $n$頂点完全グラフ$K_n$の辺$e$に対して


という確率変数を定義したとき,


が明らかに成り立ちます. 従って, 期待値の線型性より


となり, 二次モーメント $\mathrm{E}[m^2]$については


となるので, 



従って



これを上記で紹介した不等式に代入すると, $p=\omega{n^{-2}}$より$n^2p\to \infty$なので,

.


となって所望の命題が示せました. まとめると, $p=o(n^{-2})$ならば$G(n,p)$はほとんど確実に辺を持たないが, $p=\omega(n^{-2})$ならば$G(n,p)$はほとんど確実に辺を持つことが証明されました. このようにパラメータのオーダーを変えた瞬間に一気に性質のオンオフが変わってしまう性質のことを相転移(phase transition)と言います. ランダムグラフ理論ではこのような相転移現象が数多く証明されてます.

三角形の個数も指示関数の和で表せるので, 全く同様にして同じようなことを示すことができ, 相転移を観察することが出来ます.

この節の最後に, monotonicity について紹介します. グラフの性質$\mathcal{P}$が以下の性質を満たすとき, $\mathcal{P}$はmonotone increasingであると言います.

「$G$が$\mathcal{P}$を満たすならば, $G$に任意の新しい辺$e$を追加して得られたグラフ$G\cup e$も$\mathcal{P}$を満たす.」

例えば, $\mathcal{P}$を「連結であるという性質」とします. $G$が$\mathcal{P}$を満たすとき, $G$は連結グラフです. そして$G$に新しい辺を追加しても連結なままです. 従って「連結性」は monotone increasing です. 他にも「辺を持つ」「直径$\leq 100$である」「辺連結度が100以上である」「ハミルトン閉路を持つ」などの数多くの重要な性質が monotone increasing となります.

一方、性質$\mathcal{P}$を満たすグラフ$G$からどの辺を削除しても依然として$\mathcal{P}$を満たすならば, 性質$\mathcal{P}$は monotone decreasing であるといいます. 例えば「平面的である」「森である」「ハミルトン閉路を持たない」などの性質が monotone decreasingとなります.

$\mathcal{P}$をmonotone increasingであるとします.  このとき必ず相転移が発生するような閾値関数が存在するということが証明されています (Bollobas, Thomasson, 1997). 具体的には

nontrivial で monotone increasingな性質 $\mathcal{P}$に対し, ある$p^*=p^*(n)$が存在して
$p=\omega(p^*)$ならばほとんど確実に$G(n,p)$は$\mathcal{P}$を満たし, $p=o(p^*)$ならばほとんど確実に$G(n,p)$は$\mathcal{P}$を満たさない.

ことが示されています(monotone decreasing についても同様のことが成り立ちます). 例えば, 「辺を持つ」という性質では$p^*=n^{-2}$となります.


2.4. 閾値関数上の振る舞い


$p=o(n^{-2})$, $p=\omega(n^{-2})$に対する$G(n,p)$の辺の有無について解析してきました. それではこれらの中間, すなわち $p\sim c\cdot n^{-2}$のときはどうなるでしょうか?

$m$はiidな指示関数の和として書けるので, 二項分布$\mathrm{Bin}\left(\binom{n}{2}, p\right)$に従う確率変数です. ここで, ポアソンの極限定理によると,



となるので (ここでは確率密度関数が各点収束するという意), 今回の場合は



となります. 即ち, 辺の本数$m$は漸近的に平均$c/2$のポアソン分布に従うため, $\mathrm{Pr}(m=0) \to e^{-c/2}$ となります.

様々な性質$\mathcal{P}$について, $p$が閾値関数上のときの$G(n,p)$の振る舞いの確率にはポアソン分布が絡んできていることが分かっています. 例えば$G(n,p)$の頂点を一つ固定してその次数を確率分布 $d$ で表すと, 明らかに $d$ は二項分布 $\mathrm{Bin}(n-1,p) \sim \mathrm{Bin}(n,p)$に従います. 従って

・$p=o(n^{-1})$のときは



・$p=\omega(n^{-1})$のときは, $d$が指示関数の和で表せることを用いると



・$p\sim c\cdot n^{-1}$のときは, ポアソン極限定理より, $d$は漸近的に平均$c$のポアソン分布に従うため,



が簡単に示せます. 特に$d=0$ということは固定した頂点が孤立点であり, つまり$G(n,p)$が非連結であるということになるので,

.

即ち $p\sim c/n$のときは正の確率で$G(n,p)$は非連結になることが示せました.
実際には頂点を$k$個だけ固定してそれぞれの次数を$d_1,\ldots,d_k$として$k$個の確率変数を定義すると, それぞれは漸近的に平均$c$のポアソン分布に従い, しかも実は漸近的にこれらの確率変数は独立であることが言えます. つまり



となり, グラフが連結であるならば $d_1>0,\ldots,d_k>0$となるので



今, $k$は任意の自然数だったので, 右辺は任意に小さくできるので,



つまり, $G(n,p)$はほとんど確実に非連結であることが示せました.

3. ランダムグラフ理論の面白い定理


ランダムグラフ理論では閾値関数などの様々な定理が知られているので個人的に面白いと思ったものを列挙します.

3.1. 連結性




とおきます. このとき







3.2. 頂点連結度


グラフ$G$が$k$-connectedであるとは, $G$を非連結にするためには最低でも$k$個の頂点を削除しなければならないことを意味します.



とします. このとき




3.3. ハミルトン閉路


ハミルトン閉路とは, 全ての頂点を一度ずつ通るような閉路のことです. 与えられたグラフがハミルトン閉路を持つかどうかを判定する問題はNP-完全で多項式時間では判定できないとされていますが, ランダムグラフがハミルトン閉路を含むかどうかもまた大きな難問でした.



とします. このとき,




3.4. 最大独立点集合のサイズ


グラフの独立点集合とは, 頂点部分集合$S\subseteq V$で$S$の任意の二頂点間に辺が存在しないようなものです. 独立点集合のうち要素数最大なものを最大独立点集合といい, その要素数を$\alpha(G)$と書きます. 与えられたグラフに対して$\alpha(G)$を計算する問題はNP-困難ですが, ランダムグラフ理論においては次の結果が知られています.

$p\in(0,1)$を定数とし, $b=\frac{1}{1-p}$とします. このときほとんど確実に



つまり, おおよそ $\alpha(G(n,p)) \simeq 2\log_b n$.


3.5. 彩色数


グラフの彩色(頂点彩色)とは, 頂点から色への写像で, 隣接頂点同士は異なる色に写される(塗られる)という性質を持ったものです. 彩色が存在するような色の種類数のうち最小の値を彩色数と呼び, $\chi(G)$で表します. 与えられたグラフ$G$に対して$\chi(G)$を計算する問題はNP-困難です.

$p\in(0,1)$を定数とし, $b=\frac{1}{1-p}$とします. すると

おおよそ $\chi(G(n,p)) \simeq \frac{n}{\log_b n}$ となります.

(注:) 彩色数と最大独立点集合の間には, $\chi(G)\alpha(G)\geq n$という関係があってこれを用いています.




4. おわりに


 ランダムグラフ理論の動機を概説し, first order method, second order ethod, Poisson approximation theoremについて紹介しました.
 私は東大でランダムグラフ理論について研究していますが, 日本にはランダムグラフをやっている人があまり居ません(少し寂しいことですが...). ランダムグラフ理論で用いられる確率的議論(そしてそのアイデア)は, 乱択アルゴリズムの解析や組合せ論において非常に有用で, それらを学ぶことはランダムグラフのみならず他の分野でも大きな武器になるのではないかと思います(あと二項係数に強くなれます). グラフ理論と確率論のインターセクションにあるランダムグラフ理論はそれらの深い理解に通じる面白い理論であり, そしてランダムグラフ理論の勉強を通じて確率論の深い理解に繋がることがあるので, 本格的に研究しなくても学んでみる価値は大いにあると信じています.


参考文献


[1] R. Diestel, "Graph Theory"
[2] A. Frieze, M. Karoński  "Introduction to Random Graphs" (著者がドラフトをウェブ上で公開しています)
[3] ‎Bollobás, "Random Graphs"




2017年6月22日木曜日

良いと思った本

色んな本をちょくちょく読んできましたが, それぞれの感想について述べていきます (全部読んだわけではないのですが, パパッと読んで思ったことについて簡単に書きます)

Computational Complexity (S. Arora, B. Barak)


  • 茶色い本
  • チューリング機械の定義からちゃんと書いてある.
  • 説明がすごく丁寧.
  • 例が多くて分かりやすい.
  • 演習問題は難しめ.


Computational Complexity (O. Goldreich)


  • 表紙がカッコイイ.
  • トピックが広い.
  • 書いてあることは分かる(証明とかも追える)が, Arora本と比べると分かりにくい.
  • そういえばSATを3-彩色問題に帰着する証明が面白かった.


近似アルゴリズム (V. V. ヴァジラーニ; 浅野 孝夫 訳)



  • 一つ一つの章が短めで読みやすい.
  • アルゴリズムのアイデアなどを直感的に説明していて分かりやすい.
  • 演習問題も教育的.
  • LPに基づく近似アルゴリズム(ラウンディングやプライマルデュアルなど)を, 集合カバー問題を軸にして分かりやすく解説してある.


Introduction to Random Graph (A. Frieze)




  • ランダムグラフを全く知らなくても読める.
  • 測度論的確率論はほとんど用いられないので, その辺も知らなくても大丈夫.
  • 20, 21章を簡単に目を通してから1章とかを読むと良いと思う.
  • 2015年の著作なので, 分野の最新の進展が分かる.
  • 2015年の著作なので,  (Web上で公開されてるものは)タイポとかミスが多い.


グラフ理論 (R. ディーステル; 根上 生也, 太田 克弘 訳)



  • かなり有名な本.
  • イメージとしては「広く浅く」グラフ理論をカバーしている.
  • グラフ理論を初めて学ぶ人(かつしっかり学びたい人)は少なくとも1,2章はしっかりと読むべきだと思う.


組合せ論シリーズ :数え上げの手法, グラフの構造, グラフの不変数, 集合論的グラフ理論 (L. ロヴァース; 秋山 仁, 榎本 彦衛 訳)


  • 演習問題しかない.
  • 問題が羅列してあって, そのヒントと解答がすぐ下にちゃんと書いてあるのは親切.
  • 問題はそこそこ難しいものもあり, 1問解くのに数時間かかることはザラにある.
  • しかし解いていくと力がついていくので, 「時間があったらちゃんと読みたい(解きたい)本ランキング」はぶっちぎりの一位.
  • というか書いたいけど(古本含め)どこにも売ってない...




2017年6月19日月曜日

環と半環上の行列積やその検査について

行列積についてのメモついでに.

行列積アルゴリズムは応用上重要であり, これまで様々な研究がなされてきました.
現在のところ知られている最速なアルゴリズムは, $n \times n$行列$A,B$に対して$O(n^{2.38...})$時間で積$A\cdot B$を計算できます.

一方三つの$n\times n$行列$A,B,C$が与えられたときに$A\cdot B=C$であるか否かを判定するアルゴリズムは, $O(n^2)$時間で判定する乱択アルゴリズムが知られています(実際にはモンテカルロアルゴリズムで, 高々0.5の確率で$A\cdot B\neq C$なのに$A=B$と出力してしまいます).

さて, 行列積について見るとき, ほとんどの方はそれが通常の実数$\mathbb{R}$または有理数$\mathbb{Q}$上の演算で解釈しているはずです. しかし組合せ最適化の文脈ではしばしば$(\min,+)$代数が出てきます. $(\min,+)$代数は$\mathbb{R}\cup \{\infty\}$上で定義される代数系で, 要するに$a+b:=\min(a,b)$, $a\cdot b:=a+b$(通常の実数の和)として定められます. この算数は例えばグラフの最短経路を考える際に役に立ちます. そして$(\min,+)$代数の他にも数学・情報科学ではトロピカル代数(いわゆる$(\max,+)$代数のことで, Maslov 代数などとも呼ばれます), $(\max,\min)$代数, (AND, OR)代数などが知られています. ちなみにMaslov代数は本当に面白いので余裕があればこの論文この論文この記事などをさらっと眺めて見るのも良いかもしれません. そしてこれらの代数系は半環と呼ばれるものであり, "引き算"がありません. 例えば, $(\min,+)$代数においては加法の単位元が$\infty$になるわけですが, 任意の$a\in \mathbb{R}$に対して$\min(a,x)=\infty$となる$x$は存在しません. 環では加法の逆元が存在し, 半環ではそれが存在しない. これが重要なポイントです.

さて, 先ほど紹介した環上の$O(n^2)$時間の行列積検査アルゴリズムは, $n$次元ベクトル$r$を, 各成分$r_i \in \{0,1\}$をランダムに決めて生成し, $x=A(Br)$と$y=Cr$をそれぞれ計算し, $x=y$なら$A=B$, そうでないならば$A\neq B$と出力するものです.
ここでは $\mathrm{Pr}[ABr=Cr | AB\neq C] \leq 0.5$を示せば良いのですが, $D=AB-C$とすると(今は環で考えているので引き算が使えます), ある$i,j$が存在して$D_{ij}\neq 0$となるはずです. この$i,j$に対して

$\mathrm{Pr}[Dr=0 | D\neq 0]\leq \mathrm{Pr}[(Dr)_i=0 | D_{ij}\neq 0] = \mathrm{Pr}[D_{ij}r_j = -\sum_{k\neq j}D_{ik}r_k | D_{ij}\neq 0]\leq 0.5$

が成り立つので, 上の主張が示されたことになります. しかしここでの証明では$D=AB-C$を考えていたので, 代数系としては環であることを用いてます. では引き算が使えない半環だとどうなのでしょうか?

また, 行列積を$O(n^{2.807...})$時間で計算するかの Strassenのアルゴリズムでもやはり, 解をマージする部分で引き算を使っているので, 環のためのアルゴリズムになっています.

半環であっても実際に$A\cdot B$は愚直にやれば$O(n^3)$時間で計算できるので, $O(n^3)$時間で半環上の行列積や検査ができます. 一方で行列の入力に$\Omega(n^2)$時間は最低でもかかります. では$O(n^3)$より高速に, 例えば$O(n^{2.7})$時間とかで計算できないのでしょうか?

実は, 半環はおろか$(\min, +)$代数に対しては積の計算・検査は出来ないだろうと考えられていて,  計算複雑性理論においては任意の$\epsilon>0$に対して$O(n^{3-\epsilon})$時間で$(\min,+)$代数上の行列積の計算・検査はどちらも計算出来ないと考えられています.
そして実は$(\min,+)$代数上の行列積とグラフの全点対最短経路問題は似ている構造を持った問題であり, 一方が$\tilde{O}(n^{3-\epsilon})$時間で解けたらもう一方も同様の計算時間で解けるという結果が2010年に示されました ($\tilde{O}$は$\mathrm{poly}(\log n)$を無視したオーダーの意).




2017年6月11日日曜日

マイナー順序の推移性について

概要


 グラフマイナーの理論では、「$G$から部分グラフ$G'$をとり、その後$G'$のいくつかの辺を縮約することによって$H$が得られる」ならば、 $H$は$G$のマイナーであると定義されます。特にこのことを$H \preceq G$などと書き、順序関係$\preceq$はマイナー順序などと呼ばれ、世に知られるグラフマイナー定理は「$\preceq$はwell-quasi-orderである、即ち任意に有限グラフの無限列を持ってきたときに必ず$H \preceq G$なる$G,H$がその無限列に含まれる 」と主張しています。

 多くのグラフ理論では、マイナー順序を紹介する際に「マイナー順序は推移律を満たす」即ち「$X\preceq Y$ かつ $Y \preceq Z$ならば $X\preceq Z$である」ことは自明なものとして細かい説明は省かれています。しかしマイナー順序では「まず部分グラフをとり、その後縮約する」という順番があるので、この推移律の事実は「$Z$→部分グラフ→縮約→$Y$→部分グラフ→縮約→$X$」という流れを「$Z$→部分グラフ→縮約→$X$」という操作に変換できるということに他なりません。本当にそうなのでしょうか??

 本記事では、「自明」として片付けられているマイナー順序の推移律の簡単な証明っぽいものを与えることにします。

 まずグラフ$G$に対し「縮約→部分グラフ」という操作によってグラフ$H$が得られるとします。通常のマイナーでは「部分グラフ→縮約」を考えますので、これはマイナーの逆順序の操作になっています。今、マイナーの推移律を仮定せずに$H \preceq G$(注*) が示せたとしましょう。すると、「縮約→部分グラフ」という操作が「部分グラフ→縮約」という操作に書き換えることが出来ることになるので、
$Z$→部分グラフ→縮約→部分グラフ→縮約→$X$

$Z$→部分グラフ→部分グラフ→縮約→縮約→$X$
と書き換えられ、まとめると
$Z$→部分グラフ→縮約→$X$
となり、$X \preceq Z$が示せたことになります。

(注*) なお、マイナーの推移律を仮定するとこの事実は簡単に示せます。なぜならば$G$から縮約して得られるグラフを$G'$とし、$H$が$G'$の部分グラフになっているように$G'$をとってくると、$H \preceq G' \preceq G$となるので、推移律より明らかに$H \preceq G$が言えます。つまりこの事実は推移律と等価になっています。


証明っぽい説明


 というわけで、「縮約→部分グラフ」によって得られたグラフ$H$は「部分グラフ→縮約」によっても得られることを示しましょう。

・ケース1

まず、次の図の左上のグラフ$G$のように、部分グラフの領域(図の黄色領域)(注**)を、縮約する辺(赤い辺)が横切らない場合を考えます:



この図では、$G$の赤い辺を縮約することを考えており、「縮約→部分グラフ」という操作によって$H$が得られています (図の↓→に対応します)。

・黄色領域外の辺は、結局部分グラフをとるので縮約しようがしまいが関係ありません。
・図より明らかなように、この$H$は図の→↓の操作によっても得られます。

従ってこの場合は縮約と部分グラフの操作の順番を入れ替えても差し支えありません。

(注**)
$G$の黄色領域は、イメージとしては「$H$の頂点に含まれる or 寄与した頂点の全体」です。ちゃんと言うと、まず、$G$から縮約して得られたグラフ(図左下に対応)の頂点のうち、$H$に含まれるものを赤く塗ります。次にこのグラフの赤い頂点それぞれに対し、それが$G$から縮約によって得られたものならば縮約された$G$の辺に対し、その辺に接続する頂点を全て黄色く塗ります。また、$G$に含まれる$H$の頂点も黄色く塗ります。
このとき、黄色く塗られた頂点の全体が黄色い領域となります。「黄色い領域を横切る辺が存在しない」とは「どちらか一方のみが黄色い頂点であるような辺は存在しない」という意味です。

・ケース2

次の図のように、縮約する辺で黄色い領域を横切るようなものが存在する場合を考えます。



 この場合、$G$の黄色い領域を少し拡張し、またがるような縮約辺が存在しないようにすることによって所望の$H$を「部分グラフ→縮約」の操作によって得ることができます。
 具体的には、(注**)の操作によって$G$の頂点を黄色く塗った後、黄色い頂点を横切る赤い辺があったならば黄色領域外にあった頂点もまた黄色く塗る」という操作を可能な限り行います。そして、$G$から黄色い領域を部分グラフとしてもってきて、その後縮約すれば$H$を得ることができます。(この時、黄色領域内にあって$H$に寄与しないような辺は最初の部分グラフをとる操作の際に消しておきます)

まとめ


 マイナー順序の推移律を簡単に示したっぽいことをしました (直感的な説明ばかりであまり厳密な議論ではありませんが、、、)。特に面白い事実としては「縮約→部分グラフ」という操作と「部分グラフ→縮約」という操作は(書き換え可能という意味において)等価であるということだと思います。グラフ理論にはマイナーの他にも「位相的マイナー」「shallow minor」など、様々な亜種が知られていますが、多分似たような雰囲気で示せるのではないかと思います。

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)それぞれの逆操作を考えて帰納法を使えばいけます。