数学建模中的图与网络分析课件.ppt

1--第6章 图与网络分析--第六章 图与网络分析• 图是一种模型，如公路、铁路交通图， 通讯网络图等• 图示对现实的抽象，以点和线段的连接组合表示2--第6章 图与网络分析--§6.1 图的基本概念和模型一、概念（1）图：点V和边E的集合，用以表示对某种现实事物的抽象记作 G=｛V,E｝, 　V=｛v1,v2,···,vn｝,　　　　 E=｛e1,e2,···,em｝点：表示所研究的事物对象； 边：表示事物之间的联系v1v2v3v4v0e1e2e3e4e5e6e7e0（2）若边e的两个端点重合，则称e为环3）多重边：若某两端点之间多于一条边，则称为多重边3--第6章 图与网络分析--（4）简单图：无环、无多重边的图称为简单图5）链：点和边的交替序列，其中点可重复，但边不能重复6）路：点和边的交替序列，但点和边均不能重复7）圈：始点和终点重合的链8）回路：始点和终点重合的路9）连通图：若一个图中，任意两点之间至少存在一条链，称这样的图为连通图10）子图，部分图：设图G1=｛V1,E1｝, G2={V2,E2}, 如果有V1V2，E1E2，则称G1是G2的一个子图；若V1=V2，E1E2，则称G1是G2的一个部分图。

11）次：某点的关联边的个数称为该点的次，以d(vi)表示4--第6章 图与网络分析--二、图的模型 例：有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、D、E、F六个项目的比赛如表中所示，打“√”的项目是各运动员报名参加比赛的项目问：六个项目的比赛顺序应如何安排，才能做到使每名运动员不连续地参加两项比赛？甲 乙 丙 丁 戊 己项目人ABCDEF √ √　√ √ √ √ √　　√ √ √ √ √ √5--第6章 图与网络分析--建立模型：解：项目作为研究对象，排序设 点：表示运动项目边：若两个项目之间无同一名运动员参加ABCDEFA—C—D—E—F—BA—F—E—D—C—BA—C—B—F—E—DA—F—B—C—D—E顺序：6--第6章 图与网络分析--§6.2 树图和图的最小部分树（1）树：无圈的连通图称为树图，简称为树一、树图的概念7--第6章 图与网络分析--（2）树的特性：① 树是边数最多的无圈连通图在树中任加一条边，就会形成圈② 树是边数最少的连通图在树中任减一条边，则不连通。

3）图的最小部分树：定义：若G1是G2的一个部分图，且为树图，则称G1是G2的一个部分树G2：ABCD547365576G1：ACBD8--第6章 图与网络分析--定义：树枝总长为最短的部分树称为图的最小部分树二、最小部分树的求法例：要在下图所示的各个位置之间建立起通信网络，试确定使总距离最佳的方案树枝：树图中的边称为树枝9--第6章 图与网络分析--SABCDET252414317557最小部分树长Lmin=1410--第6章 图与网络分析--1. 避圈法：将图中所有的点分V为V两部分，V——最小部分树内点的集合V——非最小部分树内点的集合⑴ 任取一点vi加粗，令vi∈V， ⑵ 取V中与V相连的边中一条最短的边(vi,vj)， 加粗(vi,vj)，令vj∈V⑶ 重复⑵ ，至所有的点均在V之内2. 破圈法：⑴ 任取一圈，去掉其中一条最长的边， ⑵ 重复，至图中不存在任何的圈为止11--第6章 图与网络分析--SABCDET252414317557×× ××××最小部分树长Lmin=1412--第6章 图与网络分析--§6.3 最短路问题 在图示的网络图中，从给定的点S出发，要到达目的地T。

问：选择怎样的行走路线，可使总行程最短？方法：Dijkstra（D氏）标号法——按离出发点的距离由近至远逐渐标出最短距离和最佳行进路线S1．求某两点间最短距离的D（Dijkstra）氏标号法24713--第6章 图与网络分析--SABCDET25241431755702447891413594 最短路线：S  AB  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章 图与网络分析--其中 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）=irjdir（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例如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）=irjdir（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 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， ······}收敛条件：①当 D（k+1）= D（k）时，计算结束；②设网络中有p个点，即有p-2个中间点，则 2k-1-1

