赋权图中的最小支撑树问题及其解法

定义3　给定图G=（V，E），对G中的每一条边[vi，vj]，相应地有一个数 wij，则称这样的图G 为赋权图，wij称为边[vi，vj]上的权。

这里所说的“权”，是指与边有关的数量指标。根据实际问题的需要，可以赋予它不同的含义，例如表示距离、时间、费用等。

赋权图在图的理论及其应用方面有着重要的地位。赋权图不仅指出各个点之间的邻接关系，而且同时也表示出各点之间的数量关系。所以，赋权图被广泛地应用于解决工程技术及科学生产管理等领域的最优化问题。最小支撑树问题就是赋权图上的最优化问题之一。

设有一个连通图G=（V，E），每一边e=[vi，vj]，有一个非负权 w（e）=wij，（wij≥0）。

定义4　如果T=（V，E′）是G的一个支撑树，称E′中所有边的权之和为支撑树T的权，记为w（T）。即

如果支撑树T*的权 w（T*）是G的所有支撑树的权中最小者，则称T*是G的最小支撑树（简称最小树）。即

式中对G的所有支撑树取最小。

最小支撑树问题就是要求给定连通赋权图G的最小支撑树。

假设给定一些城市，已知每对城市间交通线的建造费用，要求建造一个连结这些城市的交通网，使总的建造费用最小，这个问题就是赋权图上的最小树问题。

下面介绍求最小树的两种方法。

1.避圈法（kruskal）

开始选一条最小权的边，以后每一步中，总从与已选边不构成圈的那些未选边中，选一条权最小的（每一步中，如果有两条或两条以上的边都是权最小的边，则从中任选一条）。

算法的具体步骤如下：

第一步：令i=1，E0=∅。

第二步：选一条边ei∈E \Ei-1，使 ei是使（V，Ei-1∪{ei}）不含圈的所有边ei（ei∈E \Ei-1）中权最小的边。令Ei∈Ei-1∪{ei}，如果这样的边不存在，则T=（V，Ei-1）是最小树。

第三步：把i 换成 i+1，转入第二步。

在证明这种方法的正确性之前，先介绍一个例子。

例6-8　某工厂内连结六个车间的道路网如图6-18（a）所示。已知每条道路的长，要求沿道路架设连结六个车间的电话线网，使电话线的总长最小。

(www.xing528.com)

图6-18

解　这个问题就是求图6-18（a）所示的赋权图上的最小树，用避圈法求解。

i=1，E0=∅，从E中选最小权边[v2，v3]，E1={[v2，v3]}；

i=2，从E \E1中选最小权边[v2，v4]（[v2，v4]与[v2，v3]不构成圈），E2={[v2，v3]，[v2，v4]}；

i=3，从E \E2中选最小权边[v4，v5]（（V，E2∪[v4，v5]）不构成圈），令E3={[v2，v3]，[v2，v4]，[v4，v5]}；

i=4，从E \E3中选边[v5，v6]（或选[v4，v6]）（（V，E3∪[v5，v6]）不构成圈），令E4={[v2，v3]，[v2，v4]，[v4，v5]，[v5，v6]}；

i=5，从E \E4中选边[v1，v2（]（V，E4∪[v1，v2]）不构成圈），注意，因[v4，v6]与已选边[v4，v5]，[v5，v6]构成圈，所以虽然[v4，v6]的权小于[v1，v2]的权，但这时不能选[v4，v6]），令

E5={[v2,v3],[v2,v4],[v4,v5],[v5,v6],[v1,v2]}；

i=6，这时，任一条未选的边都与已选的边构成圈，所以算法终止。

（V，E5）就是要求的最小树，即电话线总长最小的电话线网方案如图6-18（b）所示，电话线总长为15 单位。

现在来证明方法1的正确性。

令G=（V，E）是连通赋权图，根据6.2.2 小节中所述可知：方法1 终止时，T=（V，Ei-1）是支撑树，这时i=p（G）。记

用反证法来证明T 是最小支撑树。设T 不是最小支撑树，在G的所有支撑树中，令H 是与T的公共边数最大的最小支撑树。因T 与H 不是同一个支撑树，故T中至少有一条边不在H中。令 ei（1≤i≤p-1）是第一个不属于H的边，把 ei放入H中，必得到一个且仅一个圈，记这个圈为C。因为T 是不含圈的，故C中必有一条边不属于T，记这条边为e。在H中去掉e，增加 ei，就得到G的另一个支撑树 T0，可见

因为w（H）≤w（T0）（因H 是最小支撑树），推出 w（ei）≥w（e）。但根据算法，ei是使（V，{e1，e2，…，ei}）不含圈的权最小的边，而（V，{e1，e2，…，ei-1，e}）也是不含圈的，故必有w（ei）=w（e），从而w（T0）=w（H）。这就是说，T0也是G的一个最小支撑树，但是 T0与T的公共边数比H 与T的公共边数多一条，这与H的选取矛盾。

2.破圈法

任取一个圈，从圈中去掉一条权最大的边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条）。在余下的图中，重复这个步骤，直至得到一个不含圈的图为止，这时的图便是最小树。

例6-9　用破圈法求图6-18（a）所示赋权图的最小支撑树。

解　任取一个圈，比如（v1，v2，v3，v1），边[v1，v3]是这个圈中权最大的边，于是丢去[v1，v3]；再取圈（v3，v5，v2，v3），去掉[v2，v5]；取圈（v3，v5，v4，v2，v3），去掉[v3，v5]；取圈（v5，v6，v4，v5），这个圈中，[v5，v6]及[v4，v6]都是权最大的边，去掉其中的一条，比如说[v4，v6]，这时得到一个不含圈的图，如图6-18（b）所示，即最小树。

关于破圈法的正确性证明略去。