アルゴリズム設計・解析特論第 3 回レポート

600P031-4 高木祐介

提出日 2000-06-13

7.3 図 7.20 のグラフを考える。

V = {a, b, c, d, e, f, g, h}

a b c d e f g h
a  2 3 no no no no no
b 2  no 2 no no no no
c 3 no  1 no no no no
d no 2 1  2 4 no no
e no no no 2  1 2 no
f no no no 4 1  2 1
g no no no no 2 2  3
h no no no no no 1 3

続く 2 問は、「深さ優先の極大木を求めよ。」となっていますが、コスト最小の極大木の間違いだと思います。したがって、以下の 2 問では、 2 通りのアルゴリズムを使って、コスト最小の極大木を求めます。

(a) プリムのアルゴリズムを使って、深さ優先（ママ）の極大木を求めよ。

プリムのアルゴリズムでは、 U 内の頂点の LOWCOST に番兵として ∞ を入れています。教科書 207 ページの図 7.8 (12) 行目です。

(5) 行目から (10) 行目まで、 U 外にあって U 内の頂点に最も近い頂点 k を求めるときに、 LOWCOST [k] < ∞ であるような k が存在するという前提に立っています。

また、 (14) 行目の and (LOWCOST [j] < ∞) で、 j が U 外の頂点であるかを判定しています。このため、 no は < ∞ かつ > max{C[v, w]|v, w ∈ V } でなければなりません。

U  CLOSEST [i], LOWCOST [i]
b c d e f g h
{a}  a, 2 a, 3 a, no a, no a, no a, no a, no
{a, b}  a, ∞ a, 3 b, 2 a, no a, no a, no a, no
{a, b, d}  a, ∞ d, 1 b, ∞ d, 2 d, 4 a, no a, no
{a, b, d, c}  a, ∞ d, ∞ b, ∞ d, 2 d, 4 a, no a, no
{a, b, d, c, e}  a, ∞ d, ∞ b, ∞ d, ∞ e, 1 e, 2 a, no
{a, b, d, c, e, f}  a, ∞ d, ∞ b, ∞ d, ∞ e, ∞ e, 2 f, 1
{a, b, d, c, e, f, h}  a, ∞ d, ∞ b, ∞ d, ∞ e, ∞ e, 2 f, ∞
{a, b, d, c, e, f, h, g} a, ∞ d, ∞ b, ∞ d, ∞ e, ∞ e, ∞ f, ∞

印刷される辺 (b, a) (d, b) (c, d) (e, d) (f, e) (h, f) (g, e)

(b) クラスカルのアルゴリズムを使い、深さ優先（ママ）の極大木を求めよ。

ncomp, components  T, edges
8, [a], [b], [c], [d], [e], [f], [g], [h] ∅, {(c, d), (e, f), (f, h), (a, b), (b, d), (d, e), (e, g), (f, g), (a, c), (g, h), (d, f)}
7, [a], [b], [c, d], [e], [f], [g], [h] {(c, d)}, {(e, f), (f, h), (a, b), (b, d), (d, e), (e, g), (f, g), (a, c), (g, h), (d, f)}
6, [a], [b], [c, d], [e, f], [g], [h]  {(c, d), (e, f)}, {(f, h), (a, b), (b, d), (d, e), (e, g), (f, g), (a, c), (g, h), (d, f)}
5, [a], [b], [c, d], [e, f, h], [g]  {(c, d), (e, f), (f, h)}, {(a, b), (b, d), (d, e), (e, g), (f, g), (a, c), (g, h), (d, f)}
4, [a, b], [c, d], [e, f, h], [g]  {(c, d), (e, f), (f, h), (a, b)}, {(b, d), (d, e), (e, g), (f, g), (a, c), (g, h), (d, f)}
3, [a, b, c, d], [e, f, h], [g]  {(c, d), (e, f), (f, h), (a, b), (b, d)}, {(d, e), (e, g), (f, g), (a, c), (g, h), (d, f)}
2, [a, b, c, d, e, f, h], [g]  {(c, d), (e, f), (f, h), (a, b), (b, d), (d, e)}, {(e, g), (f, g), (a, c), (g, h), (d, f)}
1, [a, b, c, d, e, f, h, g]  {(c, d), (e, f), (f, h), (a, b), (b, d), (d, e), (e, g)}, {(f, g), (a, c), (g, h), (d, f)}

頂点の順序を a, b, c, d, e, f, g, h とすると、プリムのアルゴリズムもクラスカルのアルゴリズムも同じ結果を出しました。

クラスカルのアルゴリズムは、すべての辺を整列するのに時間がかかりますが、その後は速いです。プリムのアルゴリズムは、 CLOSEST と LOWCOST の更新に時間がかかります。

7.5 G = (V, E) をグラフとする。 R を V 上の関係として、 u と v が共通の閉路上にあることを uRv

