『最短経路の本』15章まで

ページ数でいうともうすぐ折り返し。ここまでで、最短経路を求める Dijkstra のアルゴリズム、最小全域木を求める Prim, Kruskal のアルゴリズムと、聞き覚えのあるものが三つ出てきました。あとは枝刈りや近似解の話。それからマトロイドの定義が出てきました。面白そう。

ここまでの内容は、どれも考え方は難しいものではなかったと思います。厳密にアルゴリズムの正当性を証明しようとするとそこそこ面倒だったような気億はありますが。そういえば、木のいくつかの特徴付けがそれぞれ同値であることも本気で証明しようとすると大変だったような。でも、どれも難しいというよりはどちらかというと瑣末なところで苦労させられたような気がします。情報系の教科書にあるグラフの扱い方って、数学的には洗練されてなくて煩雑なイメージが拭えません。*1といっても、別にエレガントなやり方を知ってるわけではありませんが。

*1:この本がそうだというわけではなくて、一般的にそんな印象がある、ということです