グラフ理論の一問に数十時間溶かした話

理学部情報科学科の3Sの演習授業に離散数学演習というものがあります.

離散数学演習は, 二週間に問題が13問程度出され, 学期を通して一人一回以上の発表と, 解いた問題(何問でも可)の解答の提出が課せられる授業です.

最後の方はグラフアルゴリズムの問題(特にマトロイドの問題)が増えますが, おおよそほとんどグラフ理論の問題と思って構いません. (但し, 離散数学の授業はグラフ理論よりグラフアルゴリズムよりなので, 離散数学演習ができても離散数学のテストは解けません.)

問題には難易度A,B,Cがあり, A は全員提出必須の比較的難しくない問題, B はそこそこ難しい問題からかなり厄介な問題まで揃っており, C は学期を通して一問だけ出される超難問(?)になっています.

偶然(?)僕は3S前の春休みに Graph Theory (Diestel) を8章まで読んでいたのもあって, 離散数学演習の問題は全解きチャレンジをしていたのですが, C 問題がどうしても解けなくて, 10日くらい他の課題を全てすっぽかして何十時間か溶かしましたが, 遂には解けませんでした.

その問題をここで公開すると20erに見られてしまってアレなので, 公開はしないのですが, その代わりに関連する定理を一つここで紹介して, 証明を記し, グラフ理論のノリを知っていただければいいなと思います. この記事の最後にグラフ理論の紹介をちょっとします. ("グラフ理論" はかなり分野として広くて, かなり多種多様な話題があります.)

 

定理の紹介

 

定理

ただ 1 通りに 3 枝彩色可能*1な 3 正則*2グラフ*3ハミルトニアン*4である.

(ただ一通りとは, 色の入れ替えを除いて, の意.)

 

証明

ただ一通りに3 枝彩色3 正則なグラフ  G = (V, E) *5が {1, 2, 3} の 3 色で枝彩色されているものとする.

                             c(e) = 1      ~~~      (e\in E)

と書くことで, e が 1 で塗られていることを表すことにする. (枝彩色を関数 c として表現しただけ)

いま,

                             C = c^{-1}(2) \cup c^{-1} (3)

とすると, C が G のハミルトン閉路を定めることを示す.

まず, C がいくつかの交わらない閉路からなる*6ことを示す. そのためには, 各頂点に対し, C に含まれる辺がちょうど 2 つ接続されていることを言えば十分である*7. これは各頂点にちょうど 3 辺が接続されていて(3正則の条件), 各頂点の周りに最大で 3 色しか塗られていないから(3枝彩色), 各頂点の周りには 1, 2, 3 が塗られた辺がただ一つずつ存在することになり, C にはそのうちちょうど 2 つ, 色2 と 色3 が塗られた辺が含まれるから従う.

次に, C が連結*8であることを背理法で示す. もしも連結でないなら, ある 2 頂点 [\tex: u, v \in G] があって, u から v へは道がない. このとき, C の辺で, u から歩き始めて到達できる範囲にあるものの集合を S とする. 次の関数 c' を定義する.

 c'(e) = \left\{\begin{matrix}c(e)~~~~~~~~~~~~~~~~~(e\notin S)\\2~~(e\in S, c(e)=3)\\3~~(e\in S, c(e)=2)\\\end{matrix}\right.

この関数が 3 枝彩色を定めることを示せば, G の仮定(Gは"一意に" 3 枝彩色可能)に反するので, C が連結であることが従う.  これも下にある図を見てもらえればほとんど明らかなので, 厳密に証明はしないことにする.

下が下のグラフG.

f:id:run_run_OJI:20191210171722p:plain

この G の緑, 赤の辺を取り出したものを C (左下の図)として, 色を入れ替えたものが右下の図である.

f:id:run_run_OJI:20191210171711p:plain=>f:id:run_run_OJI:20191210171704p:plain

 

 これで, C はただ一つの閉路からなり, G の各頂点は C の 2 つの辺に接続されていることがわかったが, このような C はハミルトン閉路に他ならない.

 

