2022年数学建模图论模型图论 .pdf
《2022年数学建模图论模型图论 .pdf》由会员分享,可在线阅读,更多相关《2022年数学建模图论模型图论 .pdf(21页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、图论算法1 最小生成树11 生成树的概念设图 G(V,E)是一个连通图,当从图中任一顶点出发遍历图G 时,将边集E(G)分成两个集合A(G)和 B(G)。其中 A(G)是遍历图时所经过的边的集合,B(G)是遍历图时未经过的边的集合。显然,G1(V,A)是图 G 的子图,则称子图G1 是连通图 G 的生成树。图的生成树不是惟一的。如对图1(a),当按深度和广度优先搜索法进行遍历就可以得到图1 中(b)和(c)的两棵不同的生成树,并分别称之为深度优先生成树和广度优先生成树。对于有 n 个顶点的连通图,至少有n-1 条边,而生成树中恰好有n-1 条边,所以连通图的生成树是该图的极小连通子图。若图G
2、的生成树中任意加一条边属于边集B(G)中的边,则必然形成回路。求解生成树在许多领域有实际意义。例如,对于供电线路或煤气管道的铺设问题,即假设要把n 个城市联成一个供电或煤气管道网络,则需要铺设n1 条线路。任意两城市间可铺设一条线路,n 个城市间最多可能铺设 n(n 1)/2 条线路,各条线路的造价一般是不同的。一个很实际的问题就是如何在这些可能的线路中选择 n-1 条使该网络的建造费用最少,这就是下面要讨论的最小生成树问题。1.2 网的最小生成树在前面我们已经给出图的生成树的概念。这里来讨论生成树的应用。假设,要在 n 个居民点之间敷设煤气管道。由于,在每一个居民点与其余n1 个居民点之间都
3、可能敷设煤气管道。因此,在n 个居民点之间,最多可能敷设n(n-1)/2 条煤气管道。然而,连通n 个居民点之间的管道网络,最少需要n-1 条管道。也就是说,只需要n-1 条管道线路就可以把n 个居民点间的煤气管道连通。另外,还需进一步考虑敷设每一条管道要付出的经济代价。这就提出了一个优选问题。即如何在n(n-1)/2 条可能的线路中优选n-1 条线路,构成一个煤气管道网络,从而既能连通n 个居民点,又能使总的花费代价最小。解决上述问题的数学模型就是求图中网的最小生成树问题。把居民点看作图的顶点,把居民点之间的煤气管道看作边,而把敷设各条线路的代价当作权赋给相应的边。这样,便构成一个带权的图,
4、即网。对于一个有 n 个顶点的网可以生成许多互不相同的生成树,每一棵生成树都是一个可行的敷设方案。现在的问题是应寻求一棵所有边的权总和为最小的生成树。如何构造这种网的最小生成树呢?下面给出这样一种解法:(1)已知一个网,将网中的边按其权值由小到大的次序顺序选取。名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页,共 21 页 -(2)若选某边后不形成回路,则将其保留作为树的一条边;若选某边后形成回路,则将其舍弃,以后也不再考虑。(3)如此依次进行,直到选够(n-1)条边即得到最小生成树。现以图 2 为例说明此算法。设此图是用边集数组EV 表示的,且数组中各边是按权值由小到大的次序排列,如
5、下表所示。k 1 2 3 4 5 6 7 8 9 10 EVk.p1 2 2 4 2 6 5 1 1 1 5 EVk.p2 3 4 3 6 4 7 5 6 2 6 COSTEVk.p1,EVk.p2 5 6 10 11 14 18 19 21 27 33 按权值由小到大选取各边就是在数组中按下标k 由 1 到 en(图中边数)的次序选取。选前2 条边(2,3),(2,4)时均无问题,保留作为树的边;到第3 条边(4,3)时将与已保留的边形成回路,将其舍去;同样继续做:保留(2,6);舍去(6,4);保留(5,7),(1,5),(1,6),此时,保留的边数已够(n-1)=6 条边,此时必定将 7
6、 个顶点全部互相连通了,后面剩下的边(1,2),(5,6)就不必再考虑了。最后得到的最小生成树如图 2a 中深色边所示,其各边权值总和等于80。由离散数学中的图论可以证明,这就是最小生成树了,其权值最小。当图中有权值相等的边时,其最小生成树可能有不同的选取方案。实现此算法的关键是,在选取某条边时应判断是否与已保留的边形成回路。这可用将各顶点划分为集合的办法解决:假设数组tag(1.en)作为顶点集合划分的标志初值为0。在算法的执行过程中,当所选顶点u,v 是连通的,则将相应位置的tagu,tagv 置以相同的数字,而不连通的点在初期分属不同的集合,置不同的数字;一旦两个不同的连通分支连通了,则
7、修改tag 的值,将新的连通分支改为相同的数字。我们以图 2 为例。首先选(2,3)(2,4)边,由于是连通的,并且不出现回路。tag2:1,tag3:=tag4:=1是同一个集合A;选(6,2)边与 A 集合连通;tag6:=1;再选(5,7)与集合 A 不连通,tag5:tag7:2 构成另一集合B;选(1,5)边与集合 B 连通,tag 1:=2;此时,集合A 2,3,4,6;集合 B5,7,1;当选(1,6)边时,(1,6)与集合 A、集合 B 都连通,并且两个顶点分别属于两个不同的集合A、B,这使得集合A 与集合 B 通过边(1,6)连通。修改集合B 中 tag 的值,置为 1,即将
8、集合 B 并入集合 A。边为 n-1 条,这就是一棵最小生成树。根据集合标志数组tag 的变化过程,很容易判断,选择一条新的边是否构成回路。当新选边的两个顶点u、v,若 tagu 和 tagv 相同并且均不等于0 时,即 u,v 已在生成树集合中被保留过,加入u,v 后即形成回路,不能选。而当tag utagv 或者 tagu tagv 0 时,可以选并且不形成回路,说明u,v 中至少有一个顶点未被选过或者被选过的u、v 分别属于两个不同的集合,此时选择u,v 可以将含 u 的集合与含 v 的集合连通,修改tag 数组。如此下去,到所有顶点均已属于一个集合时,此最小生成树就完全构成了。名师资料
9、总结-精品资料欢迎下载-名师精心整理-第 2 页,共 21 页 -网的最小生成树算法描述 如下:假设算法中用到的数据结构是经过处理的。COST(1.n,1.n)是带权数组存放网中顶点之间的权。EV(1.n*(n-1/2)按权从小到大存放排序后的顶点对,即 EVK.P1存放一个顶点,边的另一顶点存放在EVK.P2 之中。tag(1.n):顶点集合划分标志的数组。Enumb:当前生成树的边数。SM:当前权累计和。PROC minspanningtree(VAR cost;VAR ev);Var tag;BEGIN CALL INITIAL(tag);Enumb:0;SM:=0;诸参量初始化 k:=
10、1;边数累计 WHILE(Enumb=n-1)AND(kn)DO Begin U:=EVk.P1;V:=EVk.P2;选一对顶点(U,V)CALL FIND(U,T);找到含顶点U的集合 T CALL FIND(V,W);找到含顶点V的集合 W IF(TW)THEN Begin write(u,v);Enumb:=Enumb+1;最小生成树增加一条边 SM:=SM+COSTu,v;MERGE(T,W);选 u,v 不会形成环,合并T,W集合,并修改tag end K:=K+1;找下一条边 end IF Enumbw 表示从城市 v 到城市 W 的航线,弧 Vw 上的标号代表从V 城飞到 w 城
11、所需要的时间。要寻找由该航空图上一给定城市到另一城市所需要的最短飞行时间。可以用求解这个有向图的单源最短路径算法来完成。名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页,共 21 页 -下面,我们讨论求解单源最短路径问题的贪心算法,也称Dijkstra 算法。设有向图 G=(V,E),其中,V=1,2,n)cost 是表示 G 的邻接矩阵,costi,j表示有向边(i,j)的权。若不存在有向边(i,j),则 costi,j的权为无限大(oo)。令 S 是一个集合,其中的每个元素表示一个顶点,从源点到这些顶点的最短距离已经求出。(1)令顶点 V0 为源点,集合S 的初态只包含顶点V0,即
12、 S=V0。数组 dist 记录从源点到其他各顶点当前的最短距离,其初值为disti:=costv0,i,(i=2,n)。(2)从 S 之外的顶点集合V-S 中选出一个顶点W,使 distW 的值最小。于是,从源点到达W 只通过 S中的顶点,我们把W 加入集合 S。(3)调整 dist 中记录的从源点到V-S 中每个顶点V 的距离:从原来的distv 和 distw+costw,v中选择较小的值作为新的distv。(4)重复上述过程(2)和(3),直到 S 中包含 V 的全部顶点。最终数组 dist 记录了从源点到V 中其余各顶点的最短路径。对图 3 所示的加权有向图应用Dijkstra 算法
13、,从源点V2 出发到达各顶点的最短路径如下表所示。最短路径 -源点中间顶点终止顶点长度 2 5 10 3 15 3 4 30 3 1 35 6 oo -对图 3 的执行过程:初始时,S2,dist1 oo,dist315,dist4 oo,dist510,dist6 oo,第一遍处理时,W2 使 dist5 最小、于是把 5 加入 S。然后,调整 dist 中从源点到其余各顶点的距离:dist315,为次小,将3 加入 S。dist4cost2,3+cost3,4=15+15 30,经中间点3。S2,5,3,4,同理,dist1 cost2,3+cost3,135,S2,5,3,4,1,由于
14、2 没有一条到 6 的路径,所以 dist6=oo。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页,共 21 页 -由此我们给出最短路径算法如下PROC shortpath(VAR cost;VAR dist;VAR path;VAR S,V0);BEGIN FOR W:=1 TO n DO Begin distW:=costV0,W;最短路径初始化值 IF costV0,Wmax THEN pathW:=V0;path 记载当前最短路径 End;S:=V0;Vnum:=1;到达点集合S 和到达点 S 个数初值 WHILE(Vnumn-1)DO 最后一点已无选择余地 Begin Wm
15、:=max;u:=V0;FOR W:=1 TO n DO IF(NOT W IN S)AND(distWWm)THEN Begin U:=W;Wm:=distw End;找最小 distw S:=S+U;Vnum:=Vnum+1;U为找到最短路径的终点 FOR W:=1 TO n DO IF(NOT W IN S)AND(distU+costU,WdistW)THEN Begin distW:=distU+costU,W;调整非 S 集各点最短路径值 pathW:=U;调整非 S 集各点最短路径 End;Vnum:=Vnum+1 End;END;PROC PRINTPATH(VAR dist
16、VAR path;VAR S;V0)BEGIN FOR i:=1 TO n DO IF(i IN S)THEN Begin k:=i;WHILE(kV0)DO Begin write(k);k:=pathk End;通过找前趋点,反向输出最短路径 write(k);writeln(disti)End;ELSE Begin write(i,V0);writeln(max)End;END;容易看出,算法short path 的时间复杂度为O(n2),空间复杂度为O(n)。3 拓扑排序本节说明了如何用深度优先搜索,对一个有向无回路图进行拓扑排序。有向无回路图又称为dag。对这种有向无回路图的拓扑排序
17、的结果为该图所有顶点的一个线性序列,满足如果G 包含(u,v),则在序列中u 出现在 v 之前(如果图是有回路的就不可能存在这样的线性序列)。一个图的拓扑排序可以看成是图的所有顶点沿水平线排成的一个序列,使得所有的有向边均从左指向右。因此,拓扑排序不同于通常意义上对于线性表的排序。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页,共 21 页 -有向无回路图经常用于说明事件发生的先后次序,图 1 给出一个实例说明早晨穿衣的过程。必须先穿某一衣物才能再穿其他衣物(如先穿袜子后穿鞋),也有一些衣物可以按任意次序穿戴(如袜子和短裤)。图 1(a)所示的图中的有向边(u,v)表明衣服 u 必须
18、先于衣服v 穿戴。因此该图的拓扑排序给出了一个穿衣的顺序。每个顶点旁标的是发现时刻与完成时刻。图1(b)说明对该图进行拓扑排序后将沿水平线方向形成一个顶点序列,使得图中所有有向边均从左指向右。下列简单算法可以对一个有向无回路图进行拓扑排序。procedure Topological_Sort(G);begin 1.调用 DFS(G)计算每个顶点的完成时间fv;2.当每个顶点完成后,把它插入链表前端;3.返回由顶点组成的链表;end;图 1(b)说明经拓扑排序的结点以与其完成时刻相反的顺序出现。因为深度优先搜索的运行时间为(V+E),每一个 v 中结点插入链表需占用的时间为(1),因此进行拓扑排
19、序的运行时间(V+E)。图 1 早晨穿衣的过程为了证明算法的正确性,我们运用了下面有关有向无回路图的重要引理。引理 1 有向图 G 无回路当且仅当对G 进行深度优先搜索没有得到反向边。证明:名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页,共 21 页 -:假设有一条反向边(u,v),那么在深度优先森林中结点v 必为结点 u 的祖先,因此G 中从 v 到 u 必存在一通路,这一通路和边(u,v)构成一个回路。:假设 G 中包含一回路C,我们证明对G 的深度优先搜索将产生一条反向边。设v 是回路 C 中第一个被发现的结点且边(u,v)是 C 中的优先边,在时刻dv从 v 到 u 存在一条
20、由白色结点组成的通路,根据白色路径定理 可知在深度优先森林中结点u 必是结点 v 的后裔,因而(u,v)是一条反向边。(证毕)定理 1 Topological_Sort(G)算法可产生有向无回路图G 的拓扑排序。证明:假设对一已知有问无回路图G=(V,E)运行过程 DFS 以确定其结点的完成时刻。那么只要证明对任一对不同结点 u,v V,若 G 中存在一条从u 到 v 的有向边,则fvfu 即可。考虑过程DFS(G)所探寻的任何边(u,v),当探寻到该边时,结点v 不可能为灰色,否则v 将成为 u 的祖先,(u,v)将是一条反向边,和引理1 矛盾。因此,v 必定是白色或黑色结点。若v 是白色,
21、它就成为u 的后裔,因此fvfu。若 v 是黑色,同样 fvfu。这样一来对于图中任意边(u,v),都有 fvfu,从而定理得证。(证毕)另一种拓扑排序的算法基于以下思想:首先选择一个无前驱的顶点(即入度为0 的顶点,图中至少应有一个这样的顶点,否则肯定存在回路),然后从图中移去该顶点以及由他发出的所有有向边,如果图中还存在无前驱的顶点,则重复上述操作,直到操作无法进行。如果图不为空,说明图中存在回路,无法进行拓扑排序;否则移出的顶点的顺序就是对该图的一个拓扑排序。下面是该算法的具体实现:procedure Topological_Sort_II(G);begin 1 for 每个顶点 uVG
22、 do du0;/初始化 du,du 用来记录顶点u 的入度2 for 每个顶点 uVG do 3 for 每个顶点 vAdju do dvdv+1;/统计每个顶点的入度4 CreateStack(s);/建立一个堆栈s 5 for 每个顶点 uVG do 6 if du=0 then push(u,s);/将度为 0 的顶点压入堆栈7 count 0;名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页,共 21 页 -8 while(not Empty(s)do begin 9 utop(s);/取出栈顶元素10 pop(s);/弹出一个栈顶元素11 count count+1;12
23、Rcountu;/线性表 R 用来记录拓扑排序的结果13 for 每个顶点 vAdju do/对于每个和u 相邻的节点v begin 14 dv dv-1;15 if dv=0 then push(v,s);/如果出现入度为0 的顶点将其压入栈end;end;16 if countG.size then writeln(Error!The graph has cycle.)17 else 按次序输出 R;end;上面的算法中利用du 来记录顶点 u 的入度,第 2-3 行用来统计所有顶点的入度,第 5-6 行将入度为0的顶点压入堆栈,第 8-15 行不断地从栈顶取出顶点,将该顶点输出到拓扑序列
24、中,并将所有与该顶点相邻的顶点的入度减1,如果某个顶点的入度减至0,则压入堆栈,重复该过程直到堆栈空了为止。显而易见该算法的复杂度为O(VE),因为第 2-3 行的复杂性就是O(VE),后面 8-15 行的复杂性也是O(VE)。这个算法虽然简单,但是没有前面一个算法 的效率高。4 网络流算法:概念名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页,共 21 页 -在实际生活中有许多流量问题,例如在交通运输网络中的人流、车流、货物流,供水网络中的水流,金融系统中的现金流,通讯系统中的信息流,等等。50 年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”,是网络应
25、用的重要组成部分。在最近的奥林匹克信息学竞赛中,利用网络流算法高效地解决问题已不是什么稀罕的事了。本节着重介绍最大流(包括最小费用)算法,并通过实际例子,讨论如何在问题的原型上建立 个网络流模型,然后用最大流算法高效地解决问题。问题描述 如图 4-1 所示是联结某产品地v1 和销售地 v4 的交通网,每一弧(vi,vj)代表从 vi 到 vj 的运输线,产品经这条弧由vi 输送到 vj,弧旁的数表示这条运输线的最大通过能力。产品经过交通网从v1到 v4。现在要求制定一个运输方案使从v1 到 v4 的产品数量最多。图 4-1 图 4-2 一、基本概念及相关定理1)网络与网络流定义 1 给一个有向
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年数学建模图论模型图论 2022 数学 建模 模型
限制150内