最小・最大全域木とcut・cycle性質
辺重み順の成分併合をcut・cycle性質で正当化し、全域木の構成と閾値別成分数による最適重みを導く。
この典型を扱う単元: cut・cycle性質から最適全域木を構成する
検索別名: Kruskal法、maximum spanning tree、minimum spanning tree、最大全域木、最小全域木
未知問からこの典型を見つける手掛かり
- 扱う対象
- spanning tree
- 全域木
- 辺重み
- 重み付き無向グラフ
- 使う手掛かり
- 辺を採用できる
- 連結成分を結ぶ
- 重み順に辺
- 保つ不変量
- cut property
- cycle property
- 採用辺は閉路を作らない
- 求めるもの
- 全域木
- 最大重み
- 最小重み
- 辺の採否
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: グラフモデルと構造
関連する典型
- DSUによる連結成分管理・縮約: Kruskal順に採用済み成分を管理する実装ではDSUを併用するが、cut・cycle性質そのものとは分けて学ぶ。
学習成果と学習単位
cut・cycle性質で辺の安全性を証明し、Kruskal法または同値な選択で最小・最大全域木を構成できる。
cut・cycle性質から最適全域木を構成するで学ぶ重み閾値以下のグラフの成分数からMST重みを層別和として導き、辺追加時に各閾値の連結性を更新して最適重みを維持できる。
cut・cycle性質から最適全域木を構成するで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC218 E「Destruction」 公式問題主題: cut・cycle性質から最適全域木を構成する / 主タグ
- ABC270 F「Transportation」 公式問題主題: cut・cycle性質から最適全域木を構成する / 主タグ
- ABC282 E「Choose Two and Eat One」 公式問題主題: cut・cycle性質から最適全域木を構成する / 主タグ
- ABC352 E「Clique Connect」 公式問題主題: cut・cycle性質から最適全域木を構成する / 主タグ
- ABC355 F「MST Query」 公式問題主題: cut・cycle性質から最適全域木を構成する / 主タグ
- ABC364 F「Range Connect MST」 公式問題主題: cut・cycle性質から最適全域木を構成する / 主タグ
技能・出典
主タグ: 最小・最大全域木とcut・cycle性質 / 補助タグ: 単調進行による償却解析、DSUによる連結成分管理・縮約、ordered set・multisetの動的順序管理