第 10 章 有向グラフと半順序
有向グラフ (directed graph, digraph) を使うと、オブジェクトの間に存在する関係の表現や、関係をたどってオブジェクトの間を移動する経路の発見が容易になる。有向グラフは点 (または円) と、それらをつなぐ矢印付きの線を使って図 \(\text{10.1}\) のように図示される場合が多い。この図における点を頂点 (vertex) と呼び、線を有向辺 (directed edge) と呼ぶ。例えば図 \(\text{10.1}\) の有向グラフは \(4\) 個の頂点と \(6\) 個の辺を持つ。頂点はノード (node) とも呼ばれ、有向辺は単に辺 (edge) とも呼ばれる。
有向グラフは情報科学の様々な場所で姿を現す。例えば図 \(\text{10.2}\) の有向グラフは通信ネットワーク (第 11 章) の一種を表す。\(3\) 個の「in」頂点がネットワークからパケットを受け取り、\(3\) 個の「out」頂点にパケットが送信される。中央の \(6\) 個の頂点はスイッチを表し、\(16\) 個の辺はルーターを通り抜けるパケットの経路を表す。
情報科学で有向グラフが使われる別の例として、ワールドワイドウェブにおけるハイパーリンク構造がある。ウェブページが有向グラフの頂点 \(x_{1}\), \(\ldots\), \(x_{n}\) だとすれば、特定のページから別のページに向かうハイパーリンクは有向辺で表現できる。ハイパーリンク構造を表す有向グラフの例を図 \(\text{10.3}\) に示す ── もちろん、実際のワールドワイドウェブを表す有向グラフは数十億 (おそらくは数兆) 個の頂点を持つ巨大なものになる。一見すると、このグラフは大きいだけで興味深い点はないと思うかもしれない。しかし 1995 年、当時 Stanford 大学の学生だった Larry Page と Sergey Brin の二人は、このグラフが持つ構造が検索エンジンで非常に有用なことに気が付き、後にビリオネアとなった。そのため、グラフ理論はよく学んでおくべきだ。何が起こるか分からない！
有向グラフ (directed graph, digraph) \(G\) は、頂点集合 (vertex set) と呼ばれる非空集合 \(V(G)\) と、辺集合 (edge set) と呼ばれる集合 \(E(G)\) からなる。\(V(G)\) の要素を頂点 (vertex) と呼び、\(E(G)\) の要素を有向辺 (directed edge) と呼ぶ。頂点はノード (node) とも呼ばれ、有向辺は矢印 (arrow) や辺 (edge) とも呼ばれる。図 \(\text{10.4}\) に示すように、有向グラフの辺は始点 (tail) と呼ばれる頂点 \(u\) から終点 (head) と呼ばれる頂点 \(v\) に向かう。この辺は例えば順序付き組 \((u, v)\) で表現できる。始点 \(u\) と終点 \(v\) を持つ辺は \(\langle u \to v \rangle\) または \(\langle v \leftarrow u \rangle\) と表記され、辺 \(e\) の始点と終点はそれぞれ \(\operatorname{tail}(e)\), \(\operatorname{head}(e)\) と表記される。
この定義は新しい言葉を使っているだけで、新しい概念があるわけではない。形式的には、有向グラフ \(G\) は集合 \(V = V(G)\) 上の二項関係と等価である ── 始域と終域が \(V\) に等しい二項関係を有向グラフと呼んでいるに過ぎない。さらに、二項関係 \(G\) の「矢印」は以前からグラフと呼んでいた。例えば \([1..12]\) に属する整数の整除性は有向グラフとして図 \(\text{10.5}\) のように図示できる。
