基本的なグラフ理論の復習(Review of Elementary Graph Theory) この章は、基本的なグラフ理論を思い出させることを意図している。読者があらかじめグラフアルゴリズムの知識があるのなら、始めるにあたりこの章は十分であろう。もし読者がグラフアルゴリズムの知識がないのならば、 Cormen, Leiserson, RivestのIntroduction to Algorithms のようなもっと詳しいものを薦める。 グラフ抽象化(The Graph Abstraction) グラフは、多くの種類の問題を解くのに有効な数学的抽象化である。基本的には、グラフは頂点と辺から構成され、辺は二つの頂点を結ぶ。もっと正確には、 グラフ(graph)とは組(V,E)で表され、 Vは有限集合で、EはVの2項関係である。 Vは 頂点集合(vertex set) と呼ばれ、その要素を 頂