クリプキクローネ日記帳

ある種の音楽と数学とランニングはミニマルなところが似ていると思う。

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
  1. --/--/--(--) --:--:--|
  2. スポンサー広告

グラフ理論入門 基本とアルゴリズム[宮崎修一(著)] (森北出版)

これは素晴らしい本です。というかグラフ理論楽しすぎます。


グラフ理論は1冊ちゃんと読んだことがなかったので読んでみました。
数学的な厳密さより分かりやすさを重視しつつも、煙に巻かれた感が出ないように絶妙な難易度になっています。
ちょうど、自分で証明を考えるときの手元のノートと同じような粒度の証明なので読みやすいです。
最も、自分で考えるときはノートからいざ清書を起こすと細かいところで引っかかったりする訳ですが。

「木」の定義は「連結で閉路を含まないグラフ」というのは目から鱗でした。
今まで散々木を相手にしてきたのに、やつらはただの連結で閉路を含まないグラフだったんですね。
もう少し特別なものだと思っていました。

平面グラフとか平面的グラフの話はちょっと位相幾何みたいな気持ちですね。

2部グラフは単に対応表みたいなものをイメージしてしまいましたが、
木も2部グラフというのにやられたと思いました。
畳み込みニューラルネットで畳み込む層とフィルタの層なんかも該当しそうですね。

正則グラフは完全グラフと混同していました。
すべての頂点の次数が同じグラフを正則グラフといいます。
完全グラフはn-1正則グラフです。

最小全域木はハミルトン閉路の閉路じゃない版みたいなやつで、クラスカル、プリムなどのアルゴリズムがあります。
さらに、ターミナルさえ含めばすべての頂点を含まなくてもいい最小シュタイナー木問題というのもあります。

最短経路問題はずっと前に似たようなプログラムを書いたことがありますが、
そのときは規模も小さくて、とにかく動かすことが先決だったので、しらみつぶしにやってしまいました。
というわけでダイクストラのアルゴリズムに期待して読み始めましたが、これもなかなか力技ですね。
このダイクストラさんは、return文を最後に1つだけ置きたがるあのダイクストラさんでしょうか。

オイラー回路は全ての枝を1回ずつ通ることが大事であって、頂点は2度通ってもいいので閉路ではありません。
ハミルトンの影響もあってか、なんとなくオイラー閉路だと思ってました。
全ての頂点の次数が偶数であることがオイラー回路の必要十分条件であり、例の有名な町の地図が出てきます。
最初にオイラーに問題提起をした町の住民の名前が定理に残っていないのは寂しいですね。

ハミルトン閉路はNP完全です。NP困難とNP完全の説明がないですが、言葉だけ出てきます。
ここもすぐ分からなくなるので今調べ直しました。
任意のNP問題を帰着可能な問題のことをNP困難といい、その中でも自身がNPなものをNP完全といいます。
NP困難は決定可能ですらなくてもいいんですね。今更。

ハミルトン閉路を持つための必要条件であるディラックの定理とオーレの定理はいざというとき役立ちそうです。
いざというときっていつだっていう話はありますが。

ところでディラックの定理の証明に鳩の巣原理が出てきて思わず身構えました。
僕はいい加減なので、要素が有限であればあんまり考え込むところじゃないじゃんと思ってしまいます。
しかし軽くググってみただけで、鳩の素原理はなんで成り立つのかっていう話が出てきて、
「集合{1,...,m}から集合{1,...,n}への単射が存在すればm<=n」
という定理がペアノ算術から出てくるのでそれの対偶が鳩の素原理だというコメントがあって最高でした。
こういう人たちが数学を支えているんですね。
我々のベースは古典論理なので対偶もOKです。

頂点彩色問題は4色問題の恐ろしい影が忍び寄るのでびくびくしながら読みましたが、
5色問題なら意外と素直なアプローチで証明できることが分かりました。
といっても2色を入れ替えるところの議論はしっかりやると大変そうですが。

ところでこの頂点彩色問題でいきなり平面(的)グラフのみが対象になるのは
この問題がそもそも地図を起源としているので自然ではあるのですが、
今までの本の流れからするとちょっと不自然です。
それが正則グラフみたいに一瞬で判定できる条件であれば「ある条件で成り立つ定理なんだね」と思えますが、
平面的グラフの判定は難しそうなので、定理に前提条件がついた、というよりは
別のジャンルでわいわいやっているような感じがします。
平面的グラフの判定は本に書かれていませんが、軽くググってみると、
クラトフスキー(Kuratowski)の定理というのを使うようです。
この定理には「位相同型」という言葉が出てきますが、位相同型というのは
枝の真ん中にムリヤリ頂点を埋め込んだり外したりしても同じとみなす同型だそうです。
おもしろそうだけど調べ始めるとキリない感。

