基本的な定義

きちんと述べると、 (単純) グラフとは集合の組 \((V, E)\) であって、 \(V\) が任意の空でない有限の集合で、\(E\) が \(V\) の要素の組の集合であるものです。ここで \(V\) の要素は 頂点 (vertex)¹ またはノード (node) と呼ばれ、\(E\) の要素は辺 (edge) と呼ばれます。無向グラフ (unordered graph) では辺は順序の無い組、つまり大きさ 2 の集合です。これからは頂点 \(u\) と \(v\) の間の無向辺を \(\lbrace u, v\rbrace\) ではなく \(uv\) と書きます。また \(u\) から \(v\) へ向かう有向辺は \((u, v)\) ではなく \(u \rightarrow v\) と書きます。

標準的な記法に従って、\(V\) でグラフの頂点の数を、 \(E\) でグラフの辺の数を表すことにします (この記法が紛らわしいのは私も認めます)。この記法から、任意の無向グラフについて \(0 \leq E \leq \binom{V}{2}\) であり、任意の有向グラフについて \(0 \leq E \leq V(V - 1)\) と分かります。

辺 \(uv\) および \(u \rightarrow v\) について、頂点 \(u\) と \(v\) を端点 (endpoint) と呼びます。有向辺 \(u \rightarrow v\) の二つの端点については、\(u\) を尾 (tail)、\(v\) を頭 (head) と呼んで区別します。

グラフは組の集合として定義されるので、同じ端点を持つ無向辺および尾と頭が同じ有向辺を複数持つことはできません (有向グラフは辺 \(u \rightarrow v\) とその逆 \(v \rightarrow u\) を持てます)。同様に無向グラフの辺は二つの頂点の集合として定義されているので、端点が同じ辺は複数存在できません。このように端点が同じ辺および多重辺を持たないグラフのことを、単純 (simple) であると言います。単純でないグラフを多重グラフ (multigraph) と呼ぶことがあります。多重グラフの正式な定義は単純グラフと異なっているものの、単純なグラフに対するアルゴリズムの多くはほんの少し変更するだけで多重グラフに対するアルゴリズムに変形できるので、ここで正式な定義を説明する必要はないでしょう。

無向グラフの任意の辺 \(uv\) について、\(u\) は \(v\) の (および \(v\) は \(u\) の) 隣接点 (neighbor) である、あるいは \(u\) は \(v\) に (および \(v\) は \(u\) に) 隣接する (adjacent) と言います。\(v\) 頂点の次数 (degree) とは、その頂点に隣接する頂点の数です。有向グラフでは隣の頂点が二種類存在し、有向辺 \(u \rightarrow v\) について、 \(u\) を \(v\) の前者 (predecessor) あるいは入隣接点 (in-neighbor) と呼び、\(v\) を \(u\) の後者 (successor) あるいは出隣接点 (out-neighbor) と呼びます。有向グラフの頂点 \(v\) の入次数 (in-degree) とは \(v\) の前者の数であり、出次数 (out-degree) とは \(v\) の後者の数です。

グラフ \(G^{\prime} = (V^{\prime}, E^{\prime})\) が \(G = (V, E)\) の部分グラフ (subgraph) であるとは、\(V^{\prime} \subseteq V\) かつ \(E^{\prime} \subseteq E\) であることを言います。 \(G\) の真部分グラフ (proper subgraph) とは、\(G\) の部分グラフで \(G\) と等しくないものを言います。

無向グラフの歩道 (walk) とは、隣り合う頂点がグラフ上で隣接しているような頂点の列のことです。正式な定義ではありませんが、歩道を辺の列と考えることもできます。歩道の最初と最後の点が同じならば、その歩道は (閉じている (closed)) と言います。各頂点に多くとも一度しか通り抜けない歩道を路 (path) と呼びます。グラフ \(G\) の二つの頂点 \(u\) と \(v\) について、 \(u\) から始まって \(v\) に至る歩道 (つまりは路) が存在するとき、\(u\) から見て \(v\) は到達可能 (reachable) であると言います。全ての無向グラフは一つ以上の成分 (component) に分かれます。成分とは極大な連結部分グラフのことであり、二つの頂点が同じ成分に属することはその頂点の間に路があることと同値です²。

最初と最後の頂点が同じ路で一つ以上の辺を含むものを 閉路 (cycle) と呼びます。無向グラフが非巡回 (acyclic) であるとは、部分グラフとして閉路を含まないことを言います。非巡回グラフは森 (forest) とも呼ばれます。連結な非巡回グラフは 木 (tree) と呼びます。無向グラフ \(G\) の全域木 (spanning tree) とは、\(G\) の部分グラフの木であって \(G\) の頂点を全て含むものを言います。グラフが全域木を持つことはグラフが連結であることと同値です。グラフ \(G\) の全域森 (spanning forest) とは \(G\) の各成分に対する全域木を合わせたものです。

有向グラフに対しては少し異なる定義が必要です。有向歩道 (directed walk) とは、有向辺の列であって任意の辺の頭が次の辺の尾と同じものを言います。有向路 (directed path) とは同じ頂点を二度以上含まない有向歩道のことです。有向グラフ \(G\) において頂点 \(v\) が頂点 \(u\) から到達可能 (reachable) であるとは、\(G\) に \(u\) から \(v\) の有向歩道 (つまりは有向路) が存在することと同値です。有向グラフの全ての頂点が他の全ての頂点から到達可能であるとき、その有向グラフは強連結 (strongly connected) であると言います。有向グラフが非巡回 (acyclic) であるとは、有向閉路を持たないことを言います。有向非巡回グラフ (directed acyclic graph) は略して DAG と呼ばれます。

1. 頂点を表す英単語の複数系は "vertices" であり、その単数形が "vertex" です。同様に "martices" の単数形は "matrix"、"indices" の単数形は "index" です。イタリア語を使っていない限り、次の単語は存在しません: vertice, matrice, indice, appendice, helice, apice, vortice, radice, simplice, codice, directrice, dominatrice, Unice, Kleenice, Asterice, Obelice, Dogmatice, Getafice, Cacofonice, Vitalstatistice, Geriatrice, Jimi Hendrice! もしこの規則を覚えられないなら、常に "node" を使ってください。^[return]

2. 成分のことを連結成分 (connected component) と呼ぶことがありますが、これは冗長です。定義により成分は連結だからです。^[return]