この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

グラフ理論の問題

難易度 4大学院入試の標準レベル大学数学グラフ理論

頂点集合 $V = {v_{1}, v_{2}, v_{3}, v_{4}, v_{5}, v_{6}, v_{7}}$ をもつ重みつき単純無向グラフ $G$ があり、辺とその重みは次の $12$ 本である。
$v_{1} v_{2} : 8, v_{3} v_{4} : 13, v_{5} v_{6} : 16, v_{1} v_{3} : 3, v_{3} v_{5} : 6, v_{5} v_{7} : 1, v_{2} v_{3} : 12, v_{4} v_{5} : 11, v_{6} v_{7} : 17, v_{2} v_{4} : 4, v_{4} v_{6} : 14, v_{2} v_{6} : 18$
全域木の重みを、その全域木に含まれる辺の重みの和と定める。辺の重みはすべて異なるので、 $G$ の最小全域木（重みが最小の全域木）はただ 1 つに定まる。これを $T$ とする。

$T$ と異なる $G$ の全域木の重みの最小値を求めよ。

この問題で使うもの

最小全域木（クラスカル法・プリム法）（説明と入口の問題）

この問題を解けるようになるまで（7 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

まずクラスカル法などで最小全域木 $T$ を求めましょう。次に、 $T$ と異なる全域木で重みが最小のものは、 $T$ から辺を 1 本外して別の辺を 1 本加えたもので得られることを使います。

ヒント 2

木に入っていない辺 $f$ を $T$ に加えると閉路が 1 つでき、その閉路上の $T$ の辺を 1 本外すと全域木に戻ります。重みの増加 $w (f) - w (e)$ を最小にするには、外す辺 $e$ を閉路上で最も重い $T$ の辺にします。

ヒント 3

$T$ の重みは $36$ で、 $T$ は $v_{7} - v_{5} - v_{3} - v_{1} - v_{2} - v_{4} - v_{6}$ という道になります。6 本の非木辺それぞれについて、 $T$ 上の道の最大の重みとの差を計算して比べましょう。最小の非木辺を加えるのが最善とは限りません。

答えと解説

答えを見る

38

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

最小全域木 $T$ を求める クラスカル法で、重みの小さい辺から順に、閉路ができない限り採用する。
- $v_{5} v_{7} (1)$ ：採用
- $v_{1} v_{3} (3)$ ：採用
- $v_{2} v_{4} (4)$ ：採用
- $v_{3} v_{5} (6)$ ：採用（ ${v_{1}, v_{3}, v_{5}, v_{7}}$ と ${v_{2}, v_{4}}$ ができる）
- $v_{1} v_{2} (8)$ ：採用（ ${v_{1}, v_{2}, v_{3}, v_{4}, v_{5}, v_{7}}$ がつながる）
- $v_{4} v_{5} (11)$ 、 $v_{2} v_{3} (12)$ 、 $v_{3} v_{4} (13)$ ：両端がすでに同じ成分にあり閉路ができるので不採用
- $v_{4} v_{6} (14)$ ：採用（ $v_{6}$ がつながり、辺が $6$ 本になって終了）

よって $T = {v_{5} v_{7}, v_{1} v_{3}, v_{2} v_{4}, v_{3} v_{5}, v_{1} v_{2}, v_{4} v_{6}}$ で、その重みは $1 + 3 + 4 + 6 + 8 + 14 = 36$ である。

