yasu's blog

グラフ理論入門

グラフ理論入門―C言語によるプログラムと応用問題 (原理がわかる工学選書)
佐藤 公男, 樋口 龍雄
日刊工業新聞社 (1999/04)

とってもいい本だと思う．「グラフ理論のなかで，便利なアルゴリズムには どのようなものがあるのか？」という疑問に答えてくれる． ほかのグラフ理論の本では便利なアルゴリズムが出てこず， 「便利なアルゴリズムが見つからなかったらグラフ理論自体研究する 意義がないではないか」とフラストレーション溜まったりするが， この本を読めば一気に解消する． 隣接行列 A の n 乗 (A^n) は，長さ n の歩道の総数を表す， など．つまり，隣接行列の積 A^3 の要素 A^3_2,3 は，ノード 2 から 3 への， 長さ 3 の歩道の数（経路数）を表す．ほかにも色々載っている．