グラフ理論ならこれを読め！

うちの会社では「グラフ理論を小学校のうちに学んでおかないから、そういうことになるんジャイ！(｀ω´)」とか冗談とも本気とも取れないような会話が平気で行き交う。それほどグラフ理論は大切な分野なのにプログラマには見過ごされがちだ。ただ、グラフ理論にはいい本が少ない。そこで、グラフ理論ならこれを読め！という本を紹介する。まずは、入門書としては、左の本がお勧め。

大学の教科書としてよく採用されているのが左の「最適化とグラフ理論　技術者のための高等数学」値段も手ごろだし、高校卒業程度の知識でも読めると思う。

「そんな入門書ではなくて、もっと詳しい本は無いか？」とid:Ozyさんに聞かれて私が勧めたのは、シュプリンガー・フェアラーク東京シリーズの「グラフ理論」　このシリーズは黄色い表紙とお馬さんのマークが目印だ。 これより詳しい本となると日本語で読めるものは発売されていないと思う。「グラフ同型判定問題」(asin:4572999988)とセットで持っていればこれ最強。あとは、計算幾何学の学問領域と重複してたりするので、そちらも勉強するといいだろう。

「計算幾何学入門」は安価だし、計算幾何学の入門書として手ごろだと思う。もう少し専門的な内容については「コンピュータ・ジオメトリ」がいいだろう。

あるときには、「組み合わせ最適化」にもグラフ理論が顔を出す。「組み合わせ最適化」の学問領域は、線形計画法,整数計画法,全点木と有向木,最短パス,ネットワークフロー,最小費用フロー,最大マッチング,重み付きマッチング,b-マッチングとTジョイン,マトロイド,ナップサック問題,ビンパッキング問題,多品種フローと辺素パス,ネットワーク設計問題,巡回セールスマン問題,施設配置問題etc..。これらはグラフ理論の応用例として勉強すると効果的だと思う。「組み合わせ最適化」について最も詳しく載っている本は、同じくシュプリンガー・フェアラーク東京シリーズの左の本だと思う。

あとは丸善の「組み合わせ最適化アルゴリズムの最新手法」も上の「組み合わせ最適化」と合わせて読みたい。

また、「組み合わせ最適化」の入門書としては、電子情報通信学会の「組み合わせ最適化の理論」(asin:4885520304)が値段的にもお手ごろだろう。

「近似アルゴリズム」は、高速に高品質の近似解を求める手法について解説されている。組み合わせアルゴリズム、LP(線形計画法)に基づくアルゴリズムが多数掲載されており、グラフ理論の実際的な応用としても価値が高い。R.M.Karp氏(1985年チューリング賞受賞)とL.Lovasz氏(1999年クヌース賞受賞)の両氏も絶賛。