表示出各点之间的数量关系。 定义6.2.4设T=(V,E)是赋权图G=(V,E,的支撑树。T中所有边上的权之和称为T的权，记作w(TD, 即w(T)=∑wg。 [v.v,leE 定义6.2.5设T*=(V,E)是赋权图G=(V,E,W的支撑树。若w(T*)是G的所有支撑树中权最小的支撑 树，即w(T)=minw(T),则称T*为G的最小支撑树。 求最小支撑树方法： 避圈法：开始选一条权最小的边，以后每一步中，在与己选边不构成圈的所有边中选权最小的边。 显然，选择的边数为p(G)-1。 例6.2.2P260图10-17，用避圈法求其最小支撑树。 证明方法的正确性：设由避圈法得到的支撑树为T=(V,E),不妨设E'={e,e2,…,e},=pG)l, 并且e第一选入，e2第二选入，。，ek最后选入，故州，≤"2≤…≤"：。假设T不是G的最小支撑树， 设H是G的所有最小支撑树中与T的公共边数最多的最小支撑树。因H不同于T,故T中存在不属于H 的边，设e,是第一个不属于H的边(1≤i≤k),把e,放入H中，则得到唯一一个圈，记作C。因T中不 含圈，故C中一定有不属于T的边，设为e。在H中放入e,去掉e,则得到G的另一支撑树T。。显然， w(T)=w(H)+w(e,)-w(e),由H是G的最小支撑树知w(e,)≥w(e)。根据算法，e,是使 (V,{e,e2,…,e1,e,)不含圈的权最小的边，而(W,{e,e2,…,e-1,e)也不含圈，故w(e,)≤w(e),由此 得w(e)=w(e),故w(T)=w(H)+w(e,)-w(e)=w(H),即T也是G的最小支撑树。又T与T的公 共边数比H与T的公共边数多一条，与H的选择矛盾。因此，T是G的最小支撑树。 破圈法：开始时任选一个圈，从圈中去掉权最大的边。以后每一步中，在余下的图中任选一个圈， 从圈中去掉权最大的边。显然，去掉的边数为q(G)p(G)十1。 例6.2.3P260图10-17，用破圈法求其最小支撑树。 §6.3最短路问题 6.3.1引例 已知如图10-18（书261）所示的单行线交通图，每弧旁的数字表示通过这条单行线的费用，现在 某人要从？出发，通过该交通网到'。，求使总费用最小的路线。（与动态规划区别：这里没有固定的阶 段数) 条路线的总费用就是y到的路上所以弧旁的数字之和，此路可以不是初等路。例如从”出发， 依次经过，，6，，4,6，，最后到达g,则该路的总费用为47个单位。 般最短路问题：给定赋权有向图D=(V,A,W,即每条(y,V,)相应地有权w,又指定D中两个点V, 和y,。设P是D中从y,到y,的路，则P中所有弧上的权之和称为P的权，记作w(P)。若P是所有从V, 到y,的路中权最小的路，即w(P)=minw(P),则称P为y,到y,的最短路，并且记d(y,y,)=w(P)。 显然，不一定有d(v,y,)=d(,V)。 最短路问题不仅可以直接应用于解决如管道铺设、线路安排、厂区布局、设备更新等问题，而且经 常被作为基本工具，用于经济其他优化问题。5 表示出各点之间的数量关系。 定义 6.2.4 设 T=(V,E’)是赋权图 G=(V,E,W)的支撑树。T 中所有边上的权之和称为 T 的权，记作 w(T)， 即 [, ] ' ( ) i j ij vv E wT w ∈ = ∑ 。 定义 6.2.5 设 T*=(V,E’)是赋权图 G=(V,E,W)的支撑树。若 w(T*)是 G 的所有支撑树中权最小的支撑 树，即 * ( ) min ( ) T wT wT = ，则称 T*为 G 的最小支撑树。 求最小支撑树方法： 避圈法：开始选一条权最小的边，以后每一步中，在与已选边不构成圈的所有边中选权最小的边。 显然，选择的边数为 p(G)-1。 例 6.2.2 P260 图 10-17，用避圈法求其最小支撑树。 证明方法的正确性：设由避圈法得到的支撑树为 T=(V,E’)，不妨设 1 2 ' {, , , } E ee e = " k ， k=p(G)-1， 并且 1e 第一选入， 2 e 第二选入，。。。， k e 最后选入，故 ww w 1 2 ≤ ≤ ≤ " k 。假设 T 不是 G 的最小支撑树， 设 H 是 G 的所有最小支撑树中与 T 的公共边数最多的最小支撑树。因 H 不同于 T，故 T 中存在不属于 H 的边，设 i e 是第一个不属于 H 的边(1≤ ≤i k )，把 i e 放入 H 中，则得到唯一一个圈，记作 C。因 T 中不 含圈，故 C 中一定有不属于 T 的边，设为 e。在 H 中放入 i e 去掉 e，则得到 G 的另一支撑树T0 。显然， 0 ( ) ( ) ( ) () wT wH we we = +− i ，由 H 是 G 的最小支撑树知 ( ) () we we i ≥ 。根据算法， i e 是使 12 1 ( ,{ , , , , }) V ee e e " i i − 不含圈的权最小的边，而 12 1 ( ,{ , , , , }) V ee e e " i− 也不含圈，故 ( ) () we we i ≤ ，由此 得 ( ) () we we i = ，故 0 ( ) ( ) ( ) () ( ) wT wH we we wH = + −= i ，即T0 也是 G 的最小支撑树。又T0 与 T 的公 共边数比 H 与 T 的公共边数多一条，与 H 的选择矛盾。因此，T 是 G 的最小支撑树。 破圈法：开始时任选一个圈，从圈中去掉权最大的边。以后每一步中，在余下的图中任选一个圈， 从圈中去掉权最大的边。显然，去掉的边数为 q(G)- p(G)+1。 例 6.2.3 P260 图 10-17，用破圈法求其最小支撑树。 §6.3 最短路问题 6.3.1 引例 已知如图 10-18（书 P261）所示的单行线交通图，每弧旁的数字表示通过这条单行线的费用，现在 某人要从 1 v 出发，通过该交通网到 8 v ，求使总费用最小的路线。（与动态规划区别：这里没有固定的阶 段数） 一条路线的总费用就是 1 v 到 8 v 的路上所以弧旁的数字之和，此路可以不是初等路。例如从 1 v 出发， 依次经过 3365467 vvvvvvv ,,,,,, ，最后到达 8 v ，则该路的总费用为 47 个单位。 一般最短路问题：给定赋权有向图 D=(V,A,W)，即每条(, ) i j v v 相应地有权 wij ，又指定 D 中两个点 s v 和 t v 。设 P 是 D 中从 s v 到 t v 的路，则 P 中所有弧上的权之和称为 P 的权，记作 w(P)。若 P* 是所有从 s v 到 t v 的路中权最小的路，即 * ( ) min ( ) P wP wP = ，则称 P* 为 s v 到 t v 的最短路，并且记 * (,) ( ) s t dv v wP = 。 显然，不一定有 (,) (, ) s t ts dv v dv v = 。 最短路问题不仅可以直接应用于解决如管道铺设、线路安排、厂区布局、设备更新等问题，而且经 常被作为基本工具，用于经济其他优化问题