電気通信大学 情報理工学研究科 情報・ネットワーク工学専攻 2023年8月実施 選択問題 アルゴリズムとデータ構造

标签：

• University-of-Electro-Communications
• Prim-Algorithm
• Priority-Queue
• Binary-Heap
• Minimum-Spanning-Tree

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

正の辺コストをもつ連結無向グラフに対する Prim 法を考える。指定グラフで辺の追加順を求め、隣接リストを単純走査する場合の計算量を評価せよ。さらに優先度付きキューによる高速化と、最小全域木の 1 辺のコストが増加した場合の再計算法を示せ。

题目描述

给出 Prim 最小生成树算法，要求写出指定图从顶点 $B$ 开始时的选边顺序，分析朴素邻接表实现的复杂度，以优先队列加速，并设计树边权值增大后的高效重算方法。

Kai

(1)

各段階でカットを横切る最小コストの辺を選ぶと、

$$\boxed{(B,F),(F,C),(C,H),(F,A),(A,D)}$$

の順に追加される。

(2)

step.3 の各実行で $U$ に属する全頂点の隣接リストを走査すると、1 回当たり最悪 $O(m)$ である。while ループは $n-1$ 回実行されるので、

$$\boxed{O(nm)}$$

となる。

(3)

$X$ を辺コストをキーとする二分最小ヒープとする。

• 初期化時に $s$ に接続する全辺を $X$ に挿入する。
• step.3 では $X$ から最小辺を取り出す。両端点がすでに $U$ にあれば捨て、カットを横切る辺が得られるまで繰り返す。
• step.5 で新頂点 $v$ を $U$ に加えた後、$v$ の隣接リストを走査し、他端点が $V-U$ にある各辺を $X$ に挿入する。

各辺は高々 1 回挿入・取出しされ、各ヒープ操作は $O(\log m)$ である。

(4)

全隣接リストの走査は $O(m)$、ヒープ操作は合計 $O(m\log m)$ である。したがって、

$$\boxed{O(m\log m)}$$

となる。

(5)

コストが増加した木の辺を $e$ とする。

1. $T$ から $e$ を除き、2 つの連結成分 $S$ と $V-S$ を得る。
2. 更新後の $G$ の全辺を 1 回走査し、このカットを横切る最小コスト辺 $f$ を求める。
3. $T-e+f$ を新しい全域木とする。

更新前後のコストを $w,w'$ とする。更新後の任意の全域木を $S$ とする。

• $e\in S$ ならば、$e$ を含む木はすべて同じだけ値が増えるので $w'(T)\leq w'(S)$ であり、$w'(f)\leq w'(e)$ より $w'(T-e+f)\leq w'(S)$ である。
• $e\notin S$ ならば、$S+e$ の閉路上にこのカットを横切る辺 $g$ がある。更新前の $T$ の最小性より

$$w(T)\leq w(S-g+e)=w(S)-w(g)+w(e).$$

$w'(f)\leq w'(g)=w(g)$ であるから、$w'(T-e+f)\leq w'(S)$ となる。

よって $T-e+f$ は更新後の最小全域木である。

走査は 1 回だけなので計算量は

$$\boxed{O(m)}$$

であり、Prim 法を最初から行う $O(m\log m)$ より高速である。図の例で $CF$ を $2$ から $10$ にすると、代替辺は $BC$（コスト $3$）となる。