グラフ理論の問題
頂点集合を とする重みつき単純無向グラフ があり、辺とその重みは次の 本である。
の最小全域木の重み（最小全域木に含まれる辺の重みの和）を求めよ。
この問題で使うもの
- 最小全域木（クラスカル法・プリム法）（説明と入口の問題）
この問題を解けるようになるまで（7 技能）
読み込み中…
右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
ヒント
行き詰まったら、上から順に 1 つずつ開いてください。
ヒント 1
クラスカル法（またはプリム法）を使って最小全域木を作ります。頂点が 個なので、全域木の辺は何本になるかも確認しましょう。
ヒント 2
辺を重みの小さい順に並べ、閉路ができない辺だけを選んでいきます。全域木の辺数は 本です。
ヒント 3
小さい順に , , はそのまま選べます。次の は閉路を作るので捨てます。残り 本は をつなぐ辺のうち最小のものです。
答えと解説
答えを見る
どこでつまずきましたか？（選ぶと、戻る場所を案内します）
解説を読む
クラスカル法を使う。クラスカル法では、辺を重みの小さい順に見ていき、すでに選んだ辺と閉路を作らないなら選び、閉路を作るなら捨てる。
頂点は 個なので、全域木の辺の数は 本である。 本選んだところで終わる。
辺を重みの小さい順に並べると
となる。順に調べる。
- （重み ）: 閉路はできないので選ぶ。つながっている頂点の組は 。
- （重み ）: はまだどことも結ばれていないので選ぶ。。
- （重み ）: はまだ結ばれていないので選ぶ。。
- （重み ）: と はすでに でつながっているので、選ぶと閉路 ができる。捨てる。
- （重み ）: はまだ結ばれていないので選ぶ。。
これで 本選んだので終了する。最小全域木の辺は で、重みの和は
である。
（確認）プリム法で から始めても、 に接する最小の辺 、次に から出る最小の辺 、次に から出る最小の辺 、最後に から へ出る辺 のうち最小の を選び、同じ が得られる。
したがって、答えは である。
別解
クラスカル法で解く。辺を重みの昇順に並べると AC:2, CD:3, AB:4, BC:5, BE:6, DE:7, CE:8, BD:10。
1. AC(2) を採用。{A,C}
2. CD(3) を採用。{A,C,D}
3. AB(4) を採用。{A,B,C,D}
4. BC(5) は B,C が同じ成分内なので閉路ができる。不採用。
5. BE(6) を採用。E が加わり全頂点がつながる（辺は 4 本）。
採用した辺は AC, CD, AB, BE で、重みの和は 2+3+4+6=15。
検算：プリム法で A から始める。A-C(2)、C-D(3)、A-B(4)、B-E(6) の順に選ばれ、合計は 15 で一致する。E に接続する辺の最小は BE=6 なので、E を加えるコストは少なくとも 6。残り 4 頂点 A,B,C,D の最小全域木は AC,CD,AB で 9。合計 15。