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

600P031-4 高木祐介

提出日 2000-06-27

7.12 G = (V, E) を完全グラフとする。すなわちどの 2 頂点の間にも辺があるようなグラフとする。 E

の各辺に任意の方向を指定してできる E′ によって、有向グラフ G′ = (V, E′) を作る。 G′ にはすべての頂

点をちょうど 1 回ずつ通る有向路があることを示せ。

n についての数学的帰納法によって、任意の n について題意が成り立つことを示します。 n = 0 のとき、 V = {} です。存在しない頂点を通る有向路があるものとします。 n = 1 のとき、 E = {} です。唯一の頂点を 1 回だけ通る有向路があるものとします。

n = 2 のとき

V = {v_{1}, v_{2}} のとき、 E = {(v_{1}, v_{2})} であり、以下の 2 つの場合があります。

• E′ = {v_{1} → v_{2}} のとき、すべての頂点を 1 回ずつ通る有向路 v_{1}, v_{2} があります。

• E′ = {v_{2} → v_{1}} のとき、すべての頂点を 1 回ずつ通る有向路 v_{2}, v_{1} があります。

いずれでもない場合というのはあり得ません。いずれの場合でも、すべての頂点を 1 回ずつ通る有向路があります。

n = k + 1 のとき

題意が n = k のときに成り立つとすると、 n = k + 1 のときにも成り立つことを示します。 V = {v_{1}, …, v_{k}, v_{k+1}} のとき、

\begin{aligned}V_{k} & = \{v_{1}, …, v_{k}\} \\ V′_{k} & = \{v′_{1}, …, v′_{k}\} = V_{k} \\ E′ & = E′_{k} ∪ E′_{f} ∪ E′_{t} \\ E′_{k} & = \{v′_{i} → v′_{i+1}|v′_{i}, v′_{i+1} ∈ V′_{k}\} \\ E′_{f} & = \{v′_{i} → v_{k+1}|v′_{i} ∈ V′_{k}\} \\ E′_{t} & = \{v_{k+1} → v′_{i}|v′_{i} ∈ V′_{k}\} \end{aligned}

とします。 E′_{f}, E′_{t} の f, t は、それぞれ from, to を表します。 G から v_{k+1} を除いた誘導部分グラフ G_{k} = (V_{k}, E_{k}) は、 n = k の完全グラフであり、 E_{k} の各

辺に任意の方向を指定してできる E′_{k} によって G′_{k} = (V_{k}, E′_{k}) を作ると、 G′_{k} にはすべての頂点をちょうど 1 回ずつ通る有向路 v′_{1}, …, v′_{k} があると定義しました。（V′_{k} = V_{k} ですが、 v′_{i} = v_{i} とは限りません。）

このとき、以下の 3 つの場合があります。

1. (v′_{k} → v_{k+1}) ∈ E′_{f} のとき、すべての頂点を 1 回ずつ通る有向路 v′_{1}, …, v′_{k}, v_{k+1} があります。

2. (v_{k+1} → v′_{1}) ∈ E′_{t} のとき、すべての頂点を 1 回ずつ通る有向路 v_{k+1}, v′_{1}, …, v′_{k} があります。

3. 上 2 つのいずれも成り立たないとき、 (v′_{i} → v_{k+1}) ∈ E′_{f} ∧ (v_{k+1} → v′_{i+1}) ∈ E′_{t} であるような i が存在し、すべての頂点を 1 回ずつ通る有向路 v′_{1}, …, v′_{i}, v_{k+1}, v′_{i+1}, …, v′_{k} があります。

(v′_{1} → v_{k+1}) ∈ E′_{f} ∧ (v_{k+1} → v′_{k}) ∈ E′_{t} のとき、 (v′_{i} → v_{k+1}) ∈ E′_{f} ∧ (v_{k+1} → v′_{i+1}) ∈ E′_{t} であるような i が存在しないものとします。

(v′_{1} → v_{k+1}) ∈ E′_{f} より、 (v′_{2} → v_{k+1}) ∈ E′_{f} でなければなりません。なぜなら、 (v_{k+1} → v′_{2}) ∈ E′_{t} ならば、 v′_{1} から v_{k+1} を通って v′_{2} へ行くような有向路があり、 i = 1 が存在してしまうからです。

同様に、 (v′_{i} → v_{k+1}) ∈ E′_{f} ならば、 (v′_{i+1} → v_{k+1}) ∈ E′_{f} でなければなりません。数学的帰納法によって、 (v′_{k} → v_{k+1}) ∈ E′_{f} でなければなりません。これは前提である (v_{k+1} →

v′_{k}) ∈ E′_{t} に反しています。

よって、先に挙げた 3 つの場合ですべてを尽くしています。いずれの場合もすべての頂点を 1 回ずつ通る有向路があります。

