10.6 半順序
「直接的な依存関係」という二項関係を有向グラフで表すと、情報科学者がグラフを理解するために用いるツールを使って衣服を身に着ける順序という退屈な問題を議論できる。だからどうしたと思ったかもしれない。しかし、有向グラフに関して言えることは他にもある。本章の冒頭で言及した次の事実は重要なので繰り返しておく: 任意の有向グラフは、始域と終域が同じ二項関係と形式的に同一である。これは、始域と終域が同じ任意の二項関係を有向グラフに変換できることを意味する！ 「二項関係の辺」や「有向グラフによる集合の像」を考えるのは奇妙に思えるかもしれないが、こういった概念を考えると様々な異なる種類の二項関係の間にある重要な関係が明らかになる。例えば、衣服を身に着けるときの直接的な依存関係に Dilworth の補題 (補題 10.5.12) を適用できたのは、この関係のグラフが DAG だったからである。
では、二項関係が DAG だと言えるのはどんなときだろうか？ 二項関係が DAG だと分かったとき、正確に何が結論できるだろうか？ 本節では二項関係に関する性質を抽象的に定義して、その性質を使って二項関係のクラスをいくつか定義する。特に、節題である半順序を説明する。
10.6.1 DAG における歩道関係の性質
まず、全ての有向グラフが持つ性質を考えよう。\(u\) から \(v\) への歩道と \(v\) から \(w\) への歩道を結合すると \(u\) から \(w\) への歩道が得られる。ここから、歩道関係と正歩道関係の両方が推移性 (transitivity) を持つと分かる:
集合 \(A\) 上の二項関係 \(R\) が推移性 (transitivity) を持つとは、次の関係が任意の \(a, b, c \in A\) で成り立つことを言う:
この言葉を使うと次の事実が言える:
任意の有向グラフ \(G\) に対して、歩道関係 \(G^{+}\) と正歩道関係 \(G^{\ast}\) は推移性を持つ。
また、任意の頂点からそれ自身への長さ \(0\) の歩道は常に存在するので、歩道関係は反射性 (reflexivity) も持つ:
集合 \(A\) 上の二項関係 \(R\) が反射性 (reflexivity) を持つとは、次の関係が任意の \(a \in A\) で成り立つことを言う:
次の事実が言える:
任意の有向グラフ \(G\) に対して、歩道関係 \(G^{\ast}\) は反射性を持つ。
「有向グラフが DAG」と「長さが正の閉歩道が存在しない」は同値である。閉歩道に属する任意の頂点は閉歩道の始点かつ終点になれるので、これら二つの条件は「始点と終点が同じ長さが正の歩道が存在しない」とも同値だと分かる。これは \(D\) が DAG のとき正歩道関係 \(D^{+}\) が非反射性 (irreflexivity) という二項関係に関する性質を持つことを意味する:
集合 \(A\) 上の二項関係 \(R\) が非反射性 (irreflexivity) を持つとは、次の関係が任意の \(a \in A\) で成り立つことを言う:
先ほど説明したのは次の事実である:
10.6.2 狭義半順序
これから二項関係の興味深いクラスをいくつか定義していく。
推移性と非反射性を持つ二項関係を狭義半順序 (strict partial order) と呼ぶ。
補題 10.6.6 からは狭義半順序と DAG の間にある単純な関係が分かる:
狭義半順序は有向グラフと何の関連もない様々な場面で姿を現す。例えば、実数に関する「未満」の関係 \(<\) は狭義半順序である:
-
推移性: 任意の実数 \(x\), \(y\), \(z\) に対して \(x < y\) かつ \(y < z\) なら \(x < z\) が成り立つ。
-
非反射性: \(x < x\) を満たす実数 \(x\) は存在しない。
また、集合に関する真の包含関係 \(\subsetneq\) も狭義半順序である:
-
推移性: 任意の集合 \(A\), \(B\), \(C\) に対して \(A \subsetneq B\) かつ \(B \subsetneq C\) なら \(A \subsetneq C\) が成り立つ。
-
非反射性: \(A \subsetneq A\) を満たす集合 \(A\) は存在しない。
もし有向グラフに \(u\) から \(v\) への歩道と \(v\) から \(u\) への歩道が存在するなら、両者を連結することで閉歩道が得られる。よって \(DAG\) には互いに到達可能な二頂点が存在しない。この性質は二項関係の言葉で非対称性 (asymmetry) と呼ばれる:
集合 \(A\) 上の二項関係 \(R\) が非対称性 (asymmetry) を持つとは、次の関係が任意の \(a, b \in A\) で成り立つことを言う:
この言葉を使うと、DAG は「非対称性を持つ有向グラフ」とも特徴付けられる:
系 10.6.10 と定理 10.6.8 を合わせると次の系1を得る:
異なる DAG の正歩道関係が同じ狭義半順序になる場合がある。この事実から「特定の狭義半順序を決定する、辺の個数が最小の DAG は何か？」という疑問が自然に生まれる。この意味で最小の DAG は有限の狭義半順序に対しては一意であり、簡単に見つけられる (問題 10.31)。
10.6.3 弱半順序
狭義半順序である「未満」の関係 \(<\) と同程度によく使われる関係として「以下」の関係 \(\leq\) がある。また、通常の包含関係 \(\subseteq\) は真の包含関係 \(\subsetneq\) より使われる場面が多い。こういった関係は弱半順序 (weak partial order) の例である。弱半順序は「全ての要素は自身と関係する」という条件を加えた狭義半順序を意味する。この条件を表明するには、非対称性の定義を自身に適用されないように緩和する必要がある。この緩和された性質は反対称性 (antisymmetry) と呼ばれる:
集合 \(A\) 上の二項関係 \(R\) が反対称性 (antisymmetry) を持つとは、任意の \(a, b \in A\) が \(a \neq b\) を満たすとき次の関係が成り立つことを言う:
この言葉を使えば、狭義半順序の定義と同様の弱半順序の公理的定義を示せる:
推移性、反射性、反対称性を持つ二項関係を弱半順序と呼ぶ。
次の補題は弱半順序の異なる特徴付けであり、この定義から直ちに従う:
集合 \(A\) 上の二項関係 \(R\) が弱半順序であるのは、ある \(A\) 上の狭義半順序 \(S\) が存在して全ての \(a, b \in A\) で次の関係が成り立つとき、かつそのときに限る:
長さ \(0\) の歩道は始点と終点が同じなので、この補題と定理 10.6.8 から次の系が分かる:
一般に弱半順序は \(R\) などの文字記号ではなく \(\preceq\) や \(\sqsubseteq\) などの記号で表される場合が多い2。同様に、狭義半順序を表す記号としては一般に \(\prec\) や \(\sqsubset\) が使われる。
半順序の例を二つ示す:
集合族 \(A\) に対して \(a \mathrel{R} b \ \ \overset{\text{def}}{\longleftrightarrow}\ \ a \subsetneq b\) と定義される二項関係 \(R\) は狭義半順序である。
整除関係は非負整数全体の集合上の弱半順序である。
定義の理解の確認として、任意の集合 \(D\) に対する次の二項関係が空虚な半順序である事実を納得しておくとよい: 恒等関係 \(\text{Id}_{D}\) は弱半順序であり、空関係 (empty relation, 矢印を一つも持たない関係) は狭義半順序である。
なお、本書が弱半順序と呼ぶ概念を「半順序」と呼ぶ文献もあるので注意してほしい。本書で「半順序」は弱半順序または狭義半順序を意味する。