数模培训-图论模型

图论模型主讲：费文龙Feiwl.wokufeiwl@数学建模培训.图论模型图论根本概念最短途径算法最小生成树算法遍历性问题二分图与匹配网络流问题关键途径问题系统监控模型着色模型.1、图论的根本概念ABCD哥尼斯堡七桥表示图问题1(哥尼斯堡七桥问题):能否从任一陆地出发经过每座桥恰好一次而回到出发点？.ABDC七桥问题模拟图欧拉指出：假设每块陆地所衔接的桥都是偶数座，那么从任一陆地出发，必能经过每座桥恰好一次而回到出发地..问题2(哈密顿环球游览问题):十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？哈密顿圈〔环球游览游戏〕.问题3(四色问题):对任何一张地图进展着色，两个共同边境的国家染不同的颜色，那么只需求四种颜色就够了.问题4(关键途径问题):一项工程义务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机,都要包括许多工序.这些工序相互约束,只需在某些工序完成之后,一个工序才干开场.即它们之间存在完成的先后次序关系,普通以为这些关系是预知的,而且也可以估计完成每个工序所需求的时间.这时工程指点人员迫切希望了解最少需求多少时间才可以完成整个工程工程,影响工程进度的关键工序是哪几个？.图的定义图论中的“图〞并不是通常意义下的几何图形或物体的外形图,而是以一种笼统的方式来表达一些确定的事物之间的联络的一个数学系统.定义1一个有序二元组(V,E)称为一个图,记为G=(V,E),其中①V称为G的顶点集,V≠,其元素称为顶点或结点,简称点;②E称为G的边集,其元素称为边,它结合V中的两个点,假设这两个点是无序的,那么称该边为无向边,否那么,称为有向边.假设V={v1,v2,…,vn}是有限非空点集,那么称G为有限图或n阶图..假设E的每一条边都是无向边,那么称G为无向图(如图1);假设E的每一条边都是有向边,那么称G为有向图(如图2);否那么,称G为混合图.图1图2并且常记V={v1,v2,…,vn},|V|=n;E={e1,e2,…,em}(ek=vivj),|E|=m.称点vi,vj为边vivj的端点.在有向图中,称点vi,vj分别为边vivj的始点和终点.该图称为(n,m)图.对于一个图G=(V,E),人们常用图形来表示它,称其为图解.凡是有向边,在图解上都用箭头标明其方向.例如,设V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4},那么G=(V,E)是一个有4个顶点和6条边的图,G的图解如以下图所示..一个图会有许多外形不同的图解,下面两个图表示同一个图G=(V,E)的图解.其中V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4}.这两个图互为同构图,今后将不计较这种外形上的差别,而用一个容易了解的、确定的图解去表示一个图..有边结合的两个点称为相邻的点,有一个公共端点的边称为相邻边.边和它的端点称为相互关联.常用d(v)表示图G中与顶点v关联的边的数目,d(v)称为顶点v的度数.对于有向图,还有出度和入度之分.用N(v)表示图G中一切与顶点v相邻的顶点的集合.d(v1)=d(v3)=d(v4)=4,d(v2)=2.握手定理：.我们今后只讨论有限简单图：(1)顶点个数是有限的;(2)恣意一条边有且只需两个不同的点与它相互关联;(3)假设是无向图,那么恣意两个顶点最多只需一条边与之相结合;(4)假设是有向图,那么恣意两个顶点最多只需两条边与之相结合.当两个顶点有两条边与之相结合时，这两条边的方向相反.假设某个有限图不满足(2)(3)(4),可在某条边上增设顶点使之满足..定义2假设将图G的每一条边e都对应一个实数F(e),那么称F(e)为该边的权,并称图G为赋权图(网络),记为G=(V,E,F).定义3恣意两点均有通路的图称为连通图.定义4连通而无圈的图称为树,常用T表示树..例一摆渡人欲将一只狼,一头羊,一篮菜从河西渡过河到河东.由于船小,一次只能带一物过河，并且狼与羊,羊与菜不能独处.给出渡河方法.解：用四维0-1向量表示(人,狼,羊,菜)在河西岸的形状(在河西岸那么分量取1,否那么取0),共有24=16种形状.在河东岸的形状类似记作.由题设,形状(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允许的,从而对应形状(1,0,0,1),(1,1,0,0),(1,0,0,0)也是不允许的.以可允许的10个形状向量作为顶点,将能够相互转移的形状用线段衔接起来构成一个图.根据此图便可找到渡河方法..(1,1,1,1)(1,1,1,0)(1,1,0,1)(1,0,1,1)(1,0,1,0)(0,0,0,0)(0,0,0,1)(0,0,1,0)(0,1,0,0)(0,1,0,1)(0,1,0,1)(0,1,0,0)(0,0,1,0)(0,0,0,1)(0,0,0,0)(1,0,1,0)(1,0,1,1)(1,1,0,1)(1,1,1,0)(1,1,1,1)河西=(人,狼,羊,菜)河东=(人,狼,羊,菜)将10个顶点分别记为A1,A2,…,A10,那么渡河问题化为在该图中求一条从A1到A10的路.从图中易得到两条路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10..图的矩阵表示⑴邻接矩阵邻接矩阵表示了点与点之间的邻接关系.一个n阶图G的邻接矩阵A=(aij)n×n,其中.无向图G的邻接矩阵A是一个对称矩阵.⑵权矩阵一个n阶赋权图G=(V,E,F)的权矩阵A=(aij)n×n,其中有限简单图根本上可用权矩阵来表示..无向图G的权矩阵A是一个对称矩阵..⑶关联矩阵〔略〕一个有m条边的n阶有向图G的关联矩阵A=(aij)n×m,其中假设vi是ej的始点;假设vi是ej的终点;假设vi与ej不关联.有向图的关联矩阵每列的元素中有且仅有一个1,有且仅有一个-1..一个有m条边的n阶无向图G的关联矩阵A=(aij)n×m,其中假设vi与ej关联;假设vi与ej不关联.无向图的关联矩阵每列的元素中有且仅有两个1..2、最短途径算法定义1设P(u,v)是赋权图G=(V,E,F)中从点u到v的途径,用E(P)表示途径P(u,v)中全部边的集合,记那么称F(P)为途径P(u,v)的权或长度(间隔).定义2假设P0(u,v)是G中衔接u,v的途径,且对恣意在G中衔接u,v的途径P(u,v)都有F(P0)≤F(P),那么称P0(u,v)是G中衔接u,v的最短路..重要性质：假设v0v1…vm是图G中从v0到vm的最短路,那么1≤k≤m,v0v1…vk必为G中从v0到vk的最短路.即：最短路是一条路，且最短路的任一段也是最短路.求非负赋权图G中某一点到其它各点最短路，普通用Dijkstra标号算法；求非负赋权图上恣意两点间的最短路，普通用Floyd算法.这两种算法均适用于有向非负赋权图.下面分别引见两种算法的根本过程..Dijkstra算法目的〔a为起点〕

设T为V的子集，P=V-T且a∈T，对一切t∈T，设l(t)表示从a到t的一切通路中间隔最短的一条的长度，且这条途径中不包含T中其他的结点，那么称l(t)为t关于集合P的目的，假设不存在这样的途径，这记l(t)=∞注：l(t)不一定是从a到t的最短途径，由于最短途径中能够包含T中其他的节点。定理1

假设t是T中关于P由最小目的的结点，那么l(t)是a和t之间的最短间隔。定理2

设T为V的子集，P=V-T，设

(1)对P中的任一点p,存在一条从a到p的最短途径,这条途径仅有P中的点构成,

(2)对于每一点t,它关于P的目的为l(t),令x为最小目的所在的点,即:l(x)=min(l(t))(tT),

(3)令P'=P{x},T'=T-{x},l'(t)表示T'中结点t关于P'的目的,那么

l'(t)=min{l(t),l(x)+w(x,t)}.Dijkstra算法〔求a点到其他点的最短途径〕1、初始化，P={a}，T=V-{a}，对每个结点t计算目的l(t)=w(a,t)2、设x为T中关于P有最小目的的点,

即:l(x)=min(l(t))(t∈T),3、假设T=Ф,那么算法终了;

否那么,令P'=PU{x},T'=T-{x}

按照公式l'(t)=min{l(t),l(x)+w(x,t)},

计算T'中每一个结点t'关于P'的目的.4、P'替代P,T'替代T,反复步骤2,3〔其中：w(x,y)为图的权矩阵〕.改良Dijkstra算法〔求a点到其他点的最短途径〕1、初始化，P={a}，T=V-{a}，对每个结点t计算目的l(t)=w(a,t),pro(t)=a;2、设x为T中关于P有最小目的的点,

即:l(x)=min(l(t))(t∈T);3、假设T=Ф,那么算法终了;

否那么,令P‘=PU{x},T’=T-{x}

按照公式l‘(t)=min{l(t),l(x)+w(x,t)},

计算T’中每一个结点t‘关于P’的目的.

假设l(x)+w(x,t)<l(t),pro(t)=x;4、P'替代P,T'替代T,反复步骤2,3〔其中：w(x,y)为图的权矩阵〕.ABCDEFGHA02∞∞∞∞6∞B207∞∞13∞C∞7043∞∞∞D∞∞405∞∞2E∞∞3502∞2F∞1∞∞201∞G63∞∞∞104H∞∞∞22∞40例求以下图中A点到其他点的最短路..Floyd算法〔求恣意两点的最短途径〕设A=(aij)n×n为赋权图G=(V,E,F)的权矩阵,dij表示从vi到vj点的间隔,rij表示从vi到vj点的最短路中前一个点的编号.①赋初值.对一切i,j,dij=aij,rij=j.k=1.转向②.②更新dij,rij.对一切i,j,假设dik+dkj＜dij,那么令dij=dik+dkj,rij=k,转向③;③终止判别.假设k=n终止;否那么令k=k+1,转向②.最短道路可由rij得到..0123456700281∞∞∞∞1206∞1∞∞∞28607512∞31∞70∞∞9∞4∞15∞03∞85∞∞1∞30466∞∞29∞4037∞∞∞∞8630例求以下图中恣意两点间的最短路..以下仅从图上进展直观操作.根据假设dik+dkj＜dij,那么令dij=dik+dkj.将原来的赋权值改动为|v2v4|=4,|v5v6|=3.再依次改动为|v1v2|=5,|v0v2|=7.接下来根据假设dij>dik+dkj,那么删除vi到vj的连线.得到.从上图中容易得到恣意两点间的最短路.例如,v1到v6的路有三条：v1v0v3v2v6(长度为12),v1v4v5v2v6(长度为7),v1v4v7v6(长度为12)..例设备更新问题某企业每年年初,都要作出决议,假设继续运用旧设备,要付维修费；假设购买一台新设备,要付购买费.试制定一个5年更新方案,使总支出最少.知设备在每年年初的购买费分别为11,11,12,12,13.运用不同时间设备所需的维修费分别为5,6,8,11,18.解设bi表示设备在第i年年初的购买费,ci表示设备运用i年后的维修费,

V={v1,v2,…,v6},点vi表示第i年年初购进一台新设备,虚设一个点v6表示第5年年底.

E={vivj|1≤i＜j≤6}..这样上述设备更新问题就变为：在有向赋权图G=(V,E,F)(图解如下)中求v1到v6的最短路问题..由实践问题可知,设备运用三年后该当更新,因此删除该图中v1到v5,v1到v6,v2到v6的连线；又设备运用一年后就更新那么不划算,因此再删除该图中v1v2,v2v3,v3v4,v4v5,v5v6五条连线后得到从上图中容易得到v1到v6只需两条路：v1v3v6和v1v4v6.而这两条路都是v1到v6的最短路..3、最小生成树由树的定义不难知道,恣意一个连通的(n,m)图G适当去掉m-n+1条边后,都可以变成树,这棵树称为图G的生成树.设T是图G的一棵生成树,用F(T)表示树T中一切边的权数之和,F(T)称为树T的权.一个连通图G的生成树普通不止一棵,图G的一切生成树中权数最小的生成树称为图G的最小生成树.

求最小生成树问题有很广泛的实践运用.例如,把n个乡镇用高压电缆衔接起来建立一个电网,使所用的电缆长度之和最短,即费用最小,就是一个求最小生成树问题..Kruskal算法：从未选入树中的边中选取权重最小的且不构成回路的边参与到树中.〔判别回路比较费事〕Prim算法：把结点分成两个集合，已参与树中的(P)和未参与树中的(Q)，然后每次选择一个点在P中一个点在Q中的权重最小的边，参与树中，并把相应点参与P中。其最小生成树如下：类似地,可定义连通图G的最大生成树..例选址问题现预备在n个居民点v1,v2,…,vn中设置一银行.问设在哪个点,可使最大效力间隔最小?假设设置两个银行,问设在哪两个点?模型假设假设各个居民点都有条件设置银行,并有路相连,且路长知.模型建立与求解用Floyd算法求出恣意两个居民点vi,vj之间的最短间隔,并用dij表示.⑴设置一个银行,银行设在vi点的最大效力间隔为.求k,使即假设设置一个银行,那么银行设在vk点,可使最大效力间隔最小.⑵设置两个银行,假设银行设在vs,vt点使最大效力间隔最小.记那么s,t满足：进一步,假设设置多个银行呢？.4、遍历性问题一、欧拉图G=(V,E)为一连通无向图经过G中每条边至少一次的回路称为巡回；经过G中每条边正好一次的巡回称为欧拉巡回；存在欧拉巡回的图称为欧拉图。二、中国邮递员问题〔CPP－chinesepostmanproblem〕一名邮递员担任投递某个街区的邮件。如何为他〔她〕设计一条最短的投递道路〔从邮局出发，经过投递区内每条街道至少一次，最后前往邮局〕？这一问题是我国管梅谷教授1962年首先提出，国际上称之为中国邮递员问题。.解法：假设本身就是欧拉图，那么直接可以找到一条欧拉巡回就是本问题的解。假设不是欧拉图，必定有偶数个奇度数结点，在这些奇度数点之间添加一些边，使之变成欧拉图，再找出一个欧拉巡回。详细解法：Fleury算法+Edmonds最小对集算法.三、哈密尔顿图G=(V,E)为一连通无向图经过G中每点一次且正好一次的途径称为哈密尔顿途径；经过G中每点一次且正好一次的回路称为哈密尔顿回路；存在哈密尔顿回路的图称为哈密尔顿图。四、游览商问题〔TSP－travelingsalesmanproblem〕一名推销员预备前往假设干城市推销产品。如何为他〔她〕设计一条最短的游览道路？即：从驻地出发，经过每个城市恰好一次，最后前往驻地〔最小哈密尔顿回路〕对于n个节点的游览商问题，n个节点的恣意一个全陈列都是问题的一个能够解〔假设恣意两个点之间都有边〕。G个节点的全陈列有(n-1)!个，因此间题归结为在(n-1)!个回路中选取最小回路。TSP问题的解法属于NP完全问题，普通只研讨其近似解法.最临近算法(1)选取恣意一个点作为起始点,找出与该点相关联的权重最小的边,构成一条初始途径.

(2)找出与最新参与到途径中的点相关联的权重最小的边参与到途径中,且要求不再途径中产生回路.

(3)反复(2)直到一切的结点都参与到途径中.

(4)将起点和最后参与的结点之间的边参与到途径中,构成Hamilton回路.其他数值算法：

人工神经元方法，

遗传算法等等.5、二分图与匹配定义1设X,Y都是非空有限集,且X∩Y=,

E{xy|x∈X,y∈Y},称G=(X,Y,E)为二部图.二部图可以为是有限简单无向图.假设X中的每个点都与Y中的每个点邻接,那么称G=(X,Y,E)为完备二部图.假设F：E→R+,那么称G=(X,Y,E,F)为二部赋权图.二部赋权图的权矩阵普通记作A=(aij)|X|×|Y|,其中aij=F(xiyj)..定义2设G=(X,Y,E)为二部图,且ME.假设M中恣意两条边在G中均不邻接,那么称M是二部图G的一个匹配.定义3设M是二部图G的一个匹配,假设G的每一个点都是M中边的顶点,那么称M是二部图G的完美匹配；假设G中没有另外的匹配M0,使|M0|＞|M|,那么称M是二部图G的最大匹配.在二部赋权图G=(X,Y,E,F)中,权数最大的最大匹配M称为二部赋权图G的最正确匹配.显然,每个完美匹配都是最大匹配,反之不一定成立..任务安排问题之一给n个任务人员x1,x2,…,xn安排n项任务y1,y2,…,yn.n个任务人员中每个人能胜任一项或几项任务,但并不是一切任务人员都能从事任何一项任务.比如x1能做y1,y2任务,x2能做y2,y3,y4任务等.这样便提出一个问题,对一切的任务人员能不能都分配一件他所能胜任的任务？我们构造一个二部图G=(X,Y,E),这里X={x1,x2,…,xn},Y={y1,y2,…,yn},并且当且仅当任务人员xi胜任任务yj时,xi与yj才相邻.于是,问题转化为求二部图的一个完美匹配.由于|X|=|Y|,所以完美匹配即为最大匹配..求二部图G=(X,Y,E)的最大匹配算法(匈牙利算法,交替链算法)迭代步骤:从G的恣意匹配M开场.①将X中M的一切非饱和点都给以标号0和标志*,转向②.M的非饱和点即非M的某条边的顶点.②假设X中一切有标号的点都已去掉了标志*,那么M是G的最大匹配.否那么任取X中一个既有标号又有标志*的点xi,去掉xi的标志*,转向③.③找出在G中一切与xi邻接的点yj,假设一切这样的yj都已有标号,那么转向②,否那么转向④..④对与xi邻接且尚未给标号的yj都给定标号i.假设一切的yj都是M的饱和点,那么转向⑤,否那么逆向前往.即由其中M的任一个非饱和点yj的标号i找到xi,再由xi的标号k找到yk,…,最后由yt的标号s找到标号为0的xs时终了,获得M-增广路xsyt…xiyj,记P={xsyt,…,xiyj},重新记M为M⊕P,转向①.不用理睬M-增广路的定义.M⊕P=M∪P\M∩P,是对称差.⑤将yj在M中与之邻接的点xk,给以标号j和标志*,转向②..例求以下图所示二部图G的最大匹配.解①取初始匹配M0={x2y2,x3y3,x5y5}(上图粗线所示).②给X中M0的两个非饱和点x1,x4都给以标号0和标志*(如以下图所示).③去掉x1的标志*,将与x1邻接的两个点y2,y3都给以标号1.由于y2,y3都是M0的两个饱和点,所以将它们在M0中邻接的两个点x2,x3都给以相应的标号和标志*(如以下图所示)..④去掉x2的标志*,将与x2邻接且尚未给标号的三个点y1,y4,y5都给以标号2(如以下图所示).⑤由于y1是M0的非饱和点,所以顺着标号逆向前往依次得到x2,y2,直到x1为0为止.于是得到M0的增广路x1y2x2y1,记P={x1y2,y2x2,x2y1}.取M1=M0⊕P={x1y2,x2y1,x3y3,x5y5},那么M1是比M多一边的匹配(如以下图所示)..⑥再给X中M1的非饱和点x4给以标号0和标志*,然后去掉x4的标志*,将与x4邻接的两个点y2,y3都给以标号4.由于y2,y3都是M1的两个饱和点,所以将它们在M1中邻接的两个点x1,x3都给以相应的标号和标志*(如以下图所示).⑦去掉x1的标志*,由于与x1邻接的两个点y2,y3都有标号4,所以去掉x3的标志*.而与x3邻接的两个点y2,y3也都有标号4,此时X中一切有标号的点都已去掉了标志*(如以下图所示),因此M1是G的最大匹配.G不存在饱和X的每个点的匹配,当然也不存在完美匹配..任务安排问题之二给n个任务人员x1,x2,…,xn安排n项任务y1,y2,…,yn.假设每个任务人员任务效率不同,要求任务分配的同时思索总效率最高.我们构造一个二部赋权图G=(X,Y,E,F),这里X={x1,x2,…,xn},Y={y1,y2,…,yn},F(xiyj)为任务人员xi胜任任务yj时的任务效率.那么问题转化为：求二部赋权图G的最正确匹配.在求G的最正确匹配时,总可以假设G为完备二部赋权图.假设xi与yj不相邻,可令F(xiyj)=0.同样地,还可虚设点x或y,使|X|=|Y|.如此就将G转化为完备二部赋权图,而且不会影响结果..定义设G=(X,Y,E,F)为完备的二部赋权图,

假设L：X∪Y→R+满足：x∈X,y∈Y,L(x)+L(y)≥F(xy),那么称L为G的一个可行点标志,

记相应的生成子图为GL=(X,Y,EL,F),这里EL={xy∈E|L(x)+L(y)=F(xy)}.

求完备二部赋权图G=(X,Y,E,F)的最正确匹配算法迭代步骤：设G=(X,Y,E,F)为完备的二部赋权图,L是其一个初始可行点标志,通常取L(x)=max{F(xy)|y∈Y},x∈X,L(y)=0,y∈Y..M是GL的一个匹配.①假设X的每个点都是饱和的,那么M是最正确匹配.否那么取M的非饱和点u∈X,令S={u},T=,转向②.②记NL(S)={v|u∈S,uv∈GL}.

假设NL(S)=T,那么GL没有完美匹配,转向③.否那么转向④.③调整标志,计算aL=min{L(x)+L(y)-F(xy)|x∈S,y∈Y\T}.由此得新的可行点标志令L=H,GL=GH,重新给出GL的一个匹配M,转向①.④取y∈NL(S)\T,假设y是M的饱和点,转向⑤.否那么,转向⑥.⑤设xy∈M,那么令S=S∪{x},T=T∪{y},转向②.⑥在GL中的u-y路是M-增广路,设为P,并令M=M⊕P,转向①..6、网络流问题定义1设G=(V,E)为有向图,在V中指定一点称为发点(记为vs),和另一点称为收点(记为vt),其他点叫做中间点.对每一条边vivj∈E,对应一个非负实数Cij,称为它的容量.这样的G称为容量网络,简称网络,记作G=(V,E,C).定义2网络G=(V,E,C)中任一条边vivj有流量fij,称集合f={fij}为网络G上的一个流.满足下述条件的流f称为可行流：①(限制条件)对每一边vivj,有0≤fij≤Cij;②(平衡条件)对于中间点vk有∑fik=∑fkj,即中间点vk的输入量=输出量..假设f是可行流,那么对收、发点vt、vs有∑fsi=∑fjt=Wf,即从vs点发出的物质总量=vt点输入的量.Wf称为网络流f的总流量.上述概念可以这样来了解,如G是一个运输网络,那么发点vs表示发送站,收点vt表示接纳站,中间点vk表示中间转运站,可行流fij表示某条运输线上经过的运输量,容量Cij表示某条运输线能承当的最大运输量,Wf表示运输总量.可行流总是存在的.比如一切边的流量fij=0就是一个可行流(称为零流)..所谓最大流问题就是在容量网络中,寻觅流量最大的可行流.实践问题中,一个网络会出现下面两种情况：⑴发点和收点都不止一个.处理的方法是再虚设一个发点vs和一个收点vt,发点vs到一切原发点边的容量都设为无穷大,一切原收点到收点vt边的容量都设为无穷大.⑵网络中除了边有容量外,点也有容量.处理的方法是将一切有容量的点分成两个点,如点v有容量Cv,将点v分成两个点v'和v",令C(v'v")=Cv..最小费用流问题这里我们要进一步讨论不仅要使网上的流到达最大,或者到达要求的预定值,而且还要使运输流的费用是最小的,这就是最小费用流问题.最小费用流问题的普通提法：知网络G=(V,E,C),每条边vivj∈E除了已给容量Cij外,还给出了单位流量的费用bij(≥0).所谓最小费用流问题就是求一个总流量知的可行流f={fij}使得总费用最小..特别地,当要求f为最大流时,即为最小费用最大流问题.设网络G=(V,E,C),取初始可行流f为零流,求解最小费用流问题的迭代步骤：①构造有向赋权图Gf=(V,Ef,F),对于恣意的vivj∈E,Ef,F的定义如下：当fij=0时,vivj∈Ef,F(vivj)=bij;当fij=Cij时,vjvi∈Ef,F(vjvi)=-bij;当0＜fij＜Cij时,vivj∈Ef,F(vivj)=bij,vjvi∈Ef,F(vjvi)=-bij.然后转向②..②求出含有负权的有向赋权图Gf=(V,Ef,F)中发点vs到收点vt的最短路,假设最短路存在转向③;否那么f是所求的最小费用最大流,停顿.③增流.vivj与一样,vivj与相反.令=min{ij|vivj∈},重新定义流f={fij}为其它情况不变.假设Wf大于或等于预定的流量值,那么适当减少值,使Wf等于预定的流量值,那么f是所求的最小费用流,停顿;否那么转向①..下面引见求解有向赋权图G=(V,E,F)中含有负权的最短路的Ford算法.设边的权vivj为wij,v1到vi的路长记为(i).Ford算法的迭代步骤：①赋初值(1)=0,(i)=∞,i=2,3,…,n.②更新(i),i=2,3,…,n.(i)=min{(i),min{(j)+wji|j≠i}}.③假设一切的(i)都无变化,停顿;否那么转向②.在算法的每一步,(i)都是从v1到vi的最短路长度的上界.假设不存在负长回路,那么从v1到vi的最短路长度是(i)的下界,经过n-1次迭代后(i)将坚持不变.假设在第n次迭代后(i)仍在变化时,阐明存在负长回路..7、关键途径问题〔拓扑排序〕一项工程义务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机,都要包括许多工序.这些工序相互约束,只需在某些工序完成之后,一个工序才干开场.即它们之间存在完成的先后次序关系,普通以为这些关系是预知的,而且也可以估计完成每个工序所需求的时间.这时工程指点人员迫切希望了解最少需求多少时间才可以完成整个工程工程,影响工程进度的关键工序是哪几个？.PT(Potentialtaskgraph)图在PT(Potentialtaskgraph)图中,用结点表示工序,假设工序i完成之后工序j才干启动,那么图中有一条有向边(i,j),其长度wi表示工序i所需的时间.这种图必定不存在有向回路,否那么某些工序将在本身完成之后才干开场,这显然不符合实践情况.在PT图中添加两个虚拟结点v0和vn,使一切仅为始点的结点都直接与v0结合,v0为新增边的始点,这些新增边的权都设为0;使一切仅为终点的结点都直接与vn结合,vn为新增边的终点.这样得到的图G依然不存在有向回路..例一项工程由13道工序组成,所需时间(单位：天)及先行工序如下表所示(P172).工序序号ABCDEFGHI所需时间263243842先行工序—AABC,DDDDG,H工序序号JKLM所需时间3856先行工序GH,EJK试问这项工程至少需求多少天才干完成?那些工程不能延误?那些工程可以延误?最多可延误多少天?.先作出该工程的PT图.由于除了工序A外，均有先行工序,因此不用虚设虚拟结点v0.AB22C6D3E2F2G2H2K4N3I8J8442L3M856在PT图中,容易看出各工序先后完成的顺序及时间.虚拟结点.AB22C6D3E2F2G2H2K4N3I8J8442L3M856这项工程至少需求多少天才干完成?就是要求A到N的最长路,此途径称为关键途径.那些工程不能延误?那些工程可以延误?最多可延误多少天?关键途径上的那些工程不能延误..关键途径(最长途径)算法定理假设有向图G中不存在有向回路,那么可以将G的结点重新编号为u1,u2,…,un,使得对恣意的边uiuj∈E(G),都有i＜j.各工序最早启动时间算法步骤：①根据定理对结点重新编号为u1,u2,…,un.②赋初值(u1)=0.③依次更新(uj),j=2,3,…,n.(uj)=max{(ui)+(ui,uj)|uiuj∈E(G)}.④终了.其中(uj)表示工序uj最早启动时间,而(un)即(vn)是整个工程完工所需的最短时间..AB22C6D3E2F2G2H2K4N3I8J8442L3M856此例不用重新编号，只需按字母顺序即可.(A)=0,(B)=(C)=2,(D)=8,(E)=max{2+3,8+2}=10,(F)=(G)=(H)=(D)+2=10,(I)=max{(G)+8,(H)+4}=18,(J)=(G)+8=18,(K)=max{(E)+4,(H)+4}=14,(L)=(J)+3=21,(M)=(K)+8=22,(N)=max{(F)+3,(I)+2,(L)+5,(M)+6}=28.关键途径?.经过以上计算阐明：这项工程至少需求28天才干完成.关键途径(最长途径):A→B→D→E→K→M→NA→B→D→H→K→M→N工序A,B,D,E,H,K,M不能延误,否那么将影响工程的完成.但是对于不在关键途径上的工序,能否允许延误？假设允许,最多可以延误多长时间呢？各工序允许延误时间t(uj)等于各工序最晚启动时间(uj)减去各工序最早启动时间(uj).即t(uj)=(uj)-(uj)..最晚启动时间算法步骤(知结点重新编号)：①赋初值(un)=(un).②更新(uj),j=n-1,n-2,…,1.(uj)=min{(ui)-(ui,uj)|uiuj∈E(G)}.③终了.顺便提一句,根据工序uj允许延误时间t(uj)能否为0,可判别该工序能否在关键途径上..AB22C6D3E2F2G2H2K4N3I8J8442L3M856(N)=28,(M)=28-6=22,(L)=28-5=23,(K)=(M)-8=14,(J)=(L)-3=20,(I)=28-2=26,(H)=min{(K)-4,(I)-4}=10,(G)=min{(J)-8,(I)-8}=12,(F)=28-3=25,(E)=(K)-4=10,(D)=min{(E)-2,(F)-2,(G)-2,(H)-2}=8,(C)=(E)-3=7,(B)=(D)-6=2,(A)=0..各工序允许延误时间如下：t(A)=t(B)=t(D)=t(E)=t(H)=t(K)=t(M)=0,t(C)=5,t(F)=15,t(G)=2,t(I)=8,t(J)=2,t(L)=2..PERT图在PERT(Programmeevaluationandreviewtechnique)图中,采用有向边表示工序,其权值表示该工序所需时间.假设工序ei完成后ej才干开场,那么令vk是ei的终点,ej的始点.根据这种商定,前例的PERT图如下：ABCEFDDGGHHIJKLM对于PERT图,一些算法与PT图类似..PT图要比PERT图好一些.PT图的结点数根本上是固定的,这是最重要的一点,容易编程计算.另外PT图比PERT图更加灵敏,它能顺应一些额外的约束.例如以下图中(i)/2vivj⑴(i)+tvivj⑵bjv0vj⑶⑴表示工序vi完成一半之后vj就可以开场.⑵表示工序vi完成后经过t时辰vj才开场.⑶表示在时间bj之后工序vj才干开场,其中v0表示虚拟结点..8、系统监控模型定义1设图G=(V,E),KV假设图G的每条边都至少有一个顶点在K中,那么称K是G的一个点覆盖.假设G的一个点覆盖中恣意去掉一个点后不再是点覆盖,那么称此点覆盖是G的一个极小点覆盖.顶点数最少的点覆盖,称为G的最小点覆盖.例如,右图中,{v0,v2,v3,v5,v6}等都是极小点覆盖.{v0,v1,v3,v5},{v0,v2,v4,v6}都是最小点覆盖..系统监控问题之一假设v1,v2,…,v7是7个哨所,监视着11条路段(如以下图所示),为节省人力,问至少需求在几个哨所派人站岗,就可以监视全部路段?这就是要求最小点覆盖问题.v2v1v3v7v6v5v4{v1,v3,v5,v6}和{v1,v3,v5,v7}都是最小点覆盖,所以致少需求在4个哨所派人站岗来监视全部路段.到目前为止,还没有找到求最小点覆盖的有效算法,即多项式时间算法(算法步数不超越nc,n为G的顶点数,c为常数).有一些启发式近似算法..最大独立点集定义2设图G=(V,E),IV假设I中恣意两个顶点在G中都不相邻,那么称I是G的一个独立点集.假设G的一个独立点集中,恣意添加一个点后不再是独立点集,那么称此独立点集是G的一个极大独立点集.顶点数最多的独立点集,称为G的最大独立点集.例如,右图中,{v1,v4}等都是极大独立点集.{v1,v3,v5},{v2,v2,v6}是最大独立点集..最小控制集定义3设图G=(V,E),DV假设v∈V,要么v∈D,要么v与D的某个点相邻,那么称D是G的一个控制集.假设G的一个控制集中恣意去掉一个点后不再是控制集,那么称此控制集是G的一个极小控制集.顶点数最少的控制集,称为G的最小控制集.例如,右图中,{v1,v3,v5}是极小控制集,{v0}是最小控制集..系统监控问题之二假设以下图代表一指挥系统,顶点v1,v2,…,v7表示被指挥的单位,边表示可以直接下达命令的通讯线路.欲在某些单位建立指挥站,以便可以经过指挥站直接给各单位下达命令,问至少需求建立几个指挥站?这就是要求最小控制集问题.v2v1v3v7v6v5v4{v1,v3},{v3,v5}等都是最小控制集,所以致少需求在2个单位建立指挥站.到目前为止,还没有找到求最小控制集的有效算法...最小点覆盖、最大独立点集和最小控制集的关系定理1设无向图G=(V,E)中无孤立点(不与任何边关联