基本的なグラフ理論の復習 - boostjp

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