2 番目の全域木は辺 1 本の交換で得られること $T$ と異なる全域木のうち重みが最小のものの 1 つを $T^{'}$ とする。 $T^{'} ∖ T$ の辺 $f$ を 1 本とる。 $T^{'}$ から $f$ を除くと頂点集合が 2 つの部分 $S, V ∖ S$ に分かれ、 $f$ はその間を結ぶ。一方 $T + f$ にはただ 1 つの閉路 $C$ があり、 $C$ は $f$ を含むので、 $f$ 以外にも $S$ と $V ∖ S$ を結ぶ辺 $e$ を含む（ $e \in T$ ）。すると $T + f - e$ も $T^{'} - f + e$ も全域木である。 $T$ は最小全域木で重みはすべて異なるから、 $f$ は閉路 $C$ 上で重みが最大の辺であり、 $w (e) < w (f)$ 。よって $T^{'} - f + e$ の重みは $w (T^{'}) - w (f) + w (e) < w (T^{'})$ となる。 $T^{'}$ の最小性から $T^{'} - f + e$ は $T$ と異ならない、すなわち $T^{'} - f + e = T$ であり、 $T^{'} = T + f - e$ となる。

したがって、各非木辺 $f$ について「 $T$ 上で $f$ の両端を結ぶ道にある辺の重みの最大値」を $M (f)$ とすると、求める値は $36 + min_{f} {w (f) - M (f)}$ である（ $f$ の代わりに外すのは、その道の上で最も重い辺にするのが最善）。

各非木辺について調べる $T$ は $v_{7} - v_{5} - v_{3} - v_{1} - v_{2} - v_{4} - v_{6}$ という 1 本の道である。
- $v_{2} v_{3} (12)$ ：道 $v_{2} v_{1} v_{3}$ の辺の重み $8, 3$ 。 $M = 8$ 、増加 $12 - 8 = 4$
- $v_{3} v_{4} (13)$ ：道 $v_{3} v_{1} v_{2} v_{4}$ の辺の重み $3, 8, 4$ 。 $M = 8$ 、増加 $5$
- $v_{4} v_{5} (11)$ ：道 $v_{4} v_{2} v_{1} v_{3} v_{5}$ の辺の重み $4, 8, 3, 6$ 。 $M = 8$ 、増加 $3$
- $v_{5} v_{6} (16)$ ：道 $v_{5} v_{3} v_{1} v_{2} v_{4} v_{6}$ の辺の重み $6, 3, 8, 4, 14$ 。 $M = 14$ 、増加 $2$
- $v_{6} v_{7} (17)$ ：道 $v_{6} v_{4} v_{2} v_{1} v_{3} v_{5} v_{7}$ 。 $M = 14$ 、増加 $3$
- $v_{2} v_{6} (18)$ ：道 $v_{2} v_{4} v_{6}$ の辺の重み $4, 14$ 。 $M = 14$ 、増加 $4$

増加の最小値は $2$ （ $v_{4} v_{6}$ を外して $v_{5} v_{6}$ を加える）である。

よって求める最小値は $36 + 2 = 38$ である。

別解

まずクラスカル法で最小全域木 $T$ を求める。辺を重みの昇順に並べると $v_{5} v_{7} (1), v_{1} v_{3} (3), v_{2} v_{4} (4), v_{3} v_{5} (6), v_{1} v_{2} (8), v_{4} v_{5} (11), v_{2} v_{3} (12), v_{3} v_{4} (13), v_{4} v_{6} (14), v_{5} v_{6} (16), v_{6} v_{7} (17), v_{2} v_{6} (18)$ 。
順に採用する: $v_{5} v_{7}$ 、 $v_{1} v_{3}$ 、 $v_{2} v_{4}$ 、 $v_{3} v_{5}$ （成分 ${1, 3, 5, 7}$ ）、 $v_{1} v_{2}$ （成分 ${1, 2, 3, 4, 5, 7}$ ）。 $v_{4} v_{5}, v_{2} v_{3}, v_{3} v_{4}$ は閉路ができるので不採用。 $v_{4} v_{6}$ を採用して 6 本。
$T = {v_{5} v_{7}, v_{1} v_{3}, v_{2} v_{4}, v_{3} v_{5}, v_{1} v_{2}, v_{4} v_{6}}$ 、重みは $1 + 3 + 4 + 6 + 8 + 14 = 36$ 。

$T$ と異なる全域木のうち重みが最小のものは、 $T$ から辺を 1 本だけ入れ替えたもの（非木辺 $e$ を加え、 $T$ 上の $e$ の両端を結ぶ道の最大重みの辺を除く）の中にある。各非木辺について重みの増加は次のとおり。
- $v_{4} v_{5} (11)$ : 道 $v_{4} v_{2} v_{1} v_{3} v_{5}$ の最大は 8、増加 $11 - 8 = 3$
- $v_{2} v_{3} (12)$ : 道 $v_{2} v_{1} v_{3}$ の最大は 8、増加 4
- $v_{3} v_{4} (13)$ : 道 $v_{3} v_{1} v_{2} v_{4}$ の最大は 8、増加 5
- $v_{5} v_{6} (16)$ : 道 $v_{5} v_{3} v_{1} v_{2} v_{4} v_{6}$ の最大は 14、増加 2
- $v_{6} v_{7} (17)$ : 道 $v_{7} v_{5} v_{3} v_{1} v_{2} v_{4} v_{6}$ の最大は 14、増加 3
- $v_{2} v_{6} (18)$ : 道 $v_{2} v_{4} v_{6}$ の最大は 14、増加 4

最小の増加は 2（ $v_{5} v_{6}$ を加えて $v_{4} v_{6}$ を除く）。全域木 ${v_{5} v_{7}, v_{1} v_{3}, v_{2} v_{4}, v_{3} v_{5}, v_{1} v_{2}, v_{5} v_{6}}$ の重みは $1 + 3 + 4 + 6 + 8 + 16 = 38$ 。
よって答えは 38。

グラフ理論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題