最小树及求解方法的优化方案

在无向图中,权数总和(以下简称总权)最小的树称为最小支撑树,简称最小树。例如,在图6-9中,图6-9(b)就是图6-9(a)的一个树,若总权最小,则为最小支撑树。关于最小树的求解方法有两种:破圈法和避圈法。

图6-9 无向图和树

(1)破圈法。

步骤:①任取一圈,去掉权数最大的边;②重复步骤①,直至获得最小树。

(2)避圈法。

避圈法又称加边法,求解步骤为:①将图中的边按权数从小到大排序;②画出图中所有点;③从小到大依次加边且不能生成圈,直到获得最小树。

注意:在同一个赋权图中,最小树可能不唯一,但最小树的总权数是唯一的。

【例6-3】如图6-10所示,点S,A,B,C,D,E,T分别代表村镇名字,村镇之间的连线上赋予的权值表示距离。现需要沿图6-10中的连线架设电线,向各村镇输送电量,问:如何架设电线,才能使电线总长最短?

图6-10

解:

在现行方案中,电线总长46。现在的任务是改进方案,既要完成输电任务,又要使电线总长最短。

(1)破圈法求解。

①对于圈ABSA,去掉权最大的边BS,如图6-11所示。

图6-11

②对于圈ABCSA,去掉权最大的边CS,如图6-12所示。

图6-12

③对于圈ABDA,去掉权最大的边AD,如图6-13所示。

图6-13

④对于圈BECB,去掉权最大的边CE,如图6-14所示。

(www.xing528.com)

图6-14

⑤对于圈BDEB,去掉权最大的边BD,如图6-15所示。

图6-15

⑥对于圈DTED,去掉权最大的边ET,如图6-16所示。此时已获得最小树(无圈连通),总权最小为14(2＋2＋1＋3＋1＋5＝14)。该方案与初始方案相比,电线总长减少了32。

图6-16

(2)避圈法求解。

①首先将图6-10中的边按权数从小到大排序。

[C,B](1),[D,E](1),[A,B](2),[A,S](2),[B,E](3),[C,E](4),[C,S](4),[B,S](5),[B,D](5),[D,T](5),[A,D](7),[T,E](7)。

②画出图6-10中所有点,如图6-17所示。

图6-17

③加边CB和DE(权为1),如图6-18所示。

图6-18

④加边AB和AS(权为2),如图6-19所示。

图6-19

⑤加边BE(权为3),如图6-20所示。

图6-20

⑥若加边CE和CS(权为4),则构成圈CEBC和圈SABCS,因此不能加边CE和CS。

⑦加边DT(权为5),即获得最小树,如图6-16所示。

注意:若加边BS和BD(权为5),则构成圈ASBA和圈BDEB;若加边AD和TE(权为7),则构成圈ADEBA和圈DTED。