数学最小张成树本页总览最小张成树考虑图 G=(N,E)G=(N,E)G=(N,E)，每条边有权重 cec_ece，寻找一个包含所有节点的权重总和最小的树。 决策变量 xe∈{0,1}x_e\in\{0,1\}xe∈{0,1}，优化 min∑ecexe\min\sum_ec_ex_emin∑ecexe 切割形式 ∑e∈δ(S)xe≥1,∀S\sum_{e\in\delta(S)}x_e\ge1,\forall S∑e∈δ(S)xe≥1,∀S ∑e∈Exe=n−1\sum_{e\in E}x_e=n-1∑e∈E xe=n−1 无环形式 ∑e∈E(S)xe≤∣S∣−1,∀S\sum_{e\in E(S)}x_e\le|S|-1,\forall S∑e∈E(S)xe≤∣S∣−1,∀S ∑e∈Exe=n−1\sum_{e\in E}x_e=n-1∑e∈Exe=n−1 可以证明，这种情况下 P=CH(T)P=CH(T)P=CH(T)