19--第6章 图与网络分析-- 例：有7个村镇要联合建立一所小学，已知各村镇小学生的人数大致为S—30人， A—40人，B—20人，C—15人，D—35人，E—25人， T—50人问：学校应建在那一个地点，可使学生总行程最少？ S A B C D E T 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 0L=30 40 20 15 35 25 50人数= [1325 1030 880 1035 910 865 1485]T解：20--第6章 图与网络分析--§6.4 中国邮路问题问题：一名邮递员从邮局出发，试选择一条最短的投递路线？v1v2v3v4v5v6v8v7v9v10v11v12v13邮局4445512412544742221--第6章 图与网络分析--22--第6章 图与网络分析--奇点：图中次为奇数的点称为奇点。

偶点：图中次为偶数的点称为偶点结论：结论：最短投递路线应具有下述特征： ⑴ 若图中所有的点均为偶点，则可不重复走遍所有街道； ⑵ 重复走的路线长度应不超过所在回路总长度的一半23--第6章 图与网络分析--步骤：1.两两连接所有的奇点，使之均成为偶点；2. 检查重复走的路线长度，是否不超过其所在回路总长的一半，若超过，则调整连线，改走另一半24--第6章 图与网络分析--v1v2v3v4v5v6v8v7v9v10v11v12v13邮局44455124125447422投递距离：L=60+18=7825--第6章 图与网络分析--§6.5 网络最大流问题一、网络最大流中有关概念⑴ 有向图：含有以箭头指示方向的边的网络图⑵ 弧：有向图上的边称为弧用（vi,vj）表示⑶ 弧的容量：弧上通过负载的最大能力，简称容量以cij表示⑷ 流：加在网络每条弧上的一组负载量，以fij表示⑸ 可行流：能够通过网络的负载量，通常应满足两个条件： ①　容量限制条件：对所有的弧，0  fijcij ②　中间点平衡条件：对任何一个中间点，流入量=流出量⑹ 发点、收点、中间点：流的起源点称发点，终到点称收点，其余的点称中间点。

⑺ 最大流；能够通过网络的最大流量⑻ 割集：一组弧的集合，割断这些弧，能使流中断26--第6章 图与网络分析--8(8)v1vsv2v3v4vt7(5)9(4)9(9)2(0)6(1)5(5)10(8)(0,+∞)(vs,2)(v2,2)(v1,2)(v3,1)(v4,1)5(4)cijfij27--第6章 图与网络分析--⑼ 割的容量：割集中各弧的容量之和⑽ 最小割：所有割集中容量之和为最小的一个割集⑾ 前向弧μ+：一条发点到收点链中，由发点指向收点的弧，又称正向弧⑿ 后向弧μ-：一条发点到收点链中，由收点指向发点的弧，又称逆向弧⒀ 增广链：由发点到收点之间的一条链，如果在前向弧上满足流量小于容量，即fij0，则称这样的链为增广链定理：网络的最大流量等于它的最小割集的容量定理：当网络中不存在任何增广链时，则网络达到最大流状态二、两个定理28--第6章 图与网络分析--st6(4)5(3)4(4)8(7)设有如下增广链：∵　△f=1∴ 该网络没有达到最大流状态29--第6章 图与网络分析--三、网络最大流的标号算法(Ford-Fulkerson标号算法)基本思想：寻找增广链，改善流量分布；再重复，直到不 存在任何增广链为止。

步骤：① 给始点标号：（0，+∞）②从已标号点i出发，看与其相关联的未标号点j上的弧，对μ+，若有0fij

为避免使用旧车带来较高的维护费用，王经理可选择卖掉旧车，购买新车使用的方案，旧车的预计收入如表示为简化计算，假定任何时刻购买新车都需花费12000元，王经理的目标是使净费用最小（购置费+维护费-卖旧车收入）役龄(年)年维护费预计收入单位：元012345200040005000900012000————700060002000 1000 033--第6章 图与网络分析--解：用网络图模型描述，归结为最短路问题77777123456121212122121213131441年初5年末34--第6章 图与网络分析--例2：图示岛屿与河岸有数座桥相联，问至少需要炸毁几座桥，可中断两岸的交通？ABCDEF35--第6章 图与网络分析--ABCFED22213111136--第6章 图与网络分析--例3：有3根相同的轴A1、A2、A3，另有三根相同的齿轮B1、B2、B3因为精度不高，不能做到任意的互相配合，其中A1能与B1、B2配合，A2能与B2、B3配合，A3能与B1、B3配合要求确定合适的配合方案，以得到最多的配合数，将此问题归为网络最大流问题A1A2A3B1B2B3111111ST11111137--第6章 图与网络分析--38--第6章 图与网络分析--。