任意の n = k について題意が成り立つことを示しました。

7.13 n 頂点の完全グラフには、 n^{n−2} 通りの極大木があることを示せ。

n = 5 まで手で数えたのですが、任意の n = k についての証明は分かりませんでした。

組み合わせ

m 個のものから n 個のものを選ぶ組み合わせが何通りあるかを、このレポートでは C(m, n) で表します。

C は Combination の C です。一般に、 C(m, n) = \frac{m!}{n!(m−n)!} です。ここで、 ! は階乗を表し、 n! = ∏_{i=1}^{n} = 1 × 2 × ⋯ × n です。

完全グラフ

完全グラフとは、どの 2 頂点の間にも辺があるようなグラフです。完全グラフの頂点の数と辺の数とをそれぞれ n, e_{c} で表すと、辺の数は、 n 個の頂点から接続す

る 2 個を選ぶ組み合わせですから、 e_{c} = C(n, 2) = n(n − 1)/2 本です。 c は complete の c です。

極大木

連結グラフ G = (V, E) が与えられたとき、 V のすべての頂点を連結する自由木を G の極大木といいます。

自由木は、閉路のない連結グラフで、頂点と辺の数をそれぞれ n, e_{s} で表すと、 e_{s} = n − 1 です。 s は spanning tree の s です。

7.13 n 頂点の完全グラフには、 n^{n−2} 通りの極大木があることを示せ。

n = k のとき、 k 頂点の完全グラフには、 k^{k−2} 通りの極大木があることをそれぞれの k について調べます。

n = 0 の完全グラフには、極大木がありません。 0^{−2} = 0 で成り立っています。 n = 1 の完全グラフは、唯一の頂点と 0 本の辺を持ちます。唯一の頂点と 0 本の辺からなる 1

通りの極大木があります。 1^{−1} = 1 で成り立っています。

n = 2 の完全グラフは 1 本の辺を持ちます。 2 つの頂点を接続する唯一の辺からなる 1 通りの極大木があります。 2^{0} = 1 で成り立っています。

n = 3 の完全グラフは 3 本の辺を持ちます。極大木は 2 本の辺を持ちます。 3 頂点をそれぞれ接続すると閉路ができてしまうので、 3 辺のうち、いずれか 1 本を消さなければなりません。 C(3, 1) = 3 通りの極大木があります。 3^{1} = 3 で成り立っています。

n = 4 の完全グラフは 6 本の辺を持ちます。極大木は 3 本の辺を持ちます。 6 辺のうち 3 本を選ぶ組み合わせは C(6, 3) = (6 × 5 × 4)/(3 × 2 × 1) = 20 通りですが、この中には、 1 頂点だけ仲間はずれと 3 頂点をそれぞれ接続した閉路とからなる、極大木でないグラフが含まれています。 4 頂点から仲間はずれの 1 頂点を選ぶ組み合わせで、 C(4, 1) = 4 通りの極大木でないグラフがあるので、極大木は 20 − 4 = 16 通りです。 4^{2} = 16 で成り立っています。 n = 5 のとき

n = 5 の完全グラフは 10 本の辺を持ちます。極大木は 4 本の辺を持ちます。 4 辺を持つ 5 頂点のグラフは C(10, 4) = (10 × 9 × 8 × 7)/(4 × 3 × 2 × 1) = 210 通りですが、このうち極大木でないのは、

• 2 頂点と 1 辺を持つ連結成分と、 3 頂点と 3 辺を持つ閉路とからなるグラフ

• 仲間はずれの 1 頂点と、 4 頂点と 4 辺を持つ連結成分とからなるグラフ

の 2 種に分類できます。前者は、 2 頂点と 1 辺を持つ連結成分も、 3 頂点と 3 辺を持つ閉路も、それぞれ 1 通りしかない

ので、全体で C(5, 2) = (5 × 4)/2 = 10 通りです。

後者は、 4 頂点と 4 辺を持つ連結成分が、 C(6, 4) = (6 × 5 × 4 × 3)/(4 × 3 × 2 × 1) = 15 通りなので、全体で 15 × 5 = 75 通りです。

n = 5 のとき、 210 − (10 + 75) = 125 通りの極大木があり、 5^{3} = 125 で成り立っています。

\begin{matrix}n & e_{c} & e_{s} & 極大木 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 2 & 1 & 1 & 1 \\ 3 & 3 & 2 & 3 \\ 4 & 6 & 3 & 16 \\ 5 & 10 & 4 & 125 \end{matrix}

n = k のとき

数学的帰納法によって、 n < k のとき n 頂点の完全グラフには n^{n−2} 通りの極大木があるとすると、 n = k のときも成り立つことを示します。

分かりませんでした。