グラフ

グラフとは

グラフ(graph)とは、「対象の集合とそれらのつながり(関係)の集合を表すデータ構造」をいう。グラフにおける「対象」とは頂点またはノード(node)と呼ばれ、一般的に円で表す。「つながり」は頂点と頂点の関係をいい、辺やエッジ(edge)と呼ばれ、一般的に線または矢印で表す。グラフの例を示すと下図のようなものである。また、辺には向きや重み(値)をつけて使われることがある。

グラフの例

グラフは、辺によって以下のように分類される。

名前特徴
無向グラフ辺に向きがないグラフ
有向グラフ辺に向きがあるグラフ
重み付き無向グラフ辺に重み(値)があり、向きがないグラフ
重み付き有向グラフ辺に重み(値)があり、向きがないグラフ

グラフの表記

頂点の集合が \(V\)、辺の集合が \(E\) であるようなグラフを \(G = (V,E)\) と表記する。また、 \(G = (V,E)\) における頂点と辺の数をそれぞれ \(|V|\)、\(|E|\) と表す。2つの頂点 \(u,v\) を結ぶ辺を \(e = (u,v)\) と表す。無向グラフの場合、\((u,v)\) と \((v,u)\) は同じ辺を表す。重み付きグラフの辺 \((v,u)\) の重みを \(w(v,u)\) と表す。無向グラフに辺 \(u,v\) があるとき、頂点 \(u\) と頂点 \(v\) は「隣接している」という。隣接している頂点の列 \(v_0,v_1,...,v_k \hspace{4px} (i=1,2,...,k \hspace{4px} について辺 \hspace{4px} (v_{i-1},v_i) \hspace{4px} が存在する)\) をパスという。始点と終点が同じようなパスを「閉路」という。閉路のない有向グラフをDAG(Directed Acyclic Graph)という。下図の(a)は閉路がないためDAGになり、(b)は閉路があるためDAGにならない。

DAGとDAGにならないグラフの例

頂点 \(u\) につながっている辺の数を頂点 \(u\) の次数(degree)という。有向グラフにおいては、頂点 \(u\) に入る辺の数を頂点 \(u\) の入次数、頂点 \(u\) から出る辺の数を頂点 \(u\) の出次数という。グラフ \(G = (V,E)\) の任意の \(2\) つの頂点 \(u,v\) に対して、 \(u\) から \(v\) へパスが存在するとき、 \(G\) を連結なグラフという。 \(2\) つのグラフ \(G\) と \(G'\) について、 \(G'\) の頂点集合と辺集合の両方が \(G\) の頂点集合と辺集合の部分集合になっているとき、 \(G'\) は \(G\) の部分グラフという。

【出典】
渡部有隆, Ozy, 秋葉拓哉他「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」264〜268頁