JunKobayashi https://blog.hatena.ne.jp/JunKobayashi/ JunKobayashi's Diary https://junkobayashi.hatenablog.com/ 貪欲法 正当性証明 クラスカル法 ＜問題設定＞ 頂点集合および辺集合をそれぞれ\(V,E\)とする連結なグラフ\(G=(V,E)\)がある。\(e \in E\)なる各辺\(e\)には正の重み（\(w(e)\)と表記する）が設定されている。\(G\)の最小全域木に含まれる辺たちの重みの総和はいくらか？ ＜主張＞ 以下＜クラスカル法＞の手続きに従えば、\(G\)の最小全域木（のうちの一つ）を必ず構築できる。 ＜クラスカル法＞ グラフ\(H=(V,E_H)\)を\(H=(V,\varnothing)\)で初期化し、\(e \in E\)なる全ての辺\(e\)を\(w(e)\)の値について昇順に（同率のものが二本以上存在する場合はそ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fjunkobayashi.hatenablog.com%2Fentry%2F2025%2F11%2F30%2F113826" title="クラスカル法の正当性証明 - JunKobayashi&#39;s Diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/J/JunKobayashi/20251129/20251129074634.png Hatena Blog https://hatena.blog 2025-11-30 11:38:26 rich https://junkobayashi.hatenablog.com/entry/2025/11/30/113826 1.0 100%