第四部分图与网络分析（书第六部分） 图论是运筹学的一个分支，己广泛应用于物理学、化学、控制论、信息论、管理科学、电子计算机 等各个领域。在实际生活、生产和科学研究中，有很多问题可以用图论的理论和方法来解决。例如，在 组织生产中，为完成某项生产任务，各工序之间之间怎样衔接，才能使生产任务完成得又快有好。邮递 员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按怎样的路线走，所走的路线最短。 再例如，各种通信网络的合理架设，交通网络的合理分布等问题，应用图论的方法求解都很简便。 下面是著名的哥尼斯堡七桥问题（图见书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 = 。 最短路问题不仅可以直接应用于解决如管道铺设、线路安排、厂区布局、设备更新等问题，而且经 常被作为基本工具，用于经济其他优化问题
6.3.2最短路算法 1.所有w≥0时的Dijkstra法 基本思想：从V,出发，逐步向外探寻最短路，最终得到v,到每个点V,的最短路。 对每个点v,标号： 临时标号：T标号(T(v),(v)》一T(y)表示当前得到的v,到v,的路的权，(v)表示该路上位 于v,之间的点。若当前没有y,到v,的路，则记(T(v),(y,)》=(o,M)。 永久标号：P标号(P(y),(v)一P(v)表示v,到v,的最短路的权，(y)表示该最短路上位于 V,之间的点。 在每一步：将具有最小T标号的点改为P标号，并修改其他点的T标号，直到所有点的标号都为P 标号。记S:为第k步具有P标号的点的集合。 有向图的Dijkstra法： 1.初始步。(P(v),(v)=(0y),S={y},对每个v,∈V\{y,}, (wg,y),(y,y)∈A Te,h,》=✉，M.)eA 令=0。 2.终止判别。若S=V,则停止，对每个y,∈V，d(心，y,)=P(y,),并且用“反向跟踪”得到v,到 V,的最短路为： y,=y)→y=v)→。。→Vh=(y)→v%=(y,)→y, 否则，转3。 3.确定永久标号。令T(y,)=minT(v),则(P(y),(y)=(T(y),(y),即将点y,的临时标号改 为永久标号，S1=SsU{y}。 4.修改临时标号。考察每个(，y,)∈A并且y,ES1的点V,若T(y,)>P(y,)+w,则令 (T(y,2(y)=(P(y)+w,y,) 令k=+1,转2。 例6.3.1书P261图10-18可在图上作业。 定理6.3.1(Dijkstra法的正确性)对每个v,∈S,P(v,)是y,到y,的最短路的权，即 d(y,y)=P(v)。 证明：对k进行归纳。=O时显然正确。设对k=n结论成立，即对每个v,∈Sn,d(v,y,)=P(y)。 现在考察k=+1。因为Sn=SnU{y,},其中T(y,)=minT(v,),故只要证明d(v,y,)=P(y)=T(y,)。 在D中任取一条从y,到y的路H,只要证明w(H)≥T(y:)。 为清晰起见，第n步时的T标号记为T(y)。因为y,∈Sn,y,生Sn，故从y,出发沿H必存在一条 弧，其始点属于Sn而终点不属于Sn。设(v,y)是H中第一条这样的弧，H=(v,…,,,…,y),其
6 6.3.2 最短路算法 1．所有 0 wij ≥ 时的 Dijkstra 法 基本思想：从 s v 出发，逐步向外探寻最短路，最终得到 s v 到每个点 j v 的最短路。 对每个点 j v 标号： 临时标号：T 标号( ( ), ( )) Tv v j j λ —— ( ) T vj 表示当前得到的 s v 到 j v 的路的权， ( )j λ v 表示该路上位 于 j v 之间的点。若当前没有 s v 到 j v 的路，则记( ( ), ( )) ( , ) Tv v M j j λ = ∞ 。 永久标号：P 标号( ( ), ( )) Pv v j j λ —— ( ) P vj 表示 s v 到 j v 的最短路的权， ( )j λ v 表示该最短路上位于 j v 之间的点。 在每一步：将具有最小 T 标号的点改为 P 标号，并修改其他点的 T 标号，直到所有点的标号都为 P 标号。记 k S 为第 k 步具有 P 标号的点的集合。 有向图的 Dijkstra 法： 1． 初始步。( ( ), ( )) (0, ) Pv v v s λ s s = ， 0 { }s S v = ，对每个 \{ } j s v Vv ∈ ， ( , ), ( , ) ( ( ), ( )) ( , ), ( , ) sj s s j j j s j w v vv A Tv v M vv A λ ⎧⎪ ∈ = ⎨ ⎪ ∞ ∉ ⎩ 令 k=0。 2． 终止判别。若 k S V= ，则停止，对每个 j v V∈ ， (, ) () s j j dv v Pv = ，并且用“反向跟踪”得到 s v 到 j v 的最短路为： ( )l s j v v = λ → 1 ( ) l l j j v v λ − = → 。。。→ 2 1 ( ) j j v v = λ → 1 ( ) j j v v = λ → j v 否则，转 3。 3． 确定永久标号。令 ( ) min ( ) j k i j v S Tv Tv ∉ = ，则 ( ( ), ( )) ( ( ), ( )) Pv v Tv v ii ii λ = λ ，即将点 i v 的临时标号改 为永久标号， 1 { } k ki S Sv + = ∪ 。 4． 修改临时标号。考察每个(, ) i j vv A ∈ 并且 j k 1 v S ∉ + 的点 j v ，若 ( ) () Tv Pv w j i ij > + ，则令 ( ( ), ( )) ( ( ) , ) Tv v Pv w v j j i ij i λ = + 令 k=k+1，转 2。 例 6.3.1 书 P261 图 10-18 可在图上作业。 定 理 6.3.1(Dijkstra 法的正确性 ) 对每个 j k v S ∈ ， ( ) P vj 是 s v 到 j v 的最短路的权，即 (, ) () s j j dv v Pv = 。 证明：对 k 进行归纳。k=0 时显然正确。设对 k=n 结论成立，即对每个 j n v S ∈ ， (, ) () s j j dv v Pv = 。 现在考察 k=n+1。因为 1 { } n ni S Sv + = ∪ ，其中 ( ) min ( ) j n i j v S Tv Tv ∉ = ，故只要证明 (,) () () s iii dv v Pv Tv = = 。 在 D 中任取一条从 s v 到 i v 的路 H，只要证明 ( ) () wH Tv ≥ i 。 为清晰起见，第 n 步时的 T 标号记为 ( ) T v n j 。因为 s n v S ∈ ， i n v S ∉ ，故从 s v 出发沿 H 必存在一条 弧，其始点属于 n S 而终点不属于 n S 。设(,) r l v v 是 H 中第一条这样的弧， (, ,,, ,) H v vv v = s " " rl i ，其
中，…，y,∈Sn,y,是Sn，则w(H)=w(y,…,y,)+w,+1w(y,…,y)，由归纳假设， P(y,)=d(y,y)≤w(y,…,y,)，故w(H)=P(,)+w1+1w(y,…,y)。由算法知， P(y,)+w1≥Tn(y)≥Tn(y),故w(H)=T(y)+w(y,…,y)≥Tn(y)。因此，k=t1时结论也成立。 由归纳法知Dijkstra法是正确的。 对于赋权无向图G=(,E,W,边[y,V,]可视为两条弧(y,v)和(y,,),并且W,=",因此同样 可求出某点v,到每个点V,的最短链，算法类似于原算法。 无向图的Dijkstra法： 1.初始步。(P(y),(y》=(0,y),S={,},对每个y,∈八{y}, (Wsv,),[v,V ]EE (T(y,y,》= (co,M),[v,,v,]eE 令=0。 2.终止判别。若S=V，则停止，对每个y,∈V,d(y,y)=P(y,),并且用“反向跟踪”得到y,到 V,的最短链为： V,=(v)一V=(v)一。。一v2=(V)一V=(y,)-y 否则，转3。 3.确定永久标号。令T(g)=minT(v),则(P(,),2(:)》=(T(),(y,》,即将点y的临时标号改为 永久标号，S1=SUy}。 4.修改临时标号。考察每个[y,y,]∈E并且v,生S1的点y,若T(y,)>P(y,)+W,则令 (T(v),(v)=(P(y)+wy) 令k=k+1,转2。 例6.3.2书P264图10-19图上标出。 注6.3.1 dijkstra法只适用于所有w≥0的赋权图。当赋权图中存在负权时，则算法失效。如图10-20。 2.存在1
7 中 1, , r n v vS " ∈ ， l n v S ∉ ， 则 ( ) (, , ) (, ,) wH wv v w wv v = s " " r rl l i + + ，由归纳假设， () (, ) (, , ) Pv dv v wv v r sr s r = ≤ " ， 故 ( ) () (, ,) wH Pv w wv v = r rl l i + + " 。由算法知， () () () Pv w T v T v r rl n l n i +≥ ≥ ，故 ( ) () (, ,) () wH T v wv v T v = ni l i ni + ≥ " 。因此，k=n+1 时结论也成立。 由归纳法知 Dijkstra 法是正确的。 对于赋权无向图 G=(V,E,W)，边[, ] i j v v 可视为两条弧(, ) i j v v 和(,) j i v v ，并且 w w i j ji = ，因此同样 可求出某点 s v 到每个点 j v 的最短链，算法类似于原算法。 无向图的 Dijkstra 法： 1． 初始步。( ( ), ( )) (0, ) Pv v v s λ s s = ， 0 { }s S v = ，对每个 \{ } j s vVv ∈ ， ( , ), [ , ] ( ( ), ( )) ( , ), [ , ] sj s s j j j s j w v vv E Tv v M vv E λ ⎧⎪ ∈ = ⎨ ⎪ ∞ ∉ ⎩ 令 k=0。 2． 终止判别。若 k S V= ，则停止，对每个 j v V∈ ， (, ) () s j j dv v Pv = ，并且用“反向跟踪”得到 s v 到 j v 的最短链为： ( )l s j v v = λ — 1 ( ) l l j j v v λ − = — 。。。— 2 1 ( ) j j v v = λ — 1 ( ) j j v v = λ — j v 否则，转 3。 3． 确定永久标号。令 ( ) min ( ) j k i j v S Tv Tv ∉ = ，则( ( ), ( )) ( ( ), ( )) Pv v Tv v ii ii λ = λ ，即将点 i v 的临时标号改为 永久标号， 1 { } k ki S Sv + = ∪ 。 4． 修改临时标号。考察每个[, ] i j vv E ∈ 并且 j k 1 v S ∉ + 的点 j v ，若 ( ) () Tv Pv w j i ij > + ，则令 ( ( ), ( )) ( ( ) , ) Tv v Pv w v j j i ij i λ = + 令 k=k+1，转 2。 例 6.3.2 书 P264 图 10-19 图上标出。 注6.3.1 dijkstra法只适用于所有 0 wij ≥ 的赋权图。当赋权图中存在负权时，则算法失效。如图10-20。 2．存在 0 wij < 时的函数迭代法 对有向赋权图 D=(V,A,W)，不妨设任意两点 ,i j vv V∈ 之间都有弧（如果在 D 中，(, ) i j vv A ∉ ，则 添加弧(, ) i j v v ，并且 wij = +∞ ） 利用如下结论：如 P 是 D 中从 s v 到 j v 的最短路， i v 是 P 中的一个点，则从 s v 沿 P 到 i v 的路是 D 中从 s v 到 i v 的最短路。设 1 {, , } Vv v = " p ，得到关系式： ( , ) min{ ( , ) }, 1, , s j s i ij i dv v dv v w j p = += " 函数迭代法： 对 t=1： 1 ( , ) , 1, , s j sj dvv w j p = = " 对 t=2,3,…： 1 ( , ) min{ ( , ) }, 1, , t t s j s i ij i dvv d vv w j p − = += " （记下最优解）
直到d(y,)=d-(y,y,y,∈V,则d(y,y)是y,到y,的最短路的权。 例6.3.3书P266图10-21用表格表示。 定义6.3.1设D是赋权有向图，C是D中的一个回路。若C的权w(C)<0,则称C是D的负回路。 不难证明： 1.d(",y)是在最多包含-1个中间点的限制条件下，从y,到v,的最短路。 2.如果D是不含负回路的赋权有向图，则从V,到任一点的最短路必定是初等路，从而最多包含pD)-2 个中间点。这时，一定有dP(y,y)=d-(y,y),y,∈V。 3.如果存在某个v,∈V,使dP(y,y,)≠dP-(v,v),则D一定含负回路，这时显然v,到v,的路的权 无下界。 为加快速度，可用迭代公式： 对=1： d'(y,yj)=wg,j=1…,p t=2,3...:d'(vv)=min(min{d'(v,v)+wi),minfd(vV)+wi,j=1,p 直到d(y,y)=d-(y,y),y,∈V,则d*(y,,)是y,到y,的最短路的权。 或： 对=1： d'(y,y)=wg,j=1,…,p 对=2,4，：d'(y,y)=mind(v,y,ind'(y)+"y,j=l…,p 对=3,5.：d'(v,v)=min{d(y,v),min{d'(y,y)+wn}},j=p,…,1 直到d(y,y)=d-(y,y,y,∈V,则d(y,y)是y,到y,的最短路的权。 6.3.3应用举例 例6.3.4设备更新问题)书P267例13 §6.4网络最大流问题 许多系统包含了流量问题。例如，公路系统中的车辆流，控制系统中的信息流，供水系统中的水流， 金融系统中的现金流，等等。 例如，书P269图10-23，是联结某产品产地y到销点V。的交通网，弧(y,V)上的数字表示y,到v,这 条运输线的最大通过能力。产品交通网从y运到v。现在要求制定一个运输方案，使从y运到y。的产品 数量最多。 6.4.1基本概念和基本定理 1.网络与流 定义6.4.1给定有向图D=(V,A),在V中指定一个点为发点（记作y,),另一个点为收点（记作y,), 其余点为中间点。对于每一条弧(，y)∈A,对应有一个数C,≥0，称为弧(y,y,)的容量。把这种有 向图D称为网络，记作D=(V,A,C)
8 直到 1 ( , ) ( , ), k k sj sj j d vv d vv v V − = ∀∈ ，则 (, ) k s j d vv 是 s v 到 j v 的最短路的权。 例 6.3.3 书 P266 图 10-21 用表格表示。 定义 6.3.1 设 D 是赋权有向图，C 是 D 中的一个回路。若 C 的权 w(C) = += " 直到 1 ( , ) ( , ), k k sj sj j d vv d vv v V − = ∀∈ ，则 (, ) k s j d vv 是 s v 到 j v 的最短路的权。 6.3.3 应用举例 例 6.3.4(设备更新问题) 书 P267 例 13 §6.4 网络最大流问题 许多系统包含了流量问题。例如，公路系统中的车辆流，控制系统中的信息流，供水系统中的水流， 金融系统中的现金流，等等。 例如，书 P269 图 10-23，是联结某产品产地 1 v 到销点 6 v 的交通网，弧(, ) i j v v 上的数字表示 i v 到 j v 这 条运输线的最大通过能力。产品交通网从 1 v 运到 6 v 。现在要求制定一个运输方案，使从 1 v 运到 6 v 的产品 数量最多。 6.4.1 基本概念和基本定理 1．网络与流 定义 6.4.1 给定有向图 D=(V,A)，在 V 中指定一个点为发点（记作 s v ），另一个点为收点（记作 t v ）， 其余点为中间点。对于每一条弧 (, ) i j vv A ∈ ，对应有一个数 0 ij c ≥ ，称为弧 (, ) i j v v 的容量。把这种有 向图 D 称为网络，记作 D=(V,A,C)
定义6.4.2给定网络D=(VA,C)。若对于每一条弧(，V)∈A,有一个数f,则称f={∫}为D 的流。 定义6.4.3给定网络D=(V,A,C),∫={∫}为D的流。若f满足： (1)容量限制条件：对每条弧(，y)∈A,有0≤∫≤C: (2)平衡条件： 对于每个中间点y,(≠s,):∑=∑f元 j(v)EA j)EA 对于发点y,:f)=∑，-∑f j)EA (v,)e4 对于收点：-)=∑，-∑ j(VV)EA J(V )EA 则称∫={f}是D的可行流，并且称(0为∫的流量。 例如，书P269图10-24。 对于网络D=(V,A,C),可行流总是存在的，例如f={f=0}(称为零流)，记作0，其流量为(=0。 设∫={f}为D=(V,A,C)的可行流。若∫=C,则称弧（化，'）为饱和弧，否则称为非饱和弧。若 ∫=0，则称弧(，y)为零弧，否则称为非零弧。 定义6.4.4给定网络D=(V,A,C),∫={f}为D的可行流。(0是D的所有可行流中流量最大的可 行流，则称∫={}为D的最大流。 数学模型： max v(f) s1.0≤f≤cg,(,",)eA ∑-∑f。=0,i≠s,1 j试，)EA j(vj)EA ，-∑je) j)EA (,,EA ∑f-∑fn=-f) j)EA F(Y,)E4 2.增广链 设4是网络D=(VA,C)中联结”，与y,的链，定义4的方向是从V,到y,则链上的弧有两类： 前向弧：弧的方向与链的方向一致，前向弧的全体记作： 反向弧：弧的方向与链的方向相反，反向弧的全体记作！。 例如，书P269图10-24 对4=(，2，，4，，V6),={,2),(2,),(,4),(,6)}，={,4)}。 定义6.4.5设4是网络D=(V,A,C)中联结y,与y,的链，和4分别是前向弧的全体和反向弧的全 体。若 f0,(y,y)∈ 9
9 定义 6.4.2 给定网络 D=(V,A,C)。若对于每一条弧(, ) i j vv A ∈ ，有一个数 ij f ，则称 { }ij f = f 为 D 的流。 定义 6.4.3 给定网络 D=(V,A,C)， { }ij f = f 为 D 的流。若 f 满足： （1） 容量限制条件：对每条弧(, ) i j vv A ∈ ，有0 ij ij ≤ f ≤ c ； （2） 平衡条件： 对于每个中间点 ( ,) i v i st ≠ ： :( , ) :( , ) i j ji ij ji jvv A jv v A f f ∈ ∈ ∑ ∑ = 对于发点 s v ： :( , ) :( , ) ( ) s j js sj js jvv A jv v A vf f f ∈ ∈ = − ∑ ∑ 对于收点 t v ： :( , ) :( , ) ( ) t j jt tj jt jvv A jv v A vf f f ∈ ∈ −= − ∑ ∑ 则称 { }ij f = f 是 D 的可行流，并且称 v(f)为 f 的流量。 例如，书 P269 图 10-24。 对于网络 D=(V,A,C)，可行流总是存在的，例如 { 0} ij f f = = （称为零流），记作 f=0，其流量为 v(f)=0。 设 { }ij f = f 为 D=(V,A,C)的可行流。若 ij ij f = c ，则称弧(, ) i j v v 为饱和弧，否则称为非饱和弧。若 0 ij f = ，则称弧(, ) i j v v 为零弧，否则称为非零弧。 定义 6.4.4 给定网络 D=(V,A,C)， { }ij f = f 为 D 的可行流。v(f)是 D 的所有可行流中流量最大的可 行流，则称 { }ij f = f 为 D 的最大流。 数学模型： :( , ) :( , ) :( , ) :( , ) :( , ) :( , ) max ( ) . . 0 , ( , ) 0, , ( ) ( ) i j ji s j js t j jt ij ij i j ij ji jvv A jv v A sj js jvv A jv v A tj jt jvv A jv v A v f st f c v v A f f i st f f vf f f vf ∈ ∈ ∈ ∈ ∈ ∈ ≤≤∀ ∈ − = ∀≠ − = − =− ∑ ∑ ∑ ∑ ∑ ∑ 2．增广链 设 μ 是网络 D=(V,A,C)中联结 s v 与 t v 的链，定义 μ 的方向是从 s v 到 t v ，则链上的弧有两类： 前向弧：弧的方向与链的方向一致，前向弧的全体记作 μ+ ； 反向弧：弧的方向与链的方向相反，反向弧的全体记作 μ− 。 例如，书 P269 图 10-24 对 123456 μ = (, , , , , ) vvvvvv ， 12 23 34 56 μ {( , ),( , ),( , ),( , )} vv vv vv vv + = ， 5 4 μ {( , )} v v − = 。 定义 6.4.5 设 μ 是网络 D=(V,A,C)中联结 s v 与 t v 的链，μ+ 和 μ− 分别是前向弧的全体和反向弧的全 体。若 ,(, ) ij ij i j f c vv μ+ ∀ ∈
则称4是（关于D的增广链。 例如，书P269图10-244=(1,2，y3,V4,V,6)为增广链。 定理6.4.1若可行流f为最大流，则D中不存在关于f的增广链。 证明：否则，设4是关于∫的增广链，令 0=min-人i. (E 则0>0。令f'=(f,4,),即 f+0,(vv,)Eu f写=f-6,(,y)∈业 , (,y)E4 则f是可行流，并且v(f")=(f)+日>v(f),与f为最大流矛盾。因此，D中不存在关于f的增广链。 4.截集和集量 定义6.4.6设S,TcV,SUT=V,S∩T=0,v,∈S,y,∈T,则 (S,T)={,y)∈A|y,eS,y,∈T} 称为（分离V,y,的）截集。 显然，若把某一截集的弧从网络中删去，则就不存在V,到y,的路。所以，直观上说，截集是从y,到 y,的必经之道。 定义6.4.7设(S,T)为（分离y,,的）截集，则 cS,T)=∑cg (vE(S.T) 称为截集(S,T)的截量。 可证明：对任一可行流f和任一截集(S,T),有v()≤c(S,T)。 若存在可行流∫和截集(S,T),使v(f)=c(S,T),则∫为最大流，而(S,T)是D的所有截集中截 量最小的截集，称为最小截集。 定理6.4.2设f为D的可行流，若D中不存在关于f的增广链，则∫为最大流。 证明：只要找到截集(S,T),使v(f)=c(S,T)即可。利用下面方法构造S: 令v,∈S: 若，∈S,0,则令v,∈S。 因为不存在关于∫的增广链，故y,S。令T=V八S,则(S,T)为截集，并且 cm,(,y)∈(S,T) (,y,)e(T,S) 由此知v(f)=c(S,T)。因此，f为最大流。 最大流量最小截量定理：任一网络D中，从V,到y,的最大流的流量等于分离y,y,的最小截集的截 10
10 则称 μ 是（关于 f）的增广链。 例如，书 P269 图 10-24 123456 μ = (, , , , , ) vvvvvv 为增广链。 定理 6.4.1 若可行流 f 为最大流，则 D 中不存在关于 f 的增广链。 证明：否则，设 μ 是关于 f 的增广链，令 (, ) (, ) min{ min ( ), min } ij ij ij ij ij vv vv cf f μ μ θ + − ∈ ∈ = − 则θ > 0。令 f f ′ = (,,) μ θ ，即 , ( , ) , ( , ) , ( , ) ij i j ij ij i j ij i j f vv f f vv f vv θ μ θ μ μ + − ⎧ + ∈ ⎪⎪ ′ =− ∈ ⎨ ⎪ ∉ ⎪⎩ 则 f ‘ 是可行流，并且vf vf vf ( ) () () ′ = +> θ ，与 f 为最大流矛盾。因此，D 中不存在关于 f 的增广链。 4． 截集和集量 定义 6.4.6 设 ST V , ⊂ ， STV ∪ = ， S T ∩ = ∅ ， , s t v Sv T ∈ ∈ ，则 ( , ) {( , ) | , } ij i j ST v v Av Sv T = ∈ ∈∈ 称为（分离 ,s t v v 的）截集。 显然，若把某一截集的弧从网络中删去，则就不存在 s v 到 t v 的路。所以，直观上说，截集是从 s v 到 t v 的必经之道。 定义 6.4.7 设(, ) S T 为（分离 ,s t v v 的）截集，则 ( , )(, ) (, ) i j ij v v ST cST c ∈ = ∑ 称为截集(, ) S T 的截量。 可证明：对任一可行流 f 和任一截集(, ) S T ，有v f cST () (, ) ≤ 。 若存在可行流 f 和截集(, ) S T ，使v f cST () (, ) = ，则 f 为最大流，而(, ) S T 是 D 的所有截集中截 量最小的截集，称为最小截集。 定理 6.4.2 设 f 为 D 的可行流，若 D 中不存在关于 f 的增广链，则 f 为最大流。 证明：只要找到截集(, ) S T ，使v f cST () (, ) = 即可。利用下面方法构造 S ： 令 s v S ∈ ； 若 i v S ∈ ， ij ij f ，则令 j v S ∈ 。 因为不存在关于 f * 的增广链，故 t v S ∉ 。令T VS = \ ，则(, ) S T 为截集，并且 , ( , ) ( , ) 0, ( , ) ( , ) ij i j ij i j c v v ST f vv TS ⎧⎪ ∈ = ⎨ ⎪ ∈ ⎩ 由此知v f cST () (, ) = 。因此，f 为最大流。 最大流量最小截量定理：任一网络 D 中，从 s v 到 t v 的最大流的流量等于分离 ,s t v v 的最小截集的截