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

理学部情報科学科の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:多様体グラフ理論結びつけようとする人が正常であるはずがない. かなり難しい本なので読めないのですが, ペラペラめくるとこの人何考えてんだ!? とはなる.

この記事はISer Advent Calender 2018の13日目として書かれたものです。昨日はtera_poonさんによるEMアルゴリズムについて勉強したのでまとめてみたでした。何もわからん。そして、今日の記事は完全なる穴埋めです。

群の例をひたすら挙げるだけの記事

情報数学(笑)の授業で、イメージがつかめん。具体例がわからん。ということを言っている人が居たので、ひたすら例をあげて、すっごーい!って言ってもらうために記事を書きます。でてくる用語の定義はwikiとかで調べてください。ところで一回書き終えて読み返したんですが、デスマス調が統一されてません。草。

集合hogeがfugaに関して群になる、とは、hogeという集合に対してfugaが群の演算になるという意味です。

 

巡回群

下の二種類しかなく、位数が同じ巡回群は全て同型になっている。アーベル群。

整数環\mathbb{Z}

加法に関して(無限)巡回群になっている。元一つから生成される自由群と自然に同型。

\mathbb{Z}/n\mathbb{Z}

mod nの世界。加法を3+4\equiv_{5}2 のように定義。正n角形を時計回りに回転して元の状態と重なるようにする操作が、操作の合成に関してなす群と同型。

(30^\circ回転と45^\circ回転の合成が75^\circ回転となる。360^\circ回転=0^\circ回転とみなす。)

特に位数が素数のもの(\mathbb{Z}/p\mathbb{Z})は自明な部分群しか持たない。実は体になる。後述。

対称群S_n 交代群A_n

ちょいと説明が面倒なので、Wiki か 何か他のサイトをみてください。permutation と言った方がわかりやすい人もいるのかもしれない。

ちなみに、A_4は正四面体の点を操作前後で全ていずれかの点に重なるように(形を保って)移すような操作の群(正多面体群)と一致。S_4は立方体もしくは正八面体の正多面体群に一致。A_5は正十二面体もしくは正二十面体の正多面体群に一致する。

ところで、立方体と正八面体の正多面体群が一致するのは、正八面体の各面の中心を結ぶと立方体ができ、正十二面体と正二十面体の正多面体群が一致するのは、これも同様に、正二十面体の面の中心を結ぶと正十二面体ができるからである。

点群

分子対称性 - Wikipedia この表にいっぱい載ってます。主に化学で分子の対象性を調べ、分類するのに使います。キラリティを調べることで、旋光性の有無に関することがわかったりする。しゅごい。wikiの下の方のフラーレンとがおもしろそう。

二面体群Dn

二面体群。正n角形を巡回群と似たように回転させる操作がなす群。ただし、裏返すことが許される。位数は2n。\frac{2\pi}{n}回転する操作を\sigma、裏返す操作を\tauと書くと、群は\{ e, \sigma, \sigma^2, \cdots, \sigma^{n-1}, \tau, \tau\sigma, \tau\sigma^2, \cdots, \tau\sigma^{n-1}\} で、\tau\sigma=\sigma^{-1}\tauが成り立つ。よってアーベル群ではない。群の例として使いやすくて個人的に好き。D_3S_3に一致。

(ただし机上に書かれた決まった線で常に裏返すことにしている。また、\tau\sigma^2と書かれているときは、二回\frac{2\pi}{n}回転をしてから裏返すことを表す。(操作とは実は写像のことなので、右から順に操作は行われるイメージでいい。)あんまり気にする必要はない。)(最も単純なアーベルでない群として知られる。)

水分子の点群C_{2v}

水分子を、操作の前後で見た目が変わらないように動かす操作の群。水分子をサクランボのように紙に書いたとき、

  • 何もしない(E)
  • 紙を裏返す(回転C_2)
  • 紙に立てた鏡で写す(右と左が入れ替わる\sigma_{v_{xz}})
  • 紙に平行な鏡で写す(手前と奥が入れ替わる\sigma_{v_{yz}})