辺彩色問題も同様におもしろいんですが、オイラーさんの橋マップみたいな有名な逸話だとか
現代社会の応用とかが紹介されていないので印象に残りにくいですね。
ググってみた感じだと、グラフの分割とか、マッチングの分類とかにいいみたいですね。

重み付き有向グラフの最大流問題は、今まで最小化ばかり気にしていたので本の流れ的にパラダイムシフトでした。
すごく電流のにおいがします。
あと、プロジェクトマネジメントのPERT図に似てると思ってしまいましたが、
あっちは重みが工数でこっちは流れの太さなので、適用はちょっと難しいかもしれません。

フォード・ファルカーソン法は素直すぎてまんまじゃんと思ってしまいましたが、
その素直な方法でちゃんとできるということを示すのは意外と大変だし大事なことです。

最大フローが最小カットと等しいのも感覚的に当たり前だけど自明じゃない定理ですね。
最大フローが全体を見てて最小カットは局所的な観点なので、
こういう木と森を対応付けるような定理は役立ちそうですね。

最初カットはオブジェクト指向の結合度凝縮度の話に似ていて、
グラフを見ているだけでクラス分けにうんうん唸りそうになります。

マッチングは名前からして就活とか婚活とか気の滅入る連想をしてしまいますが、
そういう連想をしてしまうということは応用がそれだけ広いということですね。
ここでも極大と最大の概念が出てきます。
言葉の使い方が数学の中で統一されているおかげで、名前をみただけで定義がすぐ分かります。

ホールの定理は完全マッチングを持つかどうかという全体の条件が
隣接ノードの数という局所的な条件に落とし込まれていて、これは便利と思いましたが、
よく読むと任意の部分集合について調べないといけないので、そうでもないと分かりました。

ハンガリー法は逆ポーランド記法や中国人の剰余定理や中国語の部屋みたいな名前ですが、
最大マッチングを求めるアルゴリズムです。
フォード・ファルカーソン法で最大フローを求めるために、残余フローから増大道を探したのと同じで、
既存のマッチングに大して使っていない頂点から増大道を探す、という発想です。
計算時間はかなりかかりそうです。
交互道と増大道の説明のところは条件が少し抜けているのか、一瞬混乱しました。
増大道は閉路である必要がありそうです。

最大マッチングのサイズと最大フローの値が一致する定理はこの本の終盤の集大成ですね。
準備してきたものがつながる瞬間はいつも楽しいです。


ところで数学的帰納法でk以下を全て仮定するのはどこまで一般的なノウハウなんだっけと思いました。
二重帰納法とか、あるいはグラフの構造に関する順序を埋め込んで
その順序で帰納法をやったりするのもグラフ理論でよくやるんでしょうか。
そういう特別な帰納法も入門書で紹介したら帰納法がただ面倒なだけじゃなくて楽しいものだと広まると思います。
数理論理学ではそういうことをやりまくるわけですが、グラフ理論の方が間口が広そうなので。

あと、グラフ理論は深くやるとどの方向に向かうのかも気になります。
応用面でいろんな条件のグラフを考えるのはありそうですが、
あとは既知のグラフに対して最近はやりのGPUなんかの並列処理のアルゴリズム研究とか、
重みの概念を拡張したりするんでしょうか。
ニューラルネットの流行に乗っかってそっち方面はありそうですね。
個人的に気になるのは、確率が離散数学から導入しておいて密度関数みたいになっていったみたいに、
グラフ理論も離散のすっきりした姿からもっと扱いづらい姿になっていく方向もあるんでしょうか。
そうなるとしんどそうだなー。
でもグラフは計算機に密接に結びつきすぎているのでそっちにはいかないのかな。

なんにせよあらゆる方向にいきそうな分野なので、また別の本も読んでみたいと思います。
  1. 2017/03/20(月) 03:44:30|
  2. | トラックバック:0
  3. | コメント:0
<<リーダブルコード [D.Boswell, T.Foucher(著), 角征典(訳)] (オライリージャパン) | ホーム | メモリ技術が一番わかる(しくみ図解シリーズ) [石川憲二(著)] (技術評論社)>>

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

トラックバックURLはこちら
http://myumbrella.blog42.fc2.com/tb.php/358-66da4583
この記事にトラックバックする(FC2ブログユーザー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。