10.4 歩道関係

目次

有向グラフに関する基本的な質問として「特定の頂点から別の頂点に到達できるか？」がある。任意の有向グラフ \(G\) に対して、この関係を \(V(G)\) 上の二項関係 \(G^{\ast}\) として定義する:

\[ u\ G^{\ast}\ v \ \ \overset{\text{def}}{\longleftrightarrow}\ \ u \text{ から } v \text{ への歩道が } G \text{ に存在する} \tag{10.6}\]

この二項関係を頂点集合 \(V(G)\) 上の歩道関係 (walk relation) と呼ぶ。同様に、正歩道関係 (positive walk relation) \(G^{+}\) も次のように定める:

\[ u\ G^{+}\ v \ \ \overset{\text{def}}{\longleftrightarrow}\ \ u \text{ から } v \text{ への長さが正の歩道が } G \text{ に存在する} \tag{10.7}\]

また、以降で利用する用語を二つ定めておく:

定義 10.4.1

有向グラフの頂点 \(v\) から頂点 \(w\) への歩道が存在するとき、\(w\) は \(v\) から到達可能 (reachable) と言う。また、\(v\) は \(w\) に接続 (connected) とも言う。

10.4.1 関係の合成

関数と同様に、二項関係を合成する単純な方法が存在する。二項関係の合成は歩道・路・有向グラフに関する新しい視点を提供する。

定義 10.4.2[二項関係の合成]

\(R\colon B \to C\) と \(S\colon A \to B\) を二項関係とする。 このとき、次の規則で定義される二項関係 \((R \circ S) \colon A \to C\) を \(R\) と \(S\) の合成 (composition) と呼ぶ:

\[ a\ (R \circ S)\ c \ \ \overset{\text{def}}{\longleftrightarrow}\ \ \exists b \in B.\ (a \mathrel{S} b) \ \operatorname{\text{\footnotesize AND}} \ (b \mathrel{R} c) \tag{10.8}\]

この定義で \(R\) と \(S\) を関数とした特殊ケースは定義 4.3.1 で示した関数の合成の定義と矛盾しない1。

有向グラフは頂点集合上の二項関係であることを思い出せば、有向グラフ \(G\) を自身と合成できると分かる。\(n\) 個の \(G\) を合成した結果を \(G^{n}\) と表記すると定めると、容易に示せる (問題 10.11) ように \(G^{n}\) は長さ \(n\) の歩道関係 (length-\(n\) walk relation) となる。つまり、次の関係が成り立つ:

\[ a\ G^{n}\ b \ \ \longleftrightarrow \ \ a \text{ から } b \text{ への長さ } n \text{ の歩道が } G \text{ に存在する} \]

慣習的に \(G^{0}\) は頂点集合上の恒等関係2 \(\text{Id}_{V(G)}\) と定義されるので、この関係は \(n = 0\) でも成り立つ。 歩道の存在と路の存在は同値であり、任意の路の長さは \(\left| V(G) \right| - 1\) である事実から、次の関係3が分かる:

\[ G^{\ast} = G^{0} \cup G^{1} \cup G^{2} \cup \cdots \cup G^{\left| V(G) \right| - 1} = (G \cup G^{0})^{\left| V(G) \right| - 1} \tag{10.9}\]

[訳注: \(G^{\ast}\) は \(G\) の反射推移閉包 (reflexive transitive closure) と呼ばれ、任意の二項関係 \(R\) に対して \(R^{\ast} ::= R^{0} \cup R^{1} \cup \cdots \cup R^{n} \cup \cdots\) と定義される。] 最後の等式からは、高速冪乗の手法を使えば \(G^{\ast}\) を求めるのに必要な関係の合成の計算回数が \(n - 1\) 回ではなく \(\log n\) 回で済むと分かる。

  1. 定義式 \(\text{(10.8)}\) における \(R\) と \(S\) の順序が書き間違いでない理由もここにある。関数 \(f\) に関数 \(g\) を合成した結果に \(x\) を入力したときの値は \(f(g(x))\) なので、合成 \(f \circ g\) は \(g\) を最初に適用しなければならない。 ↩︎

  2. 集合 \(A\) に対して次の規則で定義される二項関係 \(\text{Id}_{A}\) を、\(A\) 上の恒等関係 (identity relation) と呼ぶ:

    \[a\ \text{Id}_{A}\ b \ \ \overset{\text{def}}{\longleftrightarrow}\ \ a = b\]

    ここで \(a, b \in A\) である。 ↩︎

  3. 等式 \(\text{(10.9)}\) には害のない記号の濫用がある: 正確には

    \[\operatorname{graph}(G^{\ast}) =\operatorname{graph}(G^{0}) \cup \operatorname{graph}(G^{1}) \cup \cdots \]

    と書く必要がある。この記法は今後も利用される。 ↩︎

広告