第四部分图与网络分析（书第六部分） 图论是运筹学的一个分支，己广泛应用于物理学、化学、控制论、信息论、管理科学、电子计算机 等各个领域。在实际生活、生产和科学研究中，有很多问题可以用图论的理论和方法来解决。例如，在 组织生产中，为完成某项生产任务，各工序之间之间怎样衔接，才能使生产任务完成得又快有好。邮递 员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按怎样的路线走，所走的路线最短。 再例如，各种通信网络的合理架设，交通网络的合理分布等问题，应用图论的方法求解都很简便。 下面是著名的哥尼斯堡七桥问题（图见书P251)。当时那里的人民热衷于这样的问题：一个散步者 能否走过七座桥，并且每座桥只走过一次，最后回到出发点。 1736年欧拉将此问题归结为图形的一笔画问题（图见书P251):能否从某有点出发，不重复地一笔 画出此图形，最后回到出发点。欧拉证明了此图形是不可能一笔画的，因为只有每个点都与偶数条线关 联的图形才能一笔画。这是图论方面的第一篇论文。 第六章图与网络优化（书第10章) §6.1图的基本概念 在实际生活中，人们为了反映一些对象之间的关系，常常在纸上用点和线画出各种各样的示意图。 例如：铁路图，电话线分布图，比赛情况图。 例6.1.1某单位储存八种化学药品，其中某些药品是不能存放在一个库房的。为了反映这个情况， 可以用点，，g分别表示这八种药品，若药品不能与y放一起，则在与y之间画一条连线，如图 (书p252)。 可见，可以用由点和点与点之间的线所构成的图，反映实际生活种某些对象之间的某种特定的关系。 图：由点和连线组成，其中 点：表示研究的对象： 连线：表示两个对象之间的特定关系。 注6.1.1在一般情况下，图中点之间的相对位置，连线的长短曲直，对于反映对象之间的关系并 不重要。 6.1.1无向图 若图中反映的对象之间的关系具有对称性（即与y有关系，则y与也有关系），则这时的图称 为无向图，或简称图。对象之间的关系用不带箭头的连线表示，称为边。 无向图记作G=-(V,E),:点的集合，E:边的集合。连接点V,y,∈V的边记作e=[y,v,]或[y,]。 无向图G=(V,E)中点和边的个数分别记作p(G)和q(G)。 对无向图G=(V,E)(如图P253,10-7): 若边e=[y,y]∈E,则称y,v,是e的端点，V,V,相邻，e是，v,的关联边。 若e=[y,y]eE,则称e是环。 若两个点之间有多于一条的边，称这些边是多重边。 一个无环无多重边的图称为简单图：一个无环但有多重边的图称为多重图。以后说到无向图，若无 特别说明，均指简单图。 设v∈V,则v的关联边的个数称为v的次，记作dc(v),或简记d(v)。若d(v)=l,称v为悬挂点
1 第四部分 图与网络分析（书第六部分） 图论是运筹学的一个分支，已广泛应用于物理学、化学、控制论、信息论、管理科学、电子计算机 等各个领域。在实际生活、生产和科学研究中，有很多问题可以用图论的理论和方法来解决。例如，在 组织生产中，为完成某项生产任务，各工序之间之间怎样衔接，才能使生产任务完成得又快有好。邮递 员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按怎样的路线走，所走的路线最短。 再例如，各种通信网络的合理架设，交通网络的合理分布等问题，应用图论的方法求解都很简便。 下面是著名的哥尼斯堡七桥问题（图见书 P251）。当时那里的人民热衷于这样的问题：一个散步者 能否走过七座桥，并且每座桥只走过一次，最后回到出发点。 1736 年欧拉将此问题归结为图形的一笔画问题（图见书 P251）：能否从某有点出发，不重复地一笔 画出此图形，最后回到出发点。欧拉证明了此图形是不可能一笔画的，因为只有每个点都与偶数条线关 联的图形才能一笔画。这是图论方面的第一篇论文。 第六章 图与网络优化（书第 10 章） §6.1 图的基本概念 在实际生活中，人们为了反映一些对象之间的关系，常常在纸上用点和线画出各种各样的示意图。 例如：铁路图，电话线分布图，比赛情况图。 例 6.1.1 某单位储存八种化学药品，其中某些药品是不能存放在一个库房的。为了反映这个情况， 可以用点 v1,…, v8 分别表示这八种药品，若药品 vi 不能与 vj 放一起，则在 vi 与 vj 之间画一条连线，如图 （书 p252）。 可见，可以用由点和点与点之间的线所构成的图，反映实际生活种某些对象之间的某种特定的关系。 图：由点和连线组成，其中 点：表示研究的对象； 连线：表示两个对象之间的特定关系。 注 6.1.1 在一般情况下，图中点之间的相对位置，连线的长短曲直，对于反映对象之间的关系并 不重要。 6.1.1 无向图 若图中反映的对象之间的关系具有对称性（即 vi 与 vj 有关系，则 vj与 vi也有关系），则这时的图称 为无向图，或简称图。对象之间的关系用不带箭头的连线表示，称为边。 无向图记作 G=(V,E)，V：点的集合，E：边的集合。连接点 ,i j vv V∈ 的边记作 [, ] i j e vv = 或[,] j i v v 。 无向图 G=(V,E)中点和边的个数分别记作 p(G)和 q(G)。 对无向图 G=(V,E)（如图 P253,10-7）： 若边 [, ] i j e vv E = ∈ ，则称 ,i j v v 是 e 的端点， ,i j v v 相邻，e 是 ,i j v v 的关联边。 若 [,] i i e vv E = ∈ ，则称 e 是环。 若两个点之间有多于一条的边，称这些边是多重边。 一个无环无多重边的图称为简单图；一个无环但有多重边的图称为多重图。以后说到无向图，若无 特别说明，均指简单图。 设v V∈ ，则 v 的关联边的个数称为 v 的次，记作 ( ) G d v ，或简记 d v( ) 。若 d v( ) =1，称 v 为悬挂点
v的关联边称为悬挂边。若d(v)=O,称v为孤立点。若d(v)为偶数，称v为偶点；若d(v)为奇数，称 v为奇点。 定理6.1.1设G=(V,E)为无向图，则∑d(v)=2q(G)。 定理6.12任一图中，奇点的个数为偶数。 对无向图G=(V,E)(如图P254,10-9): 设（化，，…，eV)是点边交错序列，其中 4,a,…,yy∈'，e=[y4y]…,e=[aya]eE 则称此序列为连结y,y的链，V。,…,称为链的中间点。特别当y=V时称为圈。 设（化，，…，，e,V)是链，若点，，…，y,互不相同，则称此链为初等链：若边 e,…,e互不相同，则称此链为简单链。 设（化，，…，e)是圈，若点4，。，…互不相同，则称此圈为初等圈：若边 e,,互不相同，则称此圈为简单圈。 对于链(，，…，e),在不引起混淆的情况下，可简记为（化，，…，Y-)。 以后说到链（圈），若无特别说明，均指简单链（圈）。 若G中任意两点之间至少存在一条链，则称G为连通图。若G不是连通图，则它的每个连通的部 分称为G的连通分图。 对无向图G=(V,E)(如图P255,10-10): 若图G=(V,E),其中E'cE,称G'是G的支撑子图。 设v∈V,用G-v表示从G中去掉点v及其关联边后得到的图。 6.1.2有向图 若图中反映的对象之间的关系不具有对称性（即：与有关系，则”与不一定有关系），则这时 的图称为有向图，对象之间的关系用带箭头的连线表示，称为弧。 有向图记作D=(V,4),:点的集合，A:弧的集合。从点y,∈V指向y,∈V的弧记作a=(y,v,)。 有向图D=(V,A)中点和弧的个数分别记作p(D)和q(D)。 对有向图G=(V,E)(如图P253,10-8): 若弧a=(y,v,)∈A,则称y,是a的始点，y,是a的终点，弧a从y,指向v,。类似可定义简单有向 图等。 从D中去掉箭头后得到的无向图称为D的基础图，记作G(D)。G(D)的链（圈，等等）称为D的链（圈， 等等)。 设（化，4,2，…，”，ay)是点弧交错序列，其中 ya,a,…,Vy&∈V，a=(a,a…,aa=(yYa)∈A 则称此序列为连结%，y的路，。，…，称为路的中间点。特别当=时称为回路。 设(，a,,…,y,ay4)是路，若点，，，y互不相同，则称此路为初等路：若弧 a,…,4,互不相同，则称此路为简单路。 2
2 v 的关联边称为悬挂边。若 d v( ) =0，称 v 为孤立点。若 d v( ) 为偶数，称 v 为偶点；若 d v( ) 为奇数，称 v 为奇点。 定理 6.1.1 设 G=(V,E)为无向图，则 () 2( ) G v V d v qG ∈ ∑ = 。 定理 6.1.2 任一图中，奇点的个数为偶数。 对无向图 G=(V,E)（如图 P254,10-9）： 设 11 2 1 1 (,, , , , , ) kkk iii i i i vev v e v " − − 是点边交错序列，其中 12 1 ,,, , k k ii i i vv v v V − " ∈ ， 1 12 1 1 [ , ], , [ , ] k kk i ii i i i e vv e v v E − − = " = ∈ 则称此序列为连结 1 , k i i v v 的链， 2 1 , , k i i v v " − 称为链的中间点。特别当 1 k i i v v = 时称为圈。 设 11 2 1 1 (,, , , , , ) kkk iii i i i vev v e v " − − 是链，若点 12 1 ,,, , k k ii i i vv v v " − 互不相同，则称此链为初等链；若边 1 1 , , k i i e e " − 互不相同，则称此链为简单链。 设 11 2 1 11 (,, , , , ,) k k iii i i i vev v e v " − − 是圈，若点 12 1 ,,, k ii i vv v " − 互不相同，则称此圈为初等圈；若边 1 1 , , k i i e e " − 互不相同，则称此圈为简单圈。 对于链 11 2 1 1 (,, , , , , ) kkk iii i i i vev v e v " − − ，在不引起混淆的情况下，可简记为 12 1 (, , , , ) k k ii i i vv v v " − 。 以后说到链（圈），若无特别说明，均指简单链（圈）。 若 G 中任意两点之间至少存在一条链，则称 G 为连通图。若 G 不是连通图，，则它的每个连通的部 分称为 G 的连通分图。 对无向图 G=(V,E)（如图 P255,10-10）： 若图 G’=(V,E’)，其中 E E ' ⊂ ，称 G’是 G 的支撑子图。 设v V∈ ，用 G-v 表示从 G 中去掉点 v 及其关联边后得到的图。 6.1.2 有向图 若图中反映的对象之间的关系不具有对称性（即 vi与 vj 有关系，则 vj与 vi 不一定有关系），则这时 的图称为有向图，对象之间的关系用带箭头的连线表示，称为弧。 有向图记作 D=(V,A)，V：点的集合，A：弧的集合。从点 i v V∈ 指向 j v V∈ 的弧记作 (, ) i j a vv = 。 有向图 D=(V,A)中点和弧的个数分别记作 p(D)和 q(D)。 对有向图 G=(V,E)（如图 P253,10-8）： 若弧 (, ) i j a vv A = ∈ ，则称 i v 是 a 的始点， j v 是 a 的终点，弧 a 从 i v 指向 j v 。类似可定义简单有向 图等。 从 D 中去掉箭头后得到的无向图称为 D 的基础图，记作 G(D)。G(D)的链(圈，等等)称为 D 的链(圈， 等等)。 设 112 1 1 (, , , , , , ) k kk i ii i i i vav v a v " − − 是点弧交错序列，其中 12 1 ,,, , k k ii i i vv v v V − " ∈ ， 1 12 1 1 ( , ), , ( , ) k kk i ii i i i a vv a v v A − − = " = ∈ 则称此序列为连结 1 , k i i v v 的路， 2 1 , , k i i v v " − 称为路的中间点。特别当 1 k i i v v = 时称为回路。 设 112 1 1 (, , , , , , ) k kk i ii i i i vav v a v " − − 是路，若点 12 1 ,,, , k k ii i i vv v v " − 互不相同，则称此路为初等路；若弧 1 1 , , k i i a a " − 互不相同，则称此路为简单路
设（化，a,2,…,-,0,y)是回路，若点，Y,…,.互不相同，则称此回路为初等回路：若弧 4,…,4互不相同，则称此回路为简单回路。 以后说到路（回路），若无特别说明，均指简单路（回路）。 §6.2树 在各种图中，有一类图极其简单但却很有用，这就是树。 6.2.1树及其性质 例62.1有五个城市，要在他们之间架设电话线，要求人两个城市可相互通电话，并且电话线的根 数最少。 定义6.2.1一个无圈的连通图称为树。 定理6.2.1设G-(V,E是树，p(G)≥2，则G至少有两个悬挂点。 证：设P=(化，，…，%)是G中含边数最多的初等链。因p(G)≥2，并且G连通，故链P 中至少存在一条边，故y,y不同。下面证明y,为悬挂点，即d(化，)=1。 否则，d(y)≥2，则存在y≠2，使[y,y]∈E。 若y在链P上，即=，S∈{3，…，，则（心uY4,a,…,八y,)为圈，与G是树矛盾。 若V不在链P上，则（化”，ya…,yy)为初等链，与P是含边数最多的初等链矛盾。 于是，d(y)=1,即v,为悬挂点。 同理可证y为悬挂点。 定理6.2.2设G=(V,E是树的充要条件是，G不含圈，并且q(G)=p(G)-1。 证明：必要性：设G=(V,E)是树，则G不含圈，故只要证明q(G)=p(G)-1。对pG)用归纳法。 p(G=l,2时，显然结论成立。假设对点数≤n的树，结论均成立。 现设p(G)=n+1。由定理6.2.1，G存在悬挂点，不妨设v为G的悬挂点，考虑G-v。显然G-v是 树，p(G-v)=p(G)-1=n,q(G-v)=q(G)-1。由归纳假设，q(G-v)=p(G-v)-1,则 q(G)=p(G)-1。 由归纳法知，结论成立。 充分性：设G=(V,E)不含圈，q(G)=p(G)-1,故只要证明G连通。 (反证法)假设G不连通，设G含有个s≥2连通分图G,…,G,。显然G,…,G,连通并且不含圈， 故G,G都是树.由必要性，gG)=pG)-L1=L.由pG)=之pG,gG)=立gG,) 故gG)=立9G,)=立(pG)-)=立pG,)-5≤pG)-2,与gG)=pG)-1矛盾.因此，G连 通，即G是树。 定理6.2.3G=(V,E)是树的充要条件是，G连通，并且q(G)=p(G)-1。 证明：必要性：设G=(V,E)是树，则G连通，并且由定理6.22知q(G)=p(G)-1。 充分性：设G连通，并且q(G)=p(G)-1,只要证明G不含圈。对p(G用归纳法
3 设 1 12 1 11 (, , , , , ,) k k i ii i i i vav v a v " − − 是回路，若点 12 1 ,,, k ii i vv v " − 互不相同，则称此回路为初等回路；若弧 1 1 , , k i i a a " − 互不相同，则称此回路为简单回路。 以后说到路（回路），若无特别说明，均指简单路（回路）。 §6.2 树 在各种图中，有一类图极其简单但却很有用，这就是树。 6.2.1 树及其性质 例 6.2.1 有五个城市，要在他们之间架设电话线，要求人两个城市可相互通电话，并且电话线的根 数最少。 定义 6.2.1 一个无圈的连通图称为树。 定理 6.2.1 设 G=(V,E)是树， p G() 2 ≥ ，则 G 至少有两个悬挂点。 证：设 12 1 (, , , , ) k k P vv v v ii i i − = " 是 G 中含边数最多的初等链。因 p G() 2 ≥ ，并且 G 连通，故链 P 中至少存在一条边，故 1 , k i i v v 不同。下面证明 1 i v 为悬挂点，即 1 ()1 i d v = 。 否则， 1 ()2 i d v ≥ ，则存在 k 1 2 i i v v + ≠ ，使 1 1 [, ] k i i vv E + ∈ 。 若 k 1 i v + 在链 P 上，即 k s 1 i i v v + = ， s k ∈{3, , } " ，则 112 1 ( ,,,, ,) k ss i ii i i v vv v v + − " 为圈，与 G 是树矛盾。 若 k 1 i v + 不在链 P 上，则 112 1 ( ,,,, ,) k kk i ii i i v vv v v + − " 为初等链，与 P 是含边数最多的初等链矛盾。 于是， 1 ()1 i d v = ，即 1 i v 为悬挂点。 同理可证 k i v 为悬挂点。 定理 6.2.2 设 G=(V,E)是树的充要条件是，G 不含圈，并且 qG pG () ()1 = − 。 证明：必要性：设 G=(V,E)是树，则 G 不含圈，故只要证明 qG pG () ()1 = − 。对 p(G)用归纳法。 p(G)=1,2 时，显然结论成立。假设对点数≤ n 的树，结论均成立。 现设 p() 1 G n = + 。由定理 6.2.1，G 存在悬挂点，不妨设 v 为 G 的悬挂点，考虑 G-v。显然 G-v 是 树 ， p( ) ()1 G v pG n − = −= ， qG v qG ( ) ()1 −= − 。由归纳假设， qG v pG v ( ) ( )1 −= −− ， 则 qG pG () ()1 = − 。 由归纳法知，结论成立。 充分性：设 G=(V,E)不含圈， qG pG () ()1 = − ，故只要证明 G 连通。 (反证法)假设 G 不连通，设 G 含有个 s ≥ 2 连通分图 1, , G G " s 。显然 1, , G G " s 连通并且不含圈， 故 1, , G G " s 都是树，由必要性， ( ) ( ) 1, 1, , i i qG pG i s = −= " 。由 1 () ( ) s i i p G pG = = ∑ ， 1 () ( ) s i i qG qG = = ∑ ， 故 11 1 ( ) ( ) ( ( ) 1) ( ) ( ) 2 ss s ii i ii i qG qG pG pG s pG == = = = − = −≤ − ∑∑ ∑ ，与 qG pG () ()1 = − 矛盾。因此，G 连 通，即 G 是树。 定理 6.2.3 G=(V,E)是树的充要条件是，G 连通，并且 qG pG () ()1 = − 。 证明：必要性：设 G=(V,E)是树，则 G 连通，并且由定理 6.2.2 知qG pG () ()1 = − 。 充分性：设 G 连通，并且 qG pG () ()1 = − ，只要证明 G 不含圈。对 p(G)用归纳法
p(G)=l,2时，显然结论成立。假设点数≤n时，结论均成立。 现设p(G)=n+1。先证明G必有悬挂点。否则d(v)≥2，v∈V,则由定理6.1.1， gG=Σdw≥pG) 与q(G)=p(G)-1矛盾。因此，G必有悬挂点。不妨设v为G的悬挂点，考虑G-v。显然G-v是连通的， 并且p(G-v)=p(G)-1=n,q(G-v)=qG)-1。由q(G)=p(G)-1得q(G-v)=p(G-v)-1, 由归纳假设得G-v不含圈，因此G也不含圈。 由归纳法知，结论成立。 定理6.2.4G=(V,E)是树的充要条件是，G中任意两点之间恰有一条链。 证明：必要性：设G是树。因G连通，故G中任意两点之间一定有链。假若某两点之间有多于一 条的链，则G中就含有圈，与G是树矛盾。 充分性。设G中任意两点之间恰有一条链。则G连通。假若G含圈，则此圈上两点之间就有两条 链，矛盾。 由此定理知： (1)从一个树中去掉任意一条边，则余下的图不连通。因此，在点集合相同的的所有图中，树是含边 数最少的连通图。 (2) 在树中不相邻的两个点之间添上一条边，则恰好得到一个圈。如果再从这个圈中去掉一条边，则 又可以得到一个树。 6.2.2支撑树 定义6.2.2设T=(V,E)是G=(V,E)的支撑子图。若T=(V,E)是树，则称T是G的支撑树。 例P257图10-14 若T=(V,E)是G=(V,E)的支撑树，则T的边数为pG)-1,G中不属于树T的边数为qG)p(G)十1。 定理6.2.5图G有支撑树的充要条件是G连通。 证明：必要性：显然。 充分性（破圈法）：设G连通。若G不含圈，则G本身是树，即G是其自身的支撑树。若G含圈， 任取一个圈，从此圈中去掉一条边，得到G的连通支撑子图G1。若G不含圈，则G是树，即G1是G 的支撑树。若G1含圈，任取一个圈，从此圈中去掉一条边，得到G的连通支撑子图G2。如此经有限次 重复，最终得到G的连通支撑子图G,并且G不含圈，因此G:是G的支撑树。其实，需共去掉qG) pG)十1条边。 例6.2.1书P258,图10-15。 求支撑树的另一方法一避圈法： 在图中任取一条边ei,找一条与e1不构成圈的边e2,再找一条与{el,e2}不构成圈的边ea,如此重 复，直到不能进行为止。其实，只要找p(G)-1条边。 6.2.3最小支撑树 定义6.2.3设G=(V,E)。若G中每条边[，l(或e),相应有一个数w或w),则称G是赋权图，w或 )称为边y,以（或）的权。赋权图记作G=(V,E,W) 根据实际问题的需要，权可以有各种含义，如距离、时间、费用，等等。 赋权图在图的理论及其应用方面有着重要的地位。赋权图不仅指出各个点之间的连接关系，而且还
4 p(G)=1,2 时，显然结论成立。假设点数≤ n 时，结论均成立。 现设 p() 1 G n = + 。先证明 G 必有悬挂点。否则 dv v V ( ) 2, ≥ ∀∈ ，则由定理 6.1.1， 1 ( ) () ( ) 2 v V qG dv pG ∈ = ≥ ∑ 与 qG pG () ()1 = − 矛盾。因此，G 必有悬挂点。不妨设 v 为 G 的悬挂点，考虑 G-v。显然 G-v 是连通的， 并且 p( ) ()1 G v pG n − = −= ， qG v qG ( ) ()1 −= − 。由 qG pG () ()1 = − 得 qG v pG v ( ) ( )1 −= −− ， 由归纳假设得 G-v 不含圈，因此 G 也不含圈。 由归纳法知，结论成立。 定理 6.2.4 G=(V,E)是树的充要条件是，G 中任意两点之间恰有一条链。 证明：必要性：设 G 是树。因 G 连通，故 G 中任意两点之间一定有链。假若某两点之间有多于一 条的链，则 G 中就含有圈，与 G 是树矛盾。 充分性。设 G 中任意两点之间恰有一条链。则 G 连通。假若 G 含圈，则此圈上两点之间就有两条 链，矛盾。 由此定理知： （1） 从一个树中去掉任意一条边，则余下的图不连通。因此，在点集合相同的的所有图中，树是含边 数最少的连通图。 （2） 在树中不相邻的两个点之间添上一条边，则恰好得到一个圈。如果再从这个圈中去掉一条边，则 又可以得到一个树。 6.2.2 支撑树 定义 6.2.2 设 T=(V,E’)是 G=(V,E)的支撑子图。若 T=(V,E’)是树，则称 T 是 G 的支撑树。 例 P257 图 10-14 若 T=(V,E’)是 G=(V,E)的支撑树，则 T 的边数为 p(G)-1，G 中不属于树 T 的边数为 q(G)- p(G)+1。 定理 6.2.5 图 G 有支撑树的充要条件是 G 连通。 证明：必要性：显然。 充分性（破圈法）：设 G 连通。若 G 不含圈，则 G 本身是树，即 G 是其自身的支撑树。若 G 含圈， 任取一个圈，从此圈中去掉一条边，得到 G 的连通支撑子图 G1。若 G1不含圈，则 G1是树，即 G1是 G 的支撑树。若 G1 含圈，任取一个圈，从此圈中去掉一条边，得到 G 的连通支撑子图 G2。如此经有限次 重复，最终得到 G 的连通支撑子图 Gk，并且 Gk不含圈，因此 Gk是 G 的支撑树。其实，需共去掉 q(G)- p(G)+1 条边。 例 6.2.1 书 P258，图 10-15。 求支撑树的另一方法——避圈法： 在图中任取一条边 ei1，找一条与 ei1不构成圈的边 ei2，再找一条与{ei1, ei2}不构成圈的边 ei3，如此重 复，直到不能进行为止。其实，只要找 p(G)-1 条边。 6.2.3 最小支撑树 定义 6.2.3 设 G=(V,E)。若 G 中每条边[vi,vj](或 el)，相应有一个数 wij(或 wl)，则称 G 是赋权图，wij(或 wl)称为边[vi,vj] (或 vl)的权。赋权图记作 G=(V,E,W)。 根据实际问题的需要，权可以有各种含义，如距离、时间、费用，等等。 赋权图在图的理论及其应用方面有着重要的地位。赋权图不仅指出各个点之间的连接关系，而且还
表示出各点之间的数量关系。 定义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 = 。 最短路问题不仅可以直接应用于解决如管道铺设、线路安排、厂区布局、设备更新等问题，而且经 常被作为基本工具，用于经济其他优化问题