グラフ理論のノリ

グラフ理論は通常の(?)代数学*9 とは かなり様相が異なります.

冒頭で僕が呼んだと紹介した本 *10は学内 springer から落とせる(+駒場図書館, 経済学部図書館で借りられる) ので, 興味があれば開いてみて欲しいのですが, 本当に慣れるまでは読みにくくて仕方がありません. (慣れるとすごくいい本に思えてきます(?))

まず, 基本的に有限集合しか扱いません. そして演算がありません. しかし, かなり難しいです.

なんとなく雰囲気で説明すると, グラフ理論においては, よく次のような言い回し(証明の流れ)がされます.

"ある性質 P を満たす頂点 x が存在するならばその x を hoge すると証明ができる. もしそのような x が存在しないならば, 全ての頂点は P を満たさない. このとき , 性質 Q を満たす頂点 x が存在するので矛盾する. もし Q を満たす x が存在しないならば ... (以下繰り返し)"

この流れは気持ち悪いと言えば気持ち悪いのですが, この証明の順番はプログラミングの末尾呼び出し的になっていて, この順番にしないと"呼び出し"のネストが深くなりすぎて混乱してしまうので仕方がないのです.

グラフ理論の証明は 五色定理の証明を一度読んでみるとわかると思うのですが, 有限集合の元を一つずつ手で動かすような操作が非常に多く, さらに場合分けが大量に出てきます. (五色定理は場合分けがかなり少ない方.) 場合分けが多いと上のような変な証明法にしないと途中で混乱してしまうのです. そしてその場合分けがかなり尽くせているかどうかの判断が難しかったりします.

グラフ理論の分野

グラフの定義というものは非常にシンプル(脚注3)で, それゆえ(?), グラフ理論と言ってもかなり広い分野があります. また, グラフ理論はかなり新しい理論なので, 未だに未解決な問題がたくさんあります.

  • 組み合わせ(マッチング等々)
  • 平面グラフ
  • 彩色問題
  • フロー
  • 無限グラフ
  • ランダムグラフ
  • グラフマイナー
  • 代数的グラフ理論

説明しだすと大変なので割愛します. 数学に興味ある人はこの Springer の本がかなり頭おかしくて*11面白いのでペラペラめくってみるとテンション上がると思います.

link.springer.com

 

最後に

この記事は

adventar.org

の3日目のものとして書かれました. 遅くなって誠に申し訳ありません...

 

 

*1:各辺に対して三色のうち一色が与えられており, 各頂点に対して, その頂点に同じ色が塗られた辺が二つとして接続されていないような彩色を3彩色という. そのような彩色が存在することを3彩色可能という.

*2:各頂点に対し, その頂点に接続(その頂点を一端にもつこと)された辺がちょうど 3 つあるようなグラフ.

*3:頂点の集合Vと辺の集合 E があり, E の要素 e はVの 2 元集合になっているもの. e = {u, v} のとき, e は頂点 u, v の間にかかる辺と解釈する. 多重辺や, ループ辺は定義からない.

*4:ある頂点から出発して, 同じ頂点を二度と通ることなく, 全ての頂点を一回ずつ通って最初の頂点に帰ってくるような道が存在すること

*5:V は頂点集合, E は辺の集合

*6:閉路は同じ頂点を二度通ることなく最初の頂点に戻ってくるような道. ここでは, C はいくつかの閉路の辺集合の非交和(disjoint union)からなることをいう.

*7:このとき, 行き止まりがない一本道になっていることになるから, これは閉路に他ならない

*8:任意の2頂点間を辺の上を通って移動できること

*9:群, 環, 体, 圏

*10:ちなみにこの本は第5版なのですが, 第1版では未解決問題とされていた予想が定理に変わっていたりしてアツい. 日本語版もありますが, これは古い.

*11:多様体グラフ理論結びつけようとする人が正常であるはずがない. かなり難しい本なので読めないのですが, ペラペラめくるとこの人何考えてんだ!? とはなる.