で示すことにする。 R が V 上の同値関係であることを証明せよ。

経路 v_{1}, …, v_{n} が閉路であるとは、以下の 3 つが成り立つことです。

\begin{matrix}頂点を自分自身と連結 & (v_{1} = v_{n}) \\ 長さ 3 以上 & (n ≥ 3) \\ 単純 & ∀i, j ∈ [1, n − 1] (i ≠ j ⇒ v_{i} ≠ v_{j}) \end{matrix}

u と v が共通の閉路上にあるとは、閉路 u, v_{1}, …, v_{i}, v, v_{i+1}, …, v_{n}, u が存在することです。

同値関係

一般に、 R が V 上の同値関係であるとは、 R が V 上の関係であって、以下の 3 つが成り立つことです。

\begin{matrix}反射律 & ∀v ∈ V (vRv) \\ 対称律 & ∀u, v ∈ V (uRv ⇒ vRu) \\ 推移律 & ∀u, v, w ∈ V (uRv ∧ vRw ⇒ uRw) \end{matrix}

設問より、 R が V 上の関係であることは分かったので、反射律、対称律、推移律の 3 つが成り立つことを示します。

反射律

∀v ∈ V (vRv) が成り立つことを示します。

• v を通る閉路が存在すれば、明らかに vRv です。 v と v は共通の閉路上にあるからです。

• v を通る閉路が存在しない場合、分かりません。 vRv は成り立ちません。

対称律

∀u, v ∈ V (uRv ⇒ vRu) が成り立つことを示します。 uRv より、閉路 u, v_{1}, …, v_{i}, v, v_{i+1}, …, v_{n}, u が存在します。この閉路は、 v, v_{i+1}, …, v_{n}, u, v_{1}, …, v_{i}, v と表すことができます。すなわち、 vRu が成り立ち

ます。

推移律

∀u, v, w ∈ V (uRv ∧ vRw ⇒ uRw) が成り立つことを示します。 uRv より、閉路 u, v_{1}, …, v_{i}, v, v_{i+1}, …, v_{n}, u が存在します。

• この閉路上に w があれば、明らかに uRw です。すなわち、 w ∈ {u, v_{1}, …, v_{i}, v, v_{i+1}, …, v_{n}} であれば、 u と w は共通の閉路上にあります。

• この閉路上の v 以外の頂点が、閉路 v, w_{1}, …, w_{j}, w, w_{j+1}, …, w_{m}, v 上にある場合、 uRw です。すなわち、 v_{k} = w_{l} ならば、

\begin{matrix}k < i, l < j の場合 & u, v_{1}, …, v_{k} = w_{l}, …, w_{j}, w, w_{j+1}, …, w_{m}, v, v_{i+1}, …, v_{n}, u \\ k < i, l > j の場合 & u, v_{1}, …, v_{k} = w_{l}, …, w_{j+1}, w, w_{j}, …, w_{1}, v, v_{i+1}, …, v_{n}, u \\ k > i, l < j の場合 & u, v_{1}, …, v_{i}, v, w_{m}, …, w_{j+1}, w, w_{j}, …, w_{l} = v_{k}, …, v_{n}, u \\ k > i, l > j の場合 & u, v_{1}, …, v_{i}, v, w_{1}, …, w_{j}, w, w_{j+1}, …, w_{l} = v_{k}, …, v_{n}, u \end{matrix}

という閉路が存在し、 u と w が共通の閉路上にあります。

• u を通る閉路と w を通る閉路に共通な頂点が v のみの場合、分かりません。 {u, v_{1}, …, v_{n}}∪ {w_{1}, …, w_{j}, w, w_{j+1}, …, w_{m}} = ∅ の場合、 uRw は成り立ちません。

結論

V 上の関係 R について、対称律は成り立ちますが、反射律と推移律は必ずしも成り立ちません。したがって、 R は V 上の同値関係ではありません。

この問題が問題として成り立つためには、制約を緩めなければなりません。以下に、制約を緩めた例をいくつか挙げます。

• 問題自体を変えてしまう。「であることを証明せよ。」とは、でないことを証明すれば解決されたものとする。

• 定義を変えてしまう。同値関係の定義、反射律と推移律を変える。あるいは閉路の定義、長さ 3 以上であること、単純であることを変える。

• 解釈を変える。「u と v が共通の閉路上にある」とは、 u と v を通る閉路が存在することではなく、 u を通る閉路と v を通る閉路が共有点を持つことであるとする。

• 問題文中の言葉を変える。 G は 3 つ以上の頂点を持つ完全グラフ、すなわちすべての頂点の対が接続されたグラフであるとする。あるいは u と v を連結する単純な経路が存在することを uRv で示すものとする。

上の方は無茶な話なので、最後の案を採るのが良いでしょう。