これは実は長方形(正方形でない)を回転・裏返しで重なるようにする群(クラインの4群)に同型。位数は4。

アンモニア分子の点群C_{3v}

これも回転・鏡映で移すことを考えると、鏡の置き方が3通りで、\frac{2\pi}{3}回転軸がある。S_3に同型。位数は6。

代数的な話

線型空間

お気付きでしたでしょうか......ベクトル空間が足し算でアーベル群をなしていることに......(係数体\mathbb{K}が有限体でないなら無限群)

行列

そりゃ行列もアーベル群ですよね......

GL(n, \mathbb{K})

行列式が0でないn次正方行列のなす乗法群。アーベル群ではない。O(n), SO(n)などの部分群を持つ。巡回群はこの部分群だったりする。

(\mathbb{Z}/n\mathbb{Z})^{\times}

1からn-1までの自然数のうち、nと互いに素なものの集合。積に関して群になる。

ex) 4\cdot7\equiv_{9}1 みたいな演算ができる。

nが素数pであるなら、(\mathbb{Z}/n\mathbb{Z})^{\times} = \{1, \cdots, p-1\}これは標数pの素体(特に有限体)になる。(\because ユークリッドの互除法)(例: mod 7 では、5が3の積に関する逆元になる。(5\cdot3\equiv_{7}1)) 

四元数

四元数 - Wikipedia

なんか、コンピュータグラフィックスで使えるらしいって書いてますね。知らんけど。

Aut(自己同型群)

ある集合に対して何らかの代数構造があって、その自己同型写像を集めた集合は往往にして合成に関して群になります。理由は簡単で、自己同型写像うしの合成は自己同型で、id(恒等写像)は自己同型写像で合成に関して単位元になり、自己同型ならば逆写像は存在して、これが群の逆元になるからです。Galois理論とかでも使います。

そのほか

\mathbb{R}\mathbb{Q}\mathbb{C}ルービックキューブ群論、自由群、自由アーベル群、リー群、ホモトピー群

最後に

適当極まりない記事で申し訳ないという気持ちでいっぱいです。

明日の記事は gif011010701 さんの偏愛的音楽入門です。全部埋まったようですね、わーい!

トポロジー


はじめまして。

2年生の人です。Twitter (@_ariHira)をやっています。理情で Advent Calender がたったので、せっかくなので文章を書きます。が、ブログ書いたことがないのでむっちゃドキドキしてきました...

位相幾何学

位相幾何学とは

せっかくなので何か書こうと思い立ったのはいいのですが、コンピュータなんもわからんので、数学の位相幾何学について書きます。

位相幾何学(=トポロジー)というのは、2Aの数学科の必修『集合と位相』で習う位相というものについて詳しく調べる幾何の分野です。よくいう、コーヒーカップとトーラス体が位相同型だ、とかいうやつで、ぐにゃぐにゃ曲げると同じ形になるものは同じものとして考えてしまいます。 (ただし穴を作ったり潰したりちぎったりすることを許さない変形に限る) 

f:id:run_run_OJI:20181203020836g:plain

wikipediaトポロジーのページにある gif。
対象と射

位相幾何学は幾何の分野と言いましたが、数学というものは通常、最初に"対象"と"射" (代数だと主に準同型写像と呼ばれるもの) を定義します。この場合、対象は位相空間で、射は連続写像と呼ばれるものになります。ここでは位相空間の例として、円や球、トーラス、などをあげます。だいたい何かの図形と思っておけばいいです。(ここであげる例は全て\mathbb{R}^3の部分空間に限定して、厳密な定義を避けます。)

連続写像の中でも、全単射で、さらに逆写像も連続になっているものを、特に同相写像と呼びます。そして、同相写像で結ばれる2つの位相空間を、同相(位相同型)であるといいます。

この同相の定義が、最初に述べた、ぐにゃぐにゃ変形すると同じになることと対応しています。

EX) 円と楕円は同相

f:id:run_run_OJI:20181203024202p:plain

EX) アニュラス(左)とシリンダー(右)は同相 (シリンダーは図の曲面のことです)

f:id:run_run_OJI:20181203030806p:plain

