V4 o V5 图7 如图7的邻接矩阵为 000 01110 0000 001 000 0000 给出了一个图的邻接矩阵就等于给出了图的全部信息,可以从邻接矩 阵中得到图的很多重要性质。如 (1)A=(a)中第i行中的1的数目等于v点的出次dt(v),第j列中 的数目等于v点的入次d(v) (2)路径问题。如果图7是路径图,则由邻接矩阵就可算出G中任 点与其它点之间是否有路可通?若有路,走几步可以达到该点? 下面通过邻接矩阵的计算来求解v→vs和v-→V6有无路可能 先求A2 011000011000011010 001000001000010010 0 00100100 0011101 A 010001010001|001010 101011011 0000101000010010101 其中a=∑aa 可以理解aia=1时,当且仅当a和aj同时等于1,所以ana=1表 示从v到v有一条路,而A2=an42)则表示从v到v可两步到达
25 v2 v4 v3 v5 图 7 如图 7 的邻接矩阵为 = 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 A 给出了一个图的邻接矩阵就等于给出了图的全部信息，可以从邻接矩 阵中得到图的很多重要性质。如 （1）A=(aij)中第 i 行中的 1 的数目等于 vi 点的出次 d + (vi)，第 j 列中 1 的数目等于 vi 点的入次 d - (vi)。 （2）路径问题。如果图 7 是路径图，则由邻接矩阵就可算出 G 中任 一点与其它点之间是否有路可通？若有路，走几步可以达到该点？ 下面通过邻接矩阵的计算来求解 v1→v5 和 v1→v6有无路可能。 先求 A2 = = = 0 1 0 1 0 1 0 1 1 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 2 (2) A aij 其中 = = 6 1 (2) i ai j aik akj 。 可以理解 ai1a1j=1 时，当且仅当 ai1 和 a1j 同时等于 1，所以 ai1a1j=1 表 示从 vi 到 vj 有一条路，而 A2=aij(2)则表示从 vi到 vj 可两步到达。 v v6 1
a12}=1,说明v到ⅴs有一条路,可两步到达。 a162)=0,表明v到v6两步不能到达。继续计算A3 0000 21021 A3=A2.A 021121 01101 由于a163)=1,表明从ⅵ三步可达v6,若要了解这条路沿途经过哪些顶 点到达v6,只要回溯前面计算过程中的a16③这个数是怎样产生的,就可知 道。因为a163是由A2中的第一行与A中的第六列相应各数乘加而得,即 是由a152)=1和a6=1相乘而得。同理a1s2=1是由a1=1与aBs=1相乘而得。 因此有v→v3→s→v6。 §2.树与最小树 、树及其性质 连通且不含圈的无向图称为树,记为T(V,E) 设图T=(VE,顶点数为P,边数为q,则以下关于树的说法是等价的 1T是一棵树; 2T无圈,且qp-1; 3T连通,且q=p-1 4T无圈,但每加一新边即得唯一的一个圈: 5T连通,但每舍去一边就不连通 6T中任意两点,有唯一链相连。 、图的生成树 若图G的生成子图是一棵树,则称该树为G的生成树
26 a15(2)=1，说明 v1到 v5有一条路，可两步到达。 a16(2)=0，表明 v1到 v6两步不能到达。继续计算 A3 = = = 0 1 1 0 1 1 0 2 1 1 2 1 0 2 0 1 1 1 0 2 1 0 2 1 0 1 1 1 0 1 0 2 1 1 1 1 ( ) 3 2 (3) A A A aij 由于 a16(3)=1，表明从 v1 三步可达 v6，若要了解这条路沿途经过哪些顶 点到达 v6，只要回溯前面计算过程中的 a16(3)这个数是怎样产生的，就可知 道。因为 a16(3)是由 A2 中的第一行与 A 中的第六列相应各数乘加而得，即 是由 a15(2)=1 和 a56=1 相乘而得。同理 a15(2)=1 是由 a13=1 与 a35=1 相乘而得。 因此有 v1→v3→v5→v6。 §2. 树与最小树 一、树及其性质 连通且不含圈的无向图称为树，记为 T(V,E)。 设图 T=(V,E)，顶点数为 P，边数为 q，则以下关于树的说法是等价的。 1.T 是一棵树； 2.T 无圈，且 q=p－1； 3.T 连通，且 q=p－1； 4.T 无圈，但每加一新边即得唯一的一个圈； 5.T 连通，但每舍去一边就不连通； 6.T 中任意两点，有唯一链相连。 二、图的生成树 若图 G 的生成子图是一棵树，则称该树为 G 的生成树
图8 图8中(b)就是(a)的生成树。 图G=(VE)有生成树的充要条件是G为连通图 三、最小树问题 在给定连通赋权无向图G=(V,E,W)中,求G的生成树T=(VE),使E 各边权WC0)的总和最小的问题称为最小树问题。其数学模型为: W(T=min > w (v,v)∈T 其中T*称为最小树。 许多网络问题都可归结为最小树问题,如设计长度最小的公路网把若 干城市联通;设计用料最省的电话线网把有关单位联系起来。求最小树有 以下两种方法: (1)用“避圈法”(Kπ rusal算法)求最小树。其基本思想是:开始选 条权最小的边,以后每步从未选的边中选取一条权最小的边,使它与已选 边不构成圈,直至选够q-1条边止 (2)用“破圈法”(管梅谷算法)求最小树。其方法步骤是: 1°先从图G任取一个圈,并从圈中去掉一条权最大的边。若在同 圈中有几条都是权最大边,则任选其中一边去掉。 2°在余下的子圈中,重复上述步骤,直至没有圈止。 例
27 (a) (b) 图 8 图 8 中(b)就是(a)的生成树。 图 G=(V,E)有生成树的充要条件是 G 为连通图。 三、最小树问题 在给定连通赋权无向图 G=(V,E,W)中，求 G 的生成树 T=(V,E)，使 E 各边权 Wij(0)的总和最小的问题称为最小树问题。其数学模型为： W T = min Wij ( ) * (vi,vj)T 其中 T*称为最小树。 许多网络问题都可归结为最小树问题，如设计长度最小的公路网把若 干城市联通；设计用料最省的电话线网把有关单位联系起来。求最小树有 以下两种方法： （1）用“避圈法”(Kruskal 算法)求最小树。其基本思想是：开始选一 条权最小的边，以后每步从未选的边中选取一条权最小的边，使它与已选 边不构成圈，直至选够 q－1 条边止。 （2）用“破圈法”(管梅谷算法)求最小树。其方法步骤是： 1°先从图 G 任取一个圈，并从圈中去掉一条权最大的边。若在同一 圈中有几条都是权最大边，则任选其中一边去掉。 2°在余下的子圈中，重复上述步骤，直至没有圈止。 例 ° ° ° ° ° ° ° ° ° e1 l1 l6 e6 l7 e7 e2 e4 l2 e3
§3.最短路问题 最短路问题是网络理论中应用最广泛的问题之一,许多优化问题可以 使用这个模型,如管道铺设,设备更新,线路安排等。在第三章我们曾介 绍了最短路问题的动态规划解法,但某些最短路的问题构造动态规划基本 方程较困难,而图论方法则直观有效 给定D=(V,A,W),其中w∈W,表示弧(v,v)的权(可以是费用、时间 距离等)。设ⅴ和v是D中任意两顶点,求一条路,使它是从ⅴ到v的 所有路中总权最小的路。其数学模型为: W(P)=mn∑W (v,v)∈P W」≥0情况下,求最短路的 Di jkstra标号法 1该法的基本思想是基于以下原理:若序列{v,v,…vk,…v}是从w到 vt的最短路,则序列{vs,wi,…Vk}必为从vs到vk的最短路。 2 Dijkstra标号法的基本思想是采用两种标号:T标号与P标号,T标 号为临时性标号( Temporary Label,P标号为永久性标号( Permanent labe 从v开始,逐步向外探寻最短路。给ⅵ点P标号时,表示从v到ⅵ点的最 短路权,ⅵ的标号不再改变。给v点T标号时,表示从vs到w点的最短路 权上界的估计。凡没有得到P标号的点都有T标号。标号法每一步都是把 某一T标号点改为P标号,当终点vt得到P标号时,计算全部结束。如果 点ⅴ不能由T标号变为P标号,则说明ws到v不存在路 3.步骤: (1)给v以P标号,P(ⅴ)=0,其余各点给T标号,且T(v)=+ (2)若v点为刚得到P标号的点,考虑T标号点v(v,v)∈A。对v的T 标号进行如下的更改 T(vimin(T(v), P(vi)+wii (4.1)
28 §3. 最短路问题 最短路问题是网络理论中应用最广泛的问题之一，许多优化问题可以 使用这个模型，如管道铺设，设备更新，线路安排等。在第三章我们曾介 绍了最短路问题的动态规划解法，但某些最短路的问题构造动态规划基本 方程较困难，而图论方法则直观有效。 给定 D=(V,A,W)，其中 wijW，表示弧(vi,vj)的权（可以是费用、时间、 距离等）。设 vs 和 vt 是 D 中任意两顶点，求一条路，使它是从 vs 到 vt 的 所有路中总权最小的路。其数学模型为： W P = min Wij ( ) * (vi,vj)P 一、Wij0 情况下，求最短路的 Dijkstra 标号法 1.该法的基本思想是基于以下原理：若序列{vs,vi1,…vik,…vt}是从 vs 到 vt 的最短路，则序列{vs,vi1,…vik}必为从 vs 到 vik的最短路。 2.Dijkstra 标号法的基本思想是采用两种标号：T 标号与 P 标号，T 标 号为临时性标号(Temporary Label)，P 标号为永久性标号(Permanent Label)。 从 vs 开始，逐步向外探寻最短路。给 vi 点 P 标号时，表示从 vs 到 vi 点的最 短路权，vi 的标号不再改变。给 vi 点 T 标号时，表示从 vs 到 vi 点的最短路 权上界的估计。凡没有得到 P 标号的点都有 T 标号。标号法每一步都是把 某一 T 标号点改为 P 标号，当终点 vt 得到 P 标号时，计算全部结束。如果 点 vj 不能由 T 标号变为 P 标号，则说明 vs 到 vj 不存在路。 3.步骤： (1)给 vs 以 P 标号，P(vs)=0，其余各点给 T 标号，且 T(vi)=+。 (2)若 vi 点为刚得到 P 标号的点，考虑 T 标号点 vj,(vi,vj)A。对 vj 的 T 标号进行如下的更改： T(vj)=min{T(vj),P(vi)+wij} (4.1)
(3)比较所有具有T标号点,把最小者改为P标号,即 P(vjo=min T(vi) 为T标号 若全部点均为P标号。则停止。否则以v代v,返回(2) 例,用 Dijkstra标号法求下图由v到各顶点的最短路。 (图9) 解:标号过程如图10中(a)-(e),其中方框表示P标号,里面的数字 表示从v到该点的最短路长。圆圈表示T标号,其中的数字表示从v到该 点最短路长的上界 (a)P(v1)=0,T(v2)=1 (b)P(v)=0,P(v2)1 T(v3)=4 T(v3)=3,T(4)=4 (c)P(v1)=0,T(v2)=1 (dP(vl)=0,P(v2)=1 P(V3)=3,T(V4)=4 P(v3)=3,P(
29 (3)比较所有具有 T 标号点，把最小者改为 P 标号，即 P(vjo)=min{T(vj)} vj 为 T 标号 若全部点均为 P 标号。则停止。否则以 vjo 代 vi，返回(2) 例，用 Dijkstra 标号法求下图由 v1 到各顶点的最短路。 v2 v5 v1 v3 v6 （图 9） 解：标号过程如图 10 中(a)－(e)，其中方框表示 P 标号，里面的数字 表示从 v1 到该点的最短路长。圆圈表示 T 标号，其中的数字表示从 v1 到该 点最短路长的上界。 v2 + v2 + v1 v1 v3 + v3 + (a) P(v1)=0,T(v2)=1 (b)P(v1)=0,P(v2)=1 T(v3)=4 T(v3)=3,T(v4)=4 v2 + v2 + v1 v1 v3 v6 v3 v6 (c) P(v1)=0,T(v2)=1 (d)P(v1)=0,P(v2)=1 P(v3)=3,T(v4)=4 P(v3)=3,P(v4)=4 ° ° ° ° ° ° 2 3 3 2 1 1 1 2 4 2