运筹学第六章图与网络分析.ppt

《运筹学第六章图与网络分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章图与网络分析6.1图的基本概念与数学模型6.2树图和图的最小部分树6.3最短路问题6.4中国邮路问题6.5网络最大流问题6.6网络模型的实际应用第六章图与网络分析图是一种模型，如公路、铁路交通图，通讯网络图等。图是对现实的抽象，以点和线段的连接组合表示。§6.1图的基本概念和模型一、概念（1）图：点V和边E的集合，用以表示对某种现实事物的抽象。记作G=｛V,E｝,V=｛v1,v2,···,vn｝,E=｛e1,e2,···,em｝点：表示所研究的事物对象；边：表示事物之间的联系。v1v2v3v4v0e1e2e3e4e5e6e7e0（2）

2、若边e的两个端点重合，则称e为环。（3）多重边：若某两端点之间多于一条边，则称为多重边。（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的一个部

3、分图。（11）次：某点的关联边的个数称为该点的次，以d(vi)表示。二、图的模型例：有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、D、E、F六个项目的比赛。如表中所示，打“√”的项目是各运动员报名参加比赛的项目。问：六个项目的比赛顺序应如何安排，才能做到使每名运动员不连续地参加两项比赛？甲乙丙丁戊己项目人ABCDEF√√　√√√√√　　√√√√√√建立模型：解：项目作为研究对象，排序。设点：表示运动项目。边：若两个项目之间无同一名运动员参加。ABCDEFA—C—D—E—F—BA—F—E—D—C—BA—C—B—F—E—DA—F—B—C

4、—D—E顺序：§6.2树图和图的最小部分树（1）树：无圈的连通图称为树图，简称为树。一、树图的概念（2）树的特性：①树是边数最多的无圈连通图。在树中任加一条边，就会形成圈。②树是边数最少的连通图。在树中任减一条边，则不连通。（3）图的最小部分树：定义：若G1是G2的一个部分图，且为树图，则称G1是G2的一个部分树。G2：ABCD547365576G1：ACBD定义：树枝总长为最短的部分树称为图的最小部分树。二、最小部分树的求法例：要在下图所示的各个位置之间建立起通信网络，试确定使总距离最佳的方案。树枝：树图中的边称为树枝。SABCDET25

5、2414317557最小部分树长Lmin=141.避圈法1.避圈法：将图中所有的点分V为V两部分，V——最小部分树内点的集合V——非最小部分树内点的集合⑴任取一点vi加粗，令vi∈V，⑵取V中与V相连的边中一条最短的边(vi,vj)，加粗(vi,vj)，令vj∈V⑶重复⑵，至所有的点均在V之内。2.破圈法：⑴任取一圈，去掉其中一条最长的边，⑵重复，至图中不存在任何的圈为止。SABCDET252414317557××××××最小部分树长Lmin=142.破圈法§6.3最短路问题在图示的网络图中，从给定的点S出发，要到达目的地T。问：选择怎样的

6、行走路线，可使总行程最短？方法：Dijkstra（D氏）标号法——按离出发点的距离由近至远逐渐标出最短距离和最佳行进路线。S1．求某两点间最短距离的D（Dijkstra）氏标号法247SABCDET25241431755702447891413594最短路线：SABEDT最短距离：Lmin=132．求任意两点间最短距离的矩阵算法⑴构造任意两点间直接到达的最短距离矩阵D（0）=dij（0）SABCDETS0254A2027B520153C4104D75015E34107T570D（0）=⑵构造

7、任意两点间直接到达、或者最多经过1个中间点到达的最短距离矩阵D（1）=dij（1）其中dij（1）=min{dir（0）+drj（0）}，SABCDETS024498A20237512B42014310C43105411D9745015E8534106T121011570D（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例

8、如其中dij（2）=min{dir（1）+drj（1）}SABCDETS02448714A20236511B4201439C43105410D8645015E7534106T14