(アニュラスは極座標表示, シリンダーは高さと角度の組で表示)

位相幾何学の目標

位相幾何学の目標は、位相空間を同相か同相でないかによって分類することにあります。

位相空間XY同相であることを証明するためには、XYの間に同相写像が存在することを証明or構成すればいいのですが、位相空間XY同相でないことを証明することは悪魔の証明的に難しくなります。(←ほんまか)

位相不変量

この同相でないことの証明には、位相不変量と言うものが大きな役割を果たします。位相不変量とは、ある位相空間を一つとってきたときに、それに対して決まる数や性質、さらには群などであって、同相な他の位相空間に対しても同じ値になるものを指します。

位相不変量の例

同相ならば位相不変量が等しいという事実は、逆手に取ると、位相不変量が異なるならば同相でないという証拠になるのです。

EX) \mathbb{R}\mathbb{R}^2は同相でない。もし同相であるならば\mathbb{R}から一点を除いた (-\infty, 0) \cup (0, \infty) と、\mathbb{R}^2 からある一点を除いたものが同相にならなければならないのだが、前者は連結でない(連結成分2つ)のに対して、 \mathbb{R}^2からどの一点を除いても連結になる(連結成分1つ)ので、これらは同相になり得ないので矛盾する。

同じように \mathbb{R} と 円周  S^{1} が同相でないことを証明できます。

球面 S^2 とトーラス T^2

この区別は難しい

球面 S^2トーラス T^2 は明らかに同相ではなさそうに見えますが、この証明は実はかなり難しくなります。これをEuler 標数という位相不変量を使って同相でないことを証明してみましょう。

Euler 標数

点と線分と三角形のみを使って、表現される図形を考えます。

例えば、3つの頂点と3本の線分を使えば、(中抜きの)三角形が作れますし、4つの点と6本の線分と4つの面を使えば正四面体ができます。

また、4つの頂点と4本の線分で(中抜きの)四角形が作れますが、これは中抜きの三角形と同相です。

実は、このようにしてできる(カクカクした)図形は、同相ならば、オイラー標数

       E = (頂点の数)-(辺の数)+(面の数)

が等しくなるという定理があります。(証明はかなり難しい)

中学校(?)で習うオイラーの多面体定理 ( オイラーの多面体定理の証明 | 高校数学の美しい物語 ) というのは実はこの特別な場合です。

カクカクのトーラス

さて、点と辺と三角形だけを使って、トーラスを作りましょう。

f:id:run_run_OJI:20181204222943p:plain



できましたね。

(これ断面が三角形なんですがわかりますかね......)

  

頑張って数えると、点が9、辺が27、面が18になるので(ここで、辺18面9ではない) Euler 標数は 0 ということになります。

(ただしここでは線と面は少し特殊な数え方をしています。すなわち、上図に書かれている線は(太線でないものも含め)全て辺として数え、辺で分割される二次元領域を全て面と呼んでいます。同じように、下の四角形(中は詰まっている)は一つの平面に乗っていますが、線5本、面2つとして数えています。ちなみに下の二つ同相で確かに  4-5+2=3-3+1=1 になっていますね。)

f:id:run_run_OJI:20181204220942p:plainf:id:run_run_OJI:20181204221405p:plain

また、四面体の Euler 標数は 2 です。

このカクカクしたトーラス(上図)とツルツルのトーラス(T^2)は同相で、球面(S^2)と四面体は同相になっています。それゆえ、もし  S^2T^2 が同相ならば、カクカクのトーラスと四面体も同相ということになりますが、これらのEuler 標数は異なるので、矛盾します。すなわち、 S^2T^2 は同相ではありません。やったね!

 

興味が湧いたらこんなものもみてみてください。

https://en.wikipedia.org/wiki/Hairy_ball_theorem

球面には必ずつむじがどこかに存在するという定理です。これも位相幾何学で証明ができます。すごい!たのしい!

補足

この投稿は、ISer Advent Calender 2018 の4日目として書かれました。 昨日の記事はHelloRuskさんの

helllrrrk.hatenablog.com

 でした。