《数学建模中的图与网络分析》由会员分享，可在线阅读，更多相关《数学建模中的图与网络分析（38页珍藏版）》请在金锄头文库上搜索。
1、1-第6章 图与网络分析-第六章 图与网络分析 图是一种模型，如公路、铁路交通图 ， 通讯网络图等。 图示对现实的抽象，以点和线段的连 接组合表示。2-第6章 图与网络分析-6.1 图的基本概念和模型 一、概念（1）图：点V和边E的集合，用以表示对某种现实事物 的抽象。记作 G=V,E, V=v1,v2,vn, E=e1,e2,em 点：表示所研究的事物对象； 边：表示事物之间的联系。v1v2v3v4v0e1e2 e3 e4 e5 e6e7e0（2）若边e的两个端点重 合，则称e为环。（3）多重边：若某两端点之 间多于一条边，则称为多重边 。3-第6章 图与网络分析-（4）简单图：无环、无多重
2、边的图称为简单图。 （5）链：点和边的交替序列，其中点可重复，但边不能 重复。 （6）路：点和边的交替序列，但点和边均不能重复。（7）圈：始点和终点重合的链。（8）回路：始点和终点重合的路。（9）连通图：若一个图中，任意两点之间至少存在一条 链，称这样的图为连通图。 （10）子图，部分图：设图G1=V1,E1, G2=V2,E2, 如果有V1V2，E1E2，则称G1是G2的一个子图；若 V1=V2，E1E2，则称G1是G2的一个部分图。（11）次：某点的关联边的个数称为该点的次，以d(vi)表示。4-第6章 图与网络分析-二、图的模型例：有甲、乙、丙、丁、戊、己六名运动员报名参加A 、B、C、
3、D、E、F六个项目的比赛。如表中所示，打“”的 项目是各运动员报名参加比赛的项目。问：六个项目的比赛 顺序应如何安排，才能做到使每名运动员不连续地参加两项 比赛？甲 乙 丙 丁 戊 己项目人ABCDEF 5-第6章 图与网络分析-建立模型：解：项目作为研究对象，排序。设 点：表示运动项目。 边：若两个项目之间无同一名运动员参加。ABCDEFACDEFB AFEDCB ACBFEDAFBCDE顺序：6-第6章 图与网络分析-6.2 树图和图的最小部分树（1）树：无圈的连通图称为树图，简称为树。一、树图的概念7-第6章 图与网络分析-（2）树的特性： 树是边数最多的无圈连通图。在树中任加一条边，就
4、会形成圈。 树是边数最少的连通图。在树中任减一条边，则不连通。（3）图的最小部分树：定义：若G1是G2的一个部分图，且为树图，则称G1是 G2的一个部分树。G2：ABCD5473655 76G1：ACBD8-第6章 图与网络分析-定义：树枝总长为最短的部分树称为图的最小部分树。二、最小部分树的求法例：要在下图所示的各个位置之间建立起通信网 络，试确定使总距离最佳的方案。树枝：树图中的边称为树枝。9-第6章 图与网络分析-SABCDET252414317557最小部分树长Lmin=1410-第6章 图与网络分析-1. 避圈法：将图中所有的点分V为V两部分， V最小部分树内点的集合 V非最小部分树
5、内点的集合 任取一点vi加粗，令viV， 取V中与V相连的边中一条最短的边(vi,vj)， 加粗(vi,vj)，令vjV 重复 ，至所有的点均在V之内。2. 破圈法： 任取一圈，去掉其中一条最长的边， 重复，至图中不存在任何的圈为止。11-第6章 图与网络分析-SABCDET252414317557 最小部分树长Lmin=1412-第6章 图与网络分析-6.3 最短路问题在图示的网络图中，从给定的点S出发，要到达目 的地T。问：选择怎样的行走路线，可使总行程最短？方法：Dijkstra（D氏）标号法按离出发点的距离由 近至远逐渐标出最短距离和最佳行进路线。S1求某两点间最短距离的D（Dijks
6、tra）氏标号法24713-第6章 图与网络分析-SABCDET25241431755702447891413594 最短路线：S AB E D T最短距离：Lmin=1314-第6章 图与网络分析-2求任意两点间最短距离的矩阵算法 构造任意两点间直接到达的最短距离矩阵D（0）= dij（0）S A B C D E T S 0 2 5 4 A 2 0 2 7 B 5 2 0 1 5 3 C 4 1 0 4 D 7 5 0 1 5 E 3 4 1 0 7 T 5 7 0D（0）= 构造任意两点间直接到达、或者最多经过1个中间点到达的最 短距离矩阵D（1）= dij（1）15-第6章 图与网络分析
7、-其中 dij（1）= min dir（0）+ drj（0） ，S A B C D E T S 0 2 4 4 9 8 A 2 0 2 3 7 5 12 B 4 2 0 1 4 3 10 C 4 3 1 0 5 4 11 D 9 7 4 5 0 1 5 E 8 5 3 4 1 0 6 T 12 10 11 5 7 0D（1）=ir jdir（0）drj（0）rdSE（1）= min dSS（0）+dSE（0）, dSA（0）+dAE（0）, dSB（0）+dBE（0）, dSC（0）+dCE（0 ）, dSD（0）+ dDE（0） , dSE（0）+ dEE（0）, dST（0）+ dTE（0
8、） =8例如16-第6章 图与网络分析-其中 dij（2）= min dir（1）+ drj（1）S A B C D E T S 0 2 4 4 8 7 14 A 2 0 2 3 6 5 11 B 4 2 0 1 4 3 9 C 4 3 1 0 5 4 10 D 8 6 4 5 0 1 5 E 7 5 3 4 1 0 6 T 14 11 9 10 5 6 0D（2）=ir jdir（1）drj（1）r 构造任意两点间最多可经过3个中间点到达的最短距 离矩阵 D（2）= dij（2）17-第6章 图与网络分析-其中 dij（3）= min dir（2）+ drj（2） S A B C D E T
9、 S 0 2 4 4 8 7 13 A 2 0 2 3 6 5 11 B 4 2 0 1 4 3 9 C 4 3 1 0 5 4 10 D 8 6 4 5 0 1 5 E 7 5 3 4 1 0 6 T 13 11 9 10 5 6 0D（3）=irjdir（2）drj（2）r 构造任意两点间最多可经过7个中间点到达的最短距 离矩阵 D（3）= dij（3）18-第6章 图与网络分析-说明：一般，对于D（k）= dij（k），其中 dij（k）= min dir（k-1）+ drj（k-1） ，k=0，1，2，3，最多可经过2k-1个中间点： 其数列为0，1，3，7，15，31， 2k-1，
10、收敛条件： 当 D（k+1）= D（k）时，计算结束； 设网络中有p个点，即有p-2个中间点，则 2k-1-1 0，则称这样的 链为增广链。定理：网络的最大流量等于它的最小割集的容量。定理：当网络中不存在任何增广链时，则网络达到最大流状态。二、两个定理28-第6章 图与网络分析-s t6(4)5(3)4(4)8(7)设有如下增广链： f=1 该网络没有达到最大流状态。29-第6章 图与网络分析-三、网络最大流的标号算法(Ford-Fulkerson标号算法)基本思想：寻找增广链，改善流量分布；再重复，直到不存在任何增广链为止。步骤： 给始点标号：（0，+） 从已标号点i出发，看与其相关联的未标
11、号点j上的弧， 对+，若有0fijcij，则可对j点标号，记（i, (j)），其中 (j)=min (i) ，cij - fij对-，若有0 fji cij，也可对j点标号，记（ i, (j)），其中 (j)=min (i) ，fji （注：若有多个可标号点，可任选其中之一。）若标号中断，则得到最大流状态，否则，重复，继续标 号，至收点得到标号，转。30-第6章 图与网络分析- 当收点得到标号，则沿标号得到的增广链进行流量调整： 对+，fij = fij + (t)对-，fij = fij - (t) 其余弧上的流量不变。 重复上述过程。 最小割集：已标号点集合与未标号点集合相连接的弧中， 流
12、量=容量的弧。31-第6章 图与网络分析-8(8)v1vsv2v3v4vt7(6)9(5)9(9)2(0)6(0)5(5)10(9)5(3)(0,+)(vs,1)(v2,1)(v1,1)最大流量：fmax=14最小割集：(v3, vt), (v2, v4)32-第6章 图与网络分析-6.6 网络模型的实际应用例1：王经理花费12000元购买了一台微型车，以后年度的 维护费用取决于年初时汽车的役龄，如表示。为避免使用旧 车带来较高的维护费用，王经理可选择卖掉旧车，购买新车 使用的方案，旧车的预计收入如表示。为简化计算，假定任 何时刻购买新车都需花费12000元，王经理的目标是使净费用 最小（购置费+维护费-卖旧车收入）。役龄(年)年维护费预计收入单位：元012345200040005000900012000700060002000 1000 033-第6章 图与网络分析-解：用网络图模型描述，归结为最短路问题。7777712
