cut・cycle性質から最適全域木を構成する

概要

最小・最大全域木とcut・cycle性質

辺重み順の成分併合をcut・cycle性質で正当化し、全域木の構成と閾値別成分数による最適重みを導く。

考え方

無向連結graphから全頂点をつなぐV−1辺を選ぶ。最小全域木では、cutをまたぐ最小辺を安全に採用できることがgreedyの根拠になる。graphが非連結なら全域森を得る。

cutの交換と閾値別成分数

Kruskalでは辺を重み昇順に読み、端点が別DSU成分なら採用して併合する。現在の採用森を含む最適全域木をTとする。新辺eがTにないなら、Tへeを足すとcycleができ、eの端点成分をまたぐ別辺fを除ける。eはその時点で使える最小辺なのでw(e)≤w(f)、既存の採用辺はfではない。交換後も最適木に採用森を含められるので、最後の木が最適になる。最大化は重み降順へ変える。

最終graphが連結で、相異なる重みをw1<…<wR、w_i以下のgraphの成分数をC_iとする。w_iまでにKruskalが選ぶ辺数はN−C_i。従って重みw_iの採用数はC_{i−1}−C_i(C_0=N)であり、MST=Σ_i w_i(C_{i−1}−C_i)=w1(N−1)+Σ_{i=1}^{R−1}(w_{i+1}−w_i)(C_i−1)。負重みでもこの有限の層別式は成立する。

小さい整数重み0,…,Wなら各閾値t=0,…,W−1にDSUを持ち、初期graphが連結ならMST=Σ_t(C_t−1)。重みwの辺追加はt≥wのDSUへ追加し、実際に成分が減った閾値だけMSTを1減らす。この実装は一追加O(W α(N))、空間O(NW)なので、Wが小さいことが必要になる。

成立条件と計算量

Kruskalはsort O(E log(E+1))とDSU。Primは頂点ごとの候補をdecrease-keyするheapならO((V+E) log(V+1))、辺候補を残して後で捨てるheapならO((V+E) log(V+E+1))となる。同重みの辺は最適値を変えなくても木の形を変える。閾値ごとの成分数から重みを数える見方は次の節で扱う。

下位単元

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。DSUやheapを用い、cut・cycle性質で全域木の辺選択を正当化する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: グラフアルゴリズム。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-spanning-tree-optimization

習得する技能

  • cut・cycle性質で辺の安全性を証明し、Kruskal法または同値な選択で最小・最大全域木を構成できる。
  • 重み閾値以下のグラフの成分数からMST重みを層別和として導き、辺追加時に各閾値の連結性を更新して最適重みを維持できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: DSUによる連結成分管理・縮約、交換論から選択順を導く。

このUnitを直接前提とする単元: Kruskal順の閾値DSU sweep。

貪欲の交換論を土台に、cut・cycle性質から最適全域木の辺の採否条件を導く。DSUはKruskal順の閾値sweepで初めて必須にする。

このUnitでは扱わないもの

  • 任意の全域木を一つ構成するだけの探索、および辺重みを最適化しない連結成分管理。

根拠