1、第四章第四章 图与路径规划图与路径规划图与网络的基本知识图与网络的基本知识树树最短路问题最短路问题网络最大流问题网络最大流问题q18世纪，哥尼斯堡城中有一世纪，哥尼斯堡城中有一条河叫普雷格尔河，河中有条河叫普雷格尔河，河中有两个小岛，河上有七座桥。两个小岛，河上有七座桥。q问题：问题：q一个散步者能否走过七座桥，一个散步者能否走过七座桥，且每座桥只走过一次，最后回且每座桥只走过一次，最后回到出发点？到出发点？哥尼斯堡七桥问题哥尼斯堡七桥问题q1736年，欧拉年，欧拉“依据几何位置依据几何位置的解题方法的解题方法”将此问题归结为将此问题归结为图图10-1(b)的一笔画问题。的一笔画问题。图图10
2、-1(b)图图10-1(a)q能否从某一点开始一笔画出这能否从某一点开始一笔画出这个图形，最后回到原点，而不个图形，最后回到原点，而不重复？重复？q基本概念基本概念q定义定义1 1一个一个图图是由点集是由点集V=vi和和V中元素的无序对的一个集中元素的无序对的一个集合合E=ek所构成的二元组，记为所构成的二元组，记为G=(V,E)，V中的元素中的元素vi叫做叫做顶点，顶点，E中的元素中的元素ek叫做边叫做边(无向边无向边)。1图与网络的基本知识图与网络的基本知识无向图无向图q定义定义11一个一个有向图有向图是由点集是由点集V=vi和和V中元素的有序对的一中元素的有序对的一个集合个集合A=ek所
3、构成的二元组，记为所构成的二元组，记为D=(V,A)，V中的元素中的元素vi叫做顶点，叫做顶点，A中的元素中的元素ek叫做弧叫做弧(有向边有向边)。e4e2e1e3e5e6v1v2v3v4v5G=(V,E)，V=v1,v2,v3,v4,v5，E=e1,e2,e3,e4,e5,e6，其中，其中e1=v1,v1，e2=v1,v2，e3=v1,v3，e4=v2,v3，e5=v2,v3，e6=v3,v4。记号：记号：m(G)=|V|表示图表示图G的顶点数，的顶点数，n(G)=|E|表示图表示图G的边数。的边数。环环多重边多重边悬挂点悬挂点悬挂边悬挂边孤立点孤立点q基本概念基本概念(续续)q定义定义2
4、2不含环和多重边的图称为不含环和多重边的图称为简单图简单图，含有多重边的图，含有多重边的图称为称为多重图多重图。(a)(b)(c)(d)q定义定义3 3每一对顶点都有边相连的无向简每一对顶点都有边相连的无向简单图称为单图称为完全图完全图。有。有n个顶点的无向完全个顶点的无向完全图记作图记作Kn。q有向完全图是指每一对顶点间有且仅有一有向完全图是指每一对顶点间有且仅有一条有向边的简单图。条有向边的简单图。q定义定义4 4图图G=(V,E)的点集的点集V可以分为两个可以分为两个非空子集非空子集X，Y，即，即X Y=V，X Y=，使得使得E中的每一条边的两个端点必有一端中的每一条边的两个端点必有一端
5、点属于点属于X，另一端点属于，另一端点属于Y，则称，则称G为二部为二部图图(偶图偶图)，有时另记作，有时另记作G=(X,Y,E)。v1v2v3v4v5v6v1v3v2v4q顶点的次顶点的次q定义定义5 5以点以点v为端点的边数叫做为端点的边数叫做点点v的的次次，记作，记作deg(v)，简记为，简记为d(v)。q定理定理1 1任何图中，顶点次数的总和任何图中，顶点次数的总和等于边数的等于边数的2倍。倍。由于每条边必与两个顶点关联，在计由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的所以顶点次数的总和等于边数的2倍。倍
6、。q定理定理2 2任何图中，次为奇数的顶点必为偶数个。任何图中，次为奇数的顶点必为偶数个。证明证明 设设V1和和V2分别表示图分别表示图G中奇点与偶点的集合中奇点与偶点的集合(V1 V2=V)由定理由定理1知，知，e4e2e1e3e5e6v1v2v3v4v5 mvdvdvdVvVvVv221 2m为偶数，为偶数，2Vvvd是若干个偶数之和，亦为偶数，是若干个偶数之和，亦为偶数，1Vvvd所以，所以，必为偶数，即必为偶数，即|V1|为偶数。为偶数。q有向图顶点的次有向图顶点的次q定义定义6 6有向图中，以点有向图中，以点v为始点的边数称为点为始点的边数称为点v的的出次出次，用，用d+(v)表示，
7、以点表示，以点v为终点的边数称为点为终点的边数称为点v的的入次入次，用，用d-(v)表示。表示。v点的出次与入次之和就是该点的次。点的出次与入次之和就是该点的次。q有向图中，所有顶点的入次之和等于所有顶点的出次之和。有向图中，所有顶点的入次之和等于所有顶点的出次之和。q子图子图q定义定义7 7图图G=(V,E)，若，若E是是E的子集，的子集，V是是V的子集，且的子集，且E中的边仅与中的边仅与V中的顶点相关联，则称中的顶点相关联，则称G=(V,E)是是G的的子图子图。特别，若特别，若V=V，则，则G称为称为G的的生成子图生成子图(支撑子图支撑子图)。q网络网络q点或边带有某种数量指标的图称为网络
8、。点或边带有某种数量指标的图称为网络。4692q定义定义8 8无向图无向图G=(V,E)，若图，若图G中某些点与边的交替中某些点与边的交替序列可以排列成序列可以排列成连通图连通图 kkkiiiiiiivevevev,12110 的形式，的形式，且且 tttiiivve,1 ，则称这个点边序列为连接，则称这个点边序列为连接kiivv 与0的一条的一条链链(道路道路)，链长为，链长为k。点边列中没有重复的点和重复的边者为点边列中没有重复的点和重复的边者为初等链初等链。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10S=v6,e6,v5,e7,v1,e8,v5,e7,v1,e9,v
9、4,e4,v3S1=v6,e6,v5,e5,v4,e4,v3q定义定义9 9无向图无向图G中，连接中，连接kiivv 与0的一条链，当的一条链，当kiivv 与0是同一个点时，称此链为是同一个点时，称此链为圈圈(回路回路)。圈中既无重复点圈中既无重复点也无重复边者为也无重复边者为初等圈初等圈。S2=v1,e7,v5,e8,v1,e9,v4,e10,v2,e2,v1S3=v1,e2,v2,e10,v4,e5,v5,e6,v6,e1,v1q定义定义1010一个图中任意两点间至少有一条链相连，则一个图中任意两点间至少有一条链相连，则称此图为称此图为连通图连通图。任何一个不连通图都可以分为若干任何一个
10、不连通图都可以分为若干个连通子图，每一个称为原图的一个个连通子图，每一个称为原图的一个分图分图。q定义定义1111网络网络(赋权赋权图图)G=(V,E)，其边，其边vi,vj有权有权wij,构构造矩阵造矩阵A=(aij)nxn，其中：，其中：图的矩阵表示图的矩阵表示 其他0,Evvwajiijij称矩阵称矩阵A为网络为网络G的的权矩阵权矩阵。v1v2v3v4v5938672445 0650760844580320430974290Aq定义定义1212对于图对于图G=(V,E)，|V|=n，构造矩阵，构造矩阵A=(aij)nxn，其中：其中：其他0,1Evvajiij称矩阵称矩阵A为图为图G的的
11、邻接矩阵邻接矩阵。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10q定义定义1212连通连通图图G中，若存在一条道路，中，若存在一条道路，经过每边一次且仅一次，则称这条路为经过每边一次且仅一次，则称这条路为欧拉道路欧拉道路。若存在一条回路，经过每边。若存在一条回路，经过每边一次且仅一次，则称这条回路为一次且仅一次，则称这条回路为欧拉回欧拉回路路。q具有欧拉回路的图称为具有欧拉回路的图称为欧拉图欧拉图(E(E图图)。欧拉回路与道路欧拉回路与道路图论中的欧拉定理图论中的欧拉定理q定理定理3 3无向连通图无向连通图G G是欧拉图，当且仅当是欧拉图，当且仅当G G中无奇点。中无奇点。
12、证明证明必要性：无向连通图必要性：无向连通图G G是欧拉图是欧拉图 G G中无奇点中无奇点 G是欧拉图，则存在一条回路，经由是欧拉图，则存在一条回路，经由G中所有的边，中所有的边，在这条回路上，顶点可能重复出现，但边不重复。在这条回路上，顶点可能重复出现，但边不重复。对于图中的任一顶点对于图中的任一顶点v v，只要在回路中出现一次，只要在回路中出现一次，必关联两条边，即这条回路沿一边进入该点，再沿另一必关联两条边，即这条回路沿一边进入该点，再沿另一边离开该点。边离开该点。所以所以v点虽然可在回路中重复出现，但点虽然可在回路中重复出现，但deg(v)必为必为偶数。偶数。充分性：充分性：G中无奇点
13、中无奇点 G是欧拉图是欧拉图G中无奇点，从任一点出发，如从中无奇点，从任一点出发，如从v1点出发，经关点出发，经关联边联边e1 “进入进入”v2,由于由于v2是偶点，则必可由是偶点，则必可由v2经关联经关联边进入另一点边进入另一点v3,如此继续，每边仅取一次。如此继续，每边仅取一次。由于由于G图中点数有限，则必可走回图中点数有限，则必可走回v1,得到一条回得到一条回路路c1。1)若回路若回路c1经过经过G G的所有边，则的所有边，则c1就是欧拉回路。就是欧拉回路。2)若否，从若否，从G中去掉中去掉c1后得到子图后得到子图G，则，则G中每个中每个顶点的次仍为偶数。顶点的次仍为偶数。因为图因为图G
14、 G是连通的，所以是连通的，所以c1与与G至少有一个顶点至少有一个顶点vi重合，在图重合，在图G中从中从vi出发，重复出发，重复c1的方法，得到回路的方法，得到回路c2。把把c1与与c2组合在一起，如果恰是图组合在一起，如果恰是图G,则得到欧拉则得到欧拉回路。回路。否则重复否则重复2)可得回路可得回路c3,如此继续如此继续由于图由于图G中边数有限，最终可得一条经过图中边数有限，最终可得一条经过图G所有所有边的回路，即欧拉回路。边的回路，即欧拉回路。欧拉定理充分性欧拉定理充分性(续续)q 推论推论1 1无向连通图无向连通图G G是欧拉图，当且仅当是欧拉图，当且仅当G G的边集可划的边集可划分为若
15、干个初等回路。分为若干个初等回路。q 推论推论2 2无向连通图无向连通图G G有欧拉道路，当且仅当有欧拉道路，当且仅当G G中恰有两中恰有两个奇点。个奇点。欧拉回路与道路欧拉回路与道路(续续)deg(A)=5,deg(B)=deg(C)=deg(D)=3欧拉回路与道路欧拉回路与道路(续续)q定理定理4 4连通有向图连通有向图G G是欧拉图，当且仅当它每是欧拉图，当且仅当它每个顶点的出次等于入次。个顶点的出次等于入次。q连通有向图连通有向图G有欧拉道路，当且仅当这个图中有欧拉道路，当且仅当这个图中除去两个顶点外，其余每个顶点的出次等于入除去两个顶点外，其余每个顶点的出次等于入次，且这两个顶点中，
16、一个顶点的入次比出次次，且这两个顶点中，一个顶点的入次比出次多多1，另一个顶点的入次比出次少，另一个顶点的入次比出次少1。q一个邮递员，负责某一地区的信件投递。他每天要从一个邮递员，负责某一地区的信件投递。他每天要从邮局出发，走遍该地区所有街道再返回邮局，问应如邮局出发，走遍该地区所有街道再返回邮局，问应如何安排送信的路线可使所走的总路程最短？何安排送信的路线可使所走的总路程最短？q图论语言描述：图论语言描述：q给定一个连通图给定一个连通图G，每边有非负权，每边有非负权l(e)，试求一条回路过每，试求一条回路过每边至少一次，且满足总权最小。边至少一次，且满足总权最小。qG无奇点无奇点qG是欧拉
17、图是欧拉图qG有奇点有奇点q在连通图在连通图G=(V,E)中，求一个边集中，求一个边集E1 E，把，把G中属于中属于E1的边均的边均变为二重边得到图变为二重边得到图G*=G+E1，使其满足，使其满足G*无奇点，且无奇点，且中国邮递员问题中国邮递员问题(1962年，管梅谷年，管梅谷)最小。11EeelELq定理定理5 5已知图已知图G*=G+E1无奇点，则无奇点，则 奇偶点图上作业法奇偶点图上作业法 11EeelEL最小的充分必要条件为：最小的充分必要条件为：1)每条边最多重复一次；每条边最多重复一次；2)2)对图对图G中每个初等圈来讲，重复边的长度和不超过中每个初等圈来讲，重复边的长度和不超过
18、圈长的一半。圈长的一半。求解中国邮递员问题实例求解中国邮递员问题实例v1v2v3v4v5v6v7v8v9559624444433v1v2v3v4v5v6v7v8v9559624444433v1v2v3v4v5v6v7v8v9559624444433v1v2v3v4v5v6v7v8v9559624444433奇点两两配对奇点两两配对每对选一条路每对选一条路检查图中每个初等检查图中每个初等圈是否满足定理圈是否满足定理5的条件的条件2，调整圈，调整圈v1,v2,v5,v4,v1调整检查图中每调整检查图中每个初等圈是否满个初等圈是否满足定理足定理5的条件的条件2调整圈调整圈v2,v3,v6,v9,v8
19、,v5,v2q树是图论中结构最简单但又十分重要的图，在自然科树是图论中结构最简单但又十分重要的图，在自然科学和社会的许多领域都有广泛的应用。学和社会的许多领域都有广泛的应用。q举例：举例：q网球比赛抽签后，可用图表示相遇情况。网球比赛抽签后，可用图表示相遇情况。二、树二、树运动员AB CDEFGHIJKLMNq定义定义1414连通连通且不包含圈的无向图称为且不包含圈的无向图称为树树。树中次。树中次为为1的点称为的点称为树叶树叶，次大于，次大于1的点称为的点称为枝点枝点。q定理定理6图图T=(V,E),|V|=n,|E|=m,则下列关于树的说则下列关于树的说法是等价的。法是等价的。1)T是一个树
20、。是一个树。2)T无圈，且无圈，且m=n-1。3)T连通，且连通，且m=n-1。4)T无圈，但每加一新边即得唯一一个圈。无圈，但每加一新边即得唯一一个圈。5)T连通，但任舍去一边就不连通。连通，但任舍去一边就不连通。6)T中任意两点，有唯一链相连。中任意两点，有唯一链相连。树的概念和性质树的概念和性质q1)1)2)2)(T是一个树是一个树T无圈，且无圈，且m=n-1)由树的定义知，由树的定义知，T连通且无圈。往证：连通且无圈。往证：m=n-1。归纳法：当归纳法：当n=2时，显然时，显然m=1，即，即m=n-1。假设假设n=k-1命题成立，即有命题成立，即有k-1个顶点时，个顶点时，T有有k-2
21、条边。条边。当当n=k时，因为时，因为T连通且无圈，连通且无圈，k个顶点中至少有一个点个顶点中至少有一个点u，其次为，其次为1。不妨设不妨设(u,v)为悬挂边。为悬挂边。从从T中去掉中去掉(u,v)，得到图，得到图T，T连通且无圈，为只有连通且无圈，为只有k-1个顶点的树，个顶点的树，从而有从而有k-2条边。条边。故故T有有k-1条边。条边。q2 2)3)3)(T无圈，且无圈，且m=n-1 T连通，且连通，且m=n-1)反证法。设反证法。设T不连通，可以分为不连通，可以分为s个连通分图个连通分图(s 2)，设第，设第i个分图有个分图有ni个顶点，个顶点，ni=n。第第i个分图是树个分图是树(?
22、)，所以有，所以有ni-1条边；条边；s个分图共有总边数为个分图共有总边数为 (ni 1)=n-sn-1，矛盾。，矛盾。树树若干定义的等价性证明若干定义的等价性证明q3)3)4)4)(T连通，且连通，且m=n-1 T无圈，但每加一新边即得唯一一个圈无圈，但每加一新边即得唯一一个圈)反证法。若反证法。若T中有圈中有圈C。可去掉。可去掉C的一边，并不影响的一边，并不影响T的连通性。的连通性。如果剩余图中仍有圈，可继续去掉该圈的一边如果剩余图中仍有圈，可继续去掉该圈的一边。如此继续去掉如此继续去掉k条边条边(k 1)后，得到一个无圈的连通图后，得到一个无圈的连通图T，T有有m-k条边。条边。无圈连通
23、图无圈连通图T是树是树，其顶点个数与，其顶点个数与T相同，所以相同，所以T有有n-1条边。条边。但由但由3)，m-k=n-1-k n-1，矛盾。即，矛盾。即T无圈。无圈。加新边得唯一圈显然。加新边得唯一圈显然。q4 4)5)5)(T无圈，但每加一新边即得唯一一个圈无圈，但每加一新边即得唯一一个圈T连通，但任舍去连通，但任舍去一边就不连通一边就不连通)反证法。若反证法。若T不连通，由连通性的定义知，存在两点不连通，由连通性的定义知，存在两点u,v之间无路可通。之间无路可通。加上一条边也不会形成圈，与加上一条边也不会形成圈，与4)矛盾。矛盾。再证：每舍一边便不连通。再证：每舍一边便不连通。若若T中
24、有一边中有一边(u,v)，其舍去后图，其舍去后图T-(u,v)仍然连通，则仍然连通，则T=T-(u,v)是树，是树，但但T加一边加一边(u,v)后得后得T仍无圈，与仍无圈，与4)矛盾。矛盾。q5 5)6)6)，6 6)1)1)显然显然树树若干定义的等价性证明若干定义的等价性证明(续续)q定义定义1515若若图图G的生成子图是一棵的生成子图是一棵树树，则称该树为，则称该树为G的生成树的生成树(支撑树支撑树)。图。图G的树。的树。图的生成树图的生成树q定理定理7 7图图G=(V,E)有生成树的充分必要条件为有生成树的充分必要条件为G是是连通图。连通图。q寻找连通图的生成树：每步选出一条边使它与已选
25、寻找连通图的生成树：每步选出一条边使它与已选的边不构成圈，直到选够的边不构成圈，直到选够n-1条边为止。条边为止。q步骤：步骤：1)1)在点集在点集V中任取一点中任取一点v，给，给v标以标以0号；号；2)若某点若某点u已得标号已得标号i，检查一端点为，检查一端点为u的各边，另一端是否均的各边，另一端是否均已标号。已标号。3)若有若有(u,w)边的点边的点w未标号，则给未标号，则给w以标号以标号i+1，记下边，记下边(u,w)。令。令w代代u，重复，重复2)；否则，若；否则，若u的邻接点均已标号，的邻接点均已标号，就退到标号为就退到标号为i-1的点的点r，以，以r代代u，重复，重复2)。直到全部
26、点得到。直到全部点得到标号为止。标号为止。构造图的生成树的方法构造图的生成树的方法1：深探法：深探法012345678910111213012345678910111213q步骤：步骤：1)1)在点集在点集V中任取一点中任取一点v，给，给v标以标以0号；所有与号；所有与0号点号点v相邻的相邻的点标以点标以1号点。号点。2)令所有标号为令所有标号为i的点集为的点集为Vi，检查，检查Vi,V-Vi中的边端点是否中的边端点是否均已标号。对所有未标号的点均标以均已标号。对所有未标号的点均标以i+1，记下这些边。，记下这些边。3)对标号对标号i+1的点重复步骤的点重复步骤2)，直到全部点得到标号为止。，
27、直到全部点得到标号为止。构造图的生成树的方法构造图的生成树的方法2：广探法：广探法0121123412223301111222223334q定义定义1616连通连通图图G=(V,E)，每条边，每条边e有非负权有非负权L(e)。一。一棵生成树所有树枝上权的总和，称为该棵生成树所有树枝上权的总和，称为该生成树的权生成树的权。具有最小权的生成树称为具有最小权的生成树称为最小生成树最小生成树(最小支撑树最小支撑树)，简称简称最小树最小树。最小生成树问题最小生成树问题v0v1v2v3v4v5v6v7v81111444423555322v0v1v2v3v4v5v6v7v811112322q基本思想基本思想
28、每步从未选边中选取边每步从未选边中选取边e，使它与已选边，使它与已选边不构成圈，且不构成圈，且e是未选边中的最小权边，直至选够是未选边中的最小权边，直至选够n-1条边为止。条边为止。最小树的最小树的Kruskal 算法算法v0v1v2v3v4v5v6v7v811112322v0v1v2v3v4v5v6v7v81111444423555322q步骤：步骤：1)1)从图从图G任选一棵树任选一棵树T1。2)2)加上一条弦加上一条弦e1 ，T1+e1中即生成一个中即生成一个圈。去掉此圈中的最大圈。去掉此圈中的最大边，得到新树边，得到新树T2。3)以以T2代替代替T1，重复，重复2)再检查剩余的弦，直至
29、全部弦检查完毕再检查剩余的弦，直至全部弦检查完毕为止。为止。破圈法求最小树破圈法求最小树v0v1v2v3v4v5v6v7v81111444423555322v0v1v2v3v4v5v6v7v814445322v0v1v2v3v4v5v6v7v81444532214152351q定理定理8 8 用用Kruskal算法得到的子图是一棵最算法得到的子图是一棵最小树。小树。q定理定理9 9图图G的生成树的生成树T T为最小树，当且仅当对为最小树，当且仅当对任一弦任一弦e来说，来说，e是是T+e中与之对应的圈中与之对应的圈 e 的最大权边。的最大权边。算法依据算法依据q最短路问题是网络理论应用最广泛的问
30、题之一。最短路问题是网络理论应用最广泛的问题之一。q动态规划求解最短路问题的局限性。动态规划求解最短路问题的局限性。三、最短路问题三、最短路问题2511214106104131112396581052C1C3D1AB1B3B2D2EC21314q设设G=(V,E)为连通图，图中各边为连通图，图中各边(vi,vj)有权有权wij(wij=表表示示vi,vj间无边间无边)，vs,vt为图中任意两点，求一条道路为图中任意两点，求一条道路，使它是从使它是从vs到到vt的所有路中总权最小的路。即的所有路中总权最小的路。即最短路问题的一般提法最短路问题的一般提法 jivvijwL,最小。最小。或或记记P是
31、从是从 vs到到 vt的所有路的集合，即的所有路的集合，即 的路到是从tsvvP :求求P0 使使得得 jivvijPPwLL,0minminq基本原理基本原理若序列若序列vs,v1,vn-1,vn，是从是从vs到到vn的的最短路，则序列最短路，则序列vs,v1,vn-1必定必定是从是从vs到到vn-1的最的最短路。短路。q该算法的基本步骤，采用标号法。该算法的基本步骤，采用标号法。qP标号：永久性标号，给点标号：永久性标号，给点vi作作P标号时，表示从标号时，表示从vs到到vi的路最的路最短，短，vi的标号不再改变；的标号不再改变；qT标号：试探性标号，给点标号：试探性标号，给点vi作作T标
32、号时，表示得到从标号时，表示得到从vs到到vi的的最短路权的上界，凡没有得到最短路权的上界，凡没有得到P标号的点都有标号的点都有T标号。标号。q基本思想基本思想从从vs出发，逐步向外探寻最短路。每一步都把某一点的出发，逐步向外探寻最短路。每一步都把某一点的T标号标号改为改为P标号，当终点标号，当终点vt得到得到P标号时，全部计算结束。标号时，全部计算结束。对于有对于有n个顶点的图，最多经个顶点的图，最多经n-1步就可以得到从始点到终点步就可以得到从始点到终点的最短路。的最短路。Dijkstra算法算法1.给给vs以以P标号，标号，P(vs)=0，其余各点均给，其余各点均给T标号，标号，T(vi
33、)=；2.若若vi为刚得到为刚得到P标号的点，考虑这样的点标号的点，考虑这样的点vj：(vi,vj)E，且，且vj为为T标号标号。对。对vj的的T标号进行如下的更改：标号进行如下的更改：T(vj)=minT(vj),P(vi)+wij3.比较所有具有比较所有具有T标号的点，把最小者改为标号的点，把最小者改为P标号，即：标号，即：Dijkstra算法的步骤算法的步骤 jivTvPmin 当存在两个以上最小者时，可同时改为当存在两个以上最小者时，可同时改为P标号。若标号。若全部点均为全部点均为P标号则停止。否则用标号则停止。否则用代替代替vi转回转回2.。ivq求从求从v1点到点到v8点的最短路。
34、点的最短路。Dijkstra算法求解举例算法求解举例v2v4v659v14v3v5v7v86447756541(1)给给v1以以P标号，标号，P(v1)=0，其余各点均给，其余各点均给T标号，标号，T(vi)=+(i=2,3,8)(2)由于边由于边(v1,v2),(v1,v3)属于属于E，且，且v2,v3为为T标号，所以修改这两个点的标标号，所以修改这两个点的标号：号：T(v2)=minT(v2),P(v1)+w12=min+,0+4=4T(v3)=minT(v3),P(v1)+w13=min+,0+6=6(3)比较所有比较所有T标号，标号，T(v2)最小，所以令最小，所以令P(v2)=4。并
35、记录路径。并记录路径(v1,v2)。(4)v2为刚得到为刚得到P标号的点，考察边标号的点，考察边(v2,v4),(v2,v5)的端点的端点v4,v5。T(v4)=minT(v4),P(v2)+w24=min+,4+5=9T(v5)=minT(v5),P(v2)+w25=min+,4+4=8(5)比较所有比较所有T标号，标号，T(v3)最小，所以令最小，所以令P(v3)=6。并记录路径。并记录路径(v1,v3)。(P,0)(T,+)(T,+)(T,+)(T,+)(T,+)(T,+)(T,+)46P98PDijkstra算法求解举例算法求解举例(续续1)(6)考虑点考虑点v3，有，有T(v4)=m
36、inT(v4),P(v3)+w34=min9,6+4=9 T(v5)=minT(v5),P(v3)+w35=min8,6+7=8(7)所有所有T标号中，标号中，T(v5)最小，所以令最小，所以令P(v5)=8。并记录路径。并记录路径(v2,v5)。(8)考虑点考虑点v5，有，有T(v6)=minT(v6),P(v5)+w56=min+,8+5=13T(v7)=minT(v7),P(v5)+w57=min+,8+6=14(9)所有所有T标号中，标号中，T(v4)最小，所以令最小，所以令P(v4)=9。并记录路径。并记录路径(v2,v4)。(10)考虑点考虑点v4，有，有T(v6)=minT(v6
37、),P(v4)+w46=min13,9+9=13T(v7)=minT(v7),P(v4)+w47=min14,9+7=14v2v4v659v14v3v5v7v86447756541(P,0)(T,+)(T,+)(T,+)(T,+)(T,+)(T,+)(T,+)46P98PP1314PDijkstra算法求解举例算法求解举例(续续2)(11)所有所有T标号中，标号中，T(v6)最小，所以令最小，所以令P(v6)=13。并记录路径。并记录路径(v5,v6)。(12)考虑点考虑点v6，有，有T(v7)=minT(v7),P(v6)+w67=min14,13+5=14T(v8)=minT(v8),P(
38、v6)+w68=min+,13+4=17(13)所有所有T标号中，标号中，T(v7)最小，所以令最小，所以令P(v7)=14。并记录路径。并记录路径(v5,v7)。(14)考虑点考虑点v7，有，有T(v8)=minT(v8),P(v7)+w78=min17,14+1=15(15)只有一个只有一个T标号标号T(v8)，令，令P(v8)=15。记录路径。记录路径(v7,v8)，计算结束。，计算结束。最短路为最短路为v1 v2 v5 v7 v8，路长，路长P(v8)=15。v2v4v659v14v3v5v7v86447756541(P,0)(T,+)(T,+)(T,+)(T,+)(T,+)(T,+)
39、(T,+)46P98PP1314PPP17P15q问题问题q下图是一输油管道网，下图是一输油管道网，vs 为起点，为起点，vt 为终点，为终点，v1，v2，v3，v4为中转站，边上的数表示该管道的最大为中转站，边上的数表示该管道的最大输油能力，问应如何安排各管道输油量，才能使从输油能力，问应如何安排各管道输油量，才能使从vs 到到 vt 的总输油量最大？的总输油量最大？4网络最大流问题网络最大流问题1084355631711vsvtv1v2v3v4vsvtv1v2v3v4q定义定义2020设有向连通图设有向连通图D=(V,A)，D的每条弧的每条弧(vi,vj)上有非负数上有非负数cij 称为该
40、弧的称为该弧的容量容量，仅有一个入次为，仅有一个入次为0的点的点vs 称为称为发点发点，一个，一个出次为出次为0的点的点vt 称为称为收点收点，其余点为，其余点为中间点中间点，这样的网络，这样的网络D称为称为容量网络容量网络，记作，记作D=(V,A,C)。q网络上的流，是指定义在弧集合网络上的流，是指定义在弧集合A上的一个函数上的一个函数f=f(vi,vj)，并，并称称f(vi,vj)为弧为弧(vi,vj)上的流量，简记为上的流量，简记为fij q满足下列条件的流满足下列条件的流f=fij称为可行流：称为可行流：1)容量限制条件：对每一弧容量限制条件：对每一弧(vi,vj)A，有，有0 fij
41、 cij 2)平衡条件：平衡条件：对于中间点：流出量对于中间点：流出量=流入量，即对于每个流入量，即对于每个i(i s,t)有有最大流的有关概念最大流的有关概念 AvvkiAvvijikjiff,对于发点：对于发点：fvfAvvsjjs,对于收点：对于收点：fvfAvvkttk,可行流的流量可行流的流量 fv发点的输出量发点的输出量(或或收点的输入量收点的输入量)q最大流问题就是求一个流最大流问题就是求一个流f=fij，使其流量，使其流量v(f)达到最达到最大，并且满足：大，并且满足：最大流问题最大流问题 tifvtsisifvffAvvcfAvvkiAvvijjiijijikji,0 0,0
42、 0,最大流问题的线性规划描述：最大流问题的线性规划描述：AvvffftsiffAvvcftsffvjiijAvvktAvvsjAvvkiAvvijjiijijAvvsjtkjsikjijs,0 00 0),(0 0,.m ma ax x,qf=fij是一可行流是一可行流q饱和弧：饱和弧：fij=cijq非饱和弧：非饱和弧：fij 0q前向弧：若前向弧：若 是网络中联结发点是网络中联结发点vs和收点和收点vt的一条链，该弧的方的一条链，该弧的方向与链的方向一致。向与链的方向一致。前向弧的全体记为前向弧的全体记为+q后向弧：后向弧：弧的方向与链的方向相反。弧的方向与链的方向相反。后向弧的全体记为
43、后向弧的全体记为-q增广链：设增广链：设f是一可行流，是一可行流，是发点是发点vs到收点到收点vt的一条链，的一条链，若若 满足下列条件，称之为一条满足下列条件，称之为一条增广链。增广链。q(vi,vj)+，0 fij cijq(vi,vj)-，0 0，则令，则令 j=min(fji，j)，并给，并给vj以标号以标号(-vi,j)b)若弧若弧(vi,vj)A，且，且fij cij，则令，则令 j=min(cij-fij，i)，并给，并给vj以标号以标号(+vi,j)3)重复重复2)直到收点直到收点vt 被标号或不再有顶点可标号为止。被标号或不再有顶点可标号为止。如果如果vt 得到标号，说明存在
44、一条增广链，转入调整得到标号，说明存在一条增广链，转入调整过程。若过程。若vt 未获得标号，标号过程已无法进行，说未获得标号，标号过程已无法进行，说明明f已是最大流。已是最大流。求最大流的标号算法求最大流的标号算法(续续)2.2.调整过程调整过程1)1)按按vt 及其它点的第一个标号，反向追踪，找出增广链及其它点的第一个标号，反向追踪，找出增广链。令令2)去掉所有标号，回到标号过程，对新的可行流去掉所有标号，回到标号过程，对新的可行流f重新标号。重新标号。jiijjitijjitijijvvfvvfvvff,标号法求最大流实例标号法求最大流实例(标号标号)1)1)给给vs标以标以(,)vsv1
45、v2v3v4v5v6vt(5,5)(4,2)(3,2)(5,2)(3,3)(3,0)(2,2)(2,2)(5,4)(3,3)(4,2)(cij,fij)2)2)检查检查vs 的邻接点的邻接点v1,v2,v3:1)fs2=24，2=min(4-2，)=2，给，给v2 以标号以标号(+vs,2)2)fs3=23，3=min(3-2，)=1，给，给v3 以标号以标号(+vs,1)3)3)检查检查v2 的邻接点的邻接点v5,v6:1)f25=00，1=min(3，2)=2，给，给v1 以标号以标号(-v5,2)5)5)检查检查v1 的邻接点的邻接点v4:1)f14=25，4=min(5-2，2)=2，
46、给，给v4 以标号以标号(+v1,2)vsv1v2v3v4v5v6vt(5,5)(4,2)(3,2)(5,2)(3,3)(3,0)(2,2)(2,2)(5,4)(3,3)(4,2)(cij,fij)(,)(+vs,2)(+vs,1)(+v2,2)(-v5,2)(+v1,2)6)6)检查检查v4 的邻接点的邻接点vt:1)f4t=24，t=min(4-2，2)=2，给，给vt 以标号以标号(+v4,2)(+v4,2)由于由于vt 已得标号，增广链存在，标号过程结束。进已得标号，增广链存在，标号过程结束。进入调整过程。入调整过程。标号法求最大流实例标号法求最大流实例(调整调整)vsv1v2v3v4
47、v5v6vt(5,5)(4,2)(3,2)(5,2)(3,3)(3,0)(2,2)(2,2)(5,4)(3,3)(4,2)(cij,fij)(,)(+vs,2)(+vs,1)(+v2,2)(-v5,2)(+v1,2)(+v4,2)7)7)令令=t=2 为调整量，从为调整量，从vt 开始反向追踪，找出增广链开始反向追踪，找出增广链，按标号，按标号(+v4,2)找到找到v4，令，令.244 ttff8)8)再由再由v4 的的标号标号(+v1,2)找到找到v1，令，令.21414 ff9)9)由由v1 的的标号标号(-v5,2)找到找到v5，令，令.21515 ff10)10)由由v5 的的标号标号
48、(+v2,2)找到找到v2，令，令.22525 ff11)11)由由v2 的的标号标号(+vs,2)找到找到vs，令，令.222 ssff标号法求最大流实例标号法求最大流实例(重新标号重新标号)1)1)给给vs标以标以(,)vsv1v2v3v4v5v6vt(5,5)(4,4)(3,2)(5,4)(3,1)(3,2)(2,2)(2,2)(5,4)(3,3)(4,4)(cij,fij)2)2)检查检查vs 的邻接点的邻接点v3:1)fs3=23，3=min(3-2，)=1，给，给v3 以标号以标号(+vs,1)3)3)检查检查vs，v3 的邻接点的邻接点v1,v2,v6:都不满足标号条件，都不满足
49、标号条件，标号过程无法继续，而此时标号过程无法继续，而此时vt 点未得标号。点未得标号。4)v(f*)=fs1+fs2+fs3=f4t+f5t+f6t=11，即为最大流量。，即为最大流量。(,)(+vs,1)3*,vvVss ttvvvvvvV,65421*6321*,vvvvvvVVssts q网络从发点到收点的各通道中，由容量决定网络从发点到收点的各通道中，由容量决定其通过能力，最小割则是这些路的咽喉部分其通过能力，最小割则是这些路的咽喉部分(瓶颈瓶颈)，其容量最小，它决定了整个网络的，其容量最小，它决定了整个网络的通过能力。通过能力。q要提高整个网络的运输能力，必须首先改造要提高整个网络的运输能力，必须首先改造瓶颈的通过能力。瓶颈的通过能力。最小割的意义最小割的意义
