最短経路の本

「最短経路の本」R．ブランデンベルク P．グリッツマン シュプリンガー・ジャパン株式会社

を読んだ。

基本的にはグラフ理論を現実的な側面から解説している本。レナという女の子が、コンピュータと話をしながら、グラフ理論やアルゴリズムについて学んでいくというストーリー。

最短経路
アルゴリズムの時間計算
最小全域木
オイラーグラフ
マッチング問題
中国人郵便配達問題
ハミルトングラフ
巡回セールスマン問題

といった内容を、図などを交えて、対話形式の話を読みながら学べる。
教科書のような作りではなく、章が比較的短くまとめられていて、しかも一つ一つの章の内容も難しすぎないため、非常に読みやすい。しかもいつの間にか一通りのグラフ理論の概要は理解できるようになっている（と思われる。）

グラフ理論ばかりではなく、チューリングや、オイラーなどの人物の逸話なども載っていて飽きない作りになっているし、何よりそれによって頭が疲れないようになっている。頭を使って考える部分と、少し休んで読める部分が交互にあるため、また次の章を読むときにも、エネルギーが残っている。

ただし、一つ一つ理解するには、それなりに時間がかかる部分もある。たださっと読んだだけでは理解できない部分もあり、頭を使って読み進めないと、次の瞬間には何を言っているのかわからなくなるようなことも多い。そういう意味では、教科書を進めるときのように、1ページ1ページ確実に理解して前に進むべき本だと思う。

主人公のレナは、数学が苦手な女の子の役割だが、少なくとも数学がそれなりに得意だった僕よりもよっぽど数学ができるという点はちょっと・・・と思うところはある。なので、まったく数学が苦手な人にはちょっと難しいかもしれない個所もある。（数学的に難しいというより、その場で自分で論理的に考えて、そこで言われていることを理解する力が必要になる。）

この本を読んだ後に、グラフ理論の教科書的なものを読んでいるが、この本を読んだ後で、教科書を読むのは非常に効率が良いと思う。教科書は数学的に正確な言葉で書かれていたりして、概要をつかむには、一つ一つを理解するのに時間がかかる。一方で概要が分かっていると、教科書はその概要を数学的に正しく書くとこうなるという説明として読めるので、頭の中のイメージをすぐにその式につなげることができる。式からイメージをつくるより、今あるイメージが式の中でどう表現されているかを考えるほうが楽だと思うし、この本はよい入門書になると思う。

最後の3章（全体の1割程度）は僕には難しすぎて理解できなかった。というより、個人的にはちょっと説明が雑すぎるんじゃないだろうかと思うところもある。おそらくこれですべてを理解してもらおうと思っていないというところはあると思うが、理解できない言葉（「1-木」ってなに？）ができたりして、説明されているようだけれど、理解できない。というわけで、最後の3章は読んでいない。

全体として、現実的な問題を解決するということを題材にして、説明されているので、その意味もはっきりしていて目的をもって読める。グラフ理論がどんなものか知りたい人、アルゴリズムに興味がある人は読んで損はない本だと思う。