《运筹学-5图与网络分析》由会员分享，可在线阅读，更多相关《运筹学-5图与网络分析（178页珍藏版）》请在金锄头文库上搜索。
1、第五章 图与网络分析,张红历,Company Logo,本章内容,Company Logo,1. 图论是运筹学中广泛应用的一个重要分支。2. 图论的起源可以追溯到18世纪，早期的图论主要研究一些游戏或纯理论问题，诸如：迷宫问题、四色问题（1840）和哈密尔顿问题（1859）等。 3. 欧拉的七桥问题（1736） :,图 论 简 介,Company Logo,结论：不存在这样一种走法。,用A、B表示两座小岛，C、D表示两岸，连线AB表示A、B之间有一座桥。,问题简化为：,在该图中，从任一点出发，能否通过每条线段一次且仅仅一次后又回到原来的出发点,七桥问题的数学模型：,Company Logo,4
2、.哈密尔顿问题（环球旅行问题）,十二面体,注意：红色的线路即为一个方案。,Company Logo,Company Logo,一、 图与网络的基本概念,在生产和日常生活中，人们常用点和线画出的示意图来反映一些对象之间的关系。,铁路交通图,比赛关系图,诸如此类的还有电话线分布图,煤气管道图,航空线图等等,Company Logo,在图中，以点代表研究的对象，点与点之间的连线表示这两个对象之间的特定关系。它不同与通常的几何图和函数图，它有如下的一些特点。这里的点只是某种事物的一种抽象；连线代表某些事物之间的关系。点与连线的画法具有随意性，连线的方式不重要。这种图是一种关系示意图，在保持相对位置与关
3、系不变的前提下，点的位置、线的长度不一定要按照实际位置和实际长度来表示。,图是反映对象之间关系的一种工具,Company Logo,1.图及其分类,(1) 图的定义:图由有限个顶点的集合V和表达顶点之间关系的线集E所组成。G=（ V，E） 其中V=v1，v2， ，vn ，表示n个事物构成的非空点集；(vi 叫做顶点) ( Ek叫做边 )E反映了n个事物之间的联系，有E= e1,e2，em。,(2) 图 的 表 示,Company Logo,端点和关联边：,相邻点和相邻边：,多重边与环：,(3) 图的一些概念,Company Logo,多重图和简单图：,Company Logo,无向图和有向图：
4、,Company Logo,完全图：,每一对顶点间都有边相连的无向简单图称为完全图。有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。,二部图（偶图）：,若能将G=（V,E） 的顶点集V划分成两个子集 X和Y（X交Y为空集），使得G中任何一条边的两个端点一个属于X，另一个属于Y，则称G为二部图（也称偶图），X、Y称为互补顶点子集，此时可将G记成G= (X,Y,E).,Company Logo,2. 顶点的次,以点v为端点的边的个数称为点v 的度（次），记作,图中 d(v1)= 4,v1,v2,v3,v4,v5,v6,e1,e2,e3,e4,e5,e6,e7,度为零的点称为弧立点， 度
5、为1的点称为悬挂点。 悬挂点的关联边称为悬挂边。 度为奇数的点称为奇点， 度为偶数的点称为偶点。,Company Logo,顶点次的性质,定理1 所有顶点度数之和等于所有边数的2倍。定理2 在任一图中，奇点的个数必为偶数。,有向图中，所有顶点的入次之和等于所有顶点的出次之和。,有向图中，以 vi 为始点的边数称为点vi的出次，用 表示；以vi 为终点的边数称为点vi 的入次，用 表示；vi 点的出次和入次之和就是该点的次。,Company Logo,3. 子图,设 G=（ V , E ），若 是E的子集， 是V的子集，且 中的边仅与 中的顶点相关联，则称 是G的一个子图。特别是，若 ,则 称为
6、G的生成子图或支撑子图。,Company Logo,4. 网络,网络图：给图中反映联系的边赋一数值，称为权，来表明一定的含义。赋有权的图称为网络图。,图只能用来研究事物之间有没有某种关系，而不能研究这种关系的强弱程度。 网络 赋权的图 权 程度的度量，数量描述。,Company Logo,二、 连通图,1. 链和圈链：对一个无向图G=（G，V），一个点、边的交替序列（vi1， ei1， vi2， ei2， vik-1， eik-1， vik），如果满足eit= vit， vit+1 （t= 1，2，k-1），则称为一条联接vi1和vik的链。圈 ：若链的起点和终点相同，则称该链为圈。简单链（圈
7、）：链（圈）中所有边均不相同时，称其为简单链(圈）。初等链（圈）：若链（圈）中所有顶点均不相同（对圈而言，除第一个和最后一个顶点相同外），则称为初等链（圈）。,Company Logo,2. 路和回路,路：如果在一条链、简单链、初等链上，满足ait=（ vit， vit+1 ）（t= 1，2，k-1），则称该链环为从vi1到vik的一条路。,回路： 若路的起点和终点相同，则称之为回路。,注：即对有向图，不考虑弧的方向，类似于无向图可得到链（圈）、简单链（圈）、初等链（圈），若链上的弧的方向一致时，得到路（回路）。,3. 连通图,连通图：若图的任何两点之间至少存在一条链，这个图就称为连通图。,若
8、一个连通图含有回路，则移去回路之任一边后，剩下的部分仍然连通。,Company Logo,简单链,链,初等,简单圈,初等圈,点与边每一条边和两个节点关联，一条边可以用两个节点的标号表示（i，j）,j,i,链（Path）前后相继的点边序列P=(1,2),(2,3),(3,4),总结：无向图中的基本概念,4,2,3,1,圈(Cycle)起点和终点重合的链称为圈 =(1,2),(2,4),(4,3),(3,1)圈中各条边方向不一定相同,点与弧（有向边)每一条弧和两个节点关联，一条弧可以用两个节点的标号表示（i，j）,路径（Path）前后相继并且方向相同的弧序列P=(1,3),(3,2),(2,4),
9、4,2,3,1,有向图中的基本概念,回路（Circuit）起点和终点重合的路径称为回路=(1,2),(2,4),(4,1) 回路中各条边方向相同,4,2,3,1,链（Chain）前后相继并且方向不一定相同的边序列称为链C=(1,2),(3,2),(3,4),有向图中的基本概念,Company Logo,三、 图的矩阵表示,对于网络（赋权图）G=（V，E），其中边 有权 ，构造矩阵 ，其中：称矩阵A为网络G的权矩阵。,权矩阵,v5,v2,v3,v4,v1,4,7,5,6,9,2,4,3,8,Company Logo,设图G=（V，E）中顶点的个数为n，构造一个 矩阵 ，其中： 称矩阵A为网络G的
10、邻接矩阵。,邻接矩阵,邻接矩阵的行和列都与图的顶点相对应。,对无向图G，令 aij =顶点vi与顶点vj关联的边数，若点vi与点vj不关联则有aij =0，得到AG=（aij）p*q为G的邻接矩阵。对有向图D，令 aij =以顶点vi为起点vj为终点的弧数，则得到 AD=（aij）p*q为D的邻接矩阵。,Company Logo,Company Logo,邻接矩阵的特点,在相邻矩阵中，对无向图每一行或每一列元素之和， 等于相应顶点相关联的边数，且为对称矩阵。对有向图，其每一行元素之和等于由该顶点射出的弧数，每列元素之和等于射入该顶点的弧数。,5,v1,v2,v3,v4,v5,v6,8,4,3,
11、7,5,2,6,1,8,运筹学中研究的图具有下列特征： （1）用点表示研究对象，用边（有方向或无方向）表示对象之间某种关系。 （2）强调点与点之间的关联关系，不讲究图的比例大小与形状。 （3）每条边上都赋有一个权，其图称为赋权图。实际中权可以代表两点之间的距离、费用、利润、时间、容量等不同的含义。 （4）建立一个网络模型，求最大值或最小值。,总结：图与网络的特点,图的意义,因此,可以说图是反映对象之间关系的一种工具,在一般情况下,图中点的相对位置如何,点与点之间联线的长短曲直,对于反映对象之间的关系,并不是重要的。图论中的图与几何图,工程图等是不同的.,Company Logo,四、 欧拉回路
12、与中国邮路问题,1. 欧拉道路（一笔画问题）,Company Logo,2. 欧拉回路,存在欧拉回路：,该图特点：,该图不存在欧拉回路,具有欧拉回路的图为欧拉图,Company Logo,相关定理与推论,定理3：无向连通图G为欧拉图的充要条件是，当且仅当G中无奇点。,推论1：无向连通图G为欧拉图，当且仅当G的边集可划分为若干个初等回路。 推论2：无向连通图G有欧拉道路的充要条件是G中恰有两个奇点,定理4：连通有向图G为欧拉图的充要条件是，当且仅当它每个顶点的出次等于入次。,Company Logo,一笔画问题：,1、一个连通图的顶点都是偶点，没有奇点，则该图可以一笔画出,2、一个连通图的顶点恰
13、有两个奇点，其余均为偶点，则从任一奇点出发，可以一笔画出该图，而终点则是另一个奇点。,（从任一点出发均可）,3、一个连通图的顶点有两个以上的奇点，则该图不能一笔画出。,Company Logo,3. 中国邮路问题,提出问题的人：管梅谷教授（1962）,提出的问题：,一个邮递员从邮局出发分送邮件，要走完他负责投递的所有街道，最后再返回邮局，应如何选择投递路线，才能使所走的路线最短？,邮路问题的图论描述：,取一无向赋权连通图G=（V，E）,E中的每一条边对应一条街道,每条边的非负权l(e)=街道的长度,V中某一个顶点为邮局，其余为街道的交叉点,在G上找一个圈，该圈过每边至少一次，且圈上所有边的权和
14、最小。,Company Logo,1、若G中的顶点均为偶点,，即G中存在欧拉回路，,则该回路过每条边一次且仅一次，,此回路即为所求的投递路线,2、G中有奇点：,不存在欧拉回路,投递路线：至少有一街道要重复走一次或多次,即不存在每条街道走一次且只走一次的投递路线,分析：,结论： 选择最佳投递路线=选择重复边的权和最小的路线,Company Logo,反之，对邮路图G，,对该链上的每一条边增加一条重复边,投递路线,欧拉图,Company Logo,结论：,对任意一个含奇点的邮路图G，由于奇点的个数为偶数个，把每两个配成一对，由于G为连通图，每对奇点之间至少存在一条链，对该条链上的每一条边增加一条重
15、复边，可得一欧拉图，该欧拉图对应一条投递路线,寻找最佳投递路线方法：,在原邮路图上增加一些重复边得一个欧拉图，在所得欧拉图上找出一条欧拉回路。计算重复边的权和，重复边权和最小欧拉回路既为所求的最佳投递路线,管梅谷奇偶点图上作业法,奇偶点图上作业法：,例：求解右图所示的邮路问题,第一步：确定一个初始可行方案,方法：,检查图G中是否有奇点,无奇点：,图G已是欧拉图 ，找出一条以v1为起点的欧拉回路，该回路就是最佳投递路线。,有奇点：,把所有奇点两两配成一对，每对奇点找一条链，在该条链上的每一条边增加一条重复边，得一个欧拉图G1， 由G1所确定的欧拉回路即为一个可行方案,v2,，v8,，v4,，v6,G中有奇点：,取v2到v4的一条链：,v2v1v6v7v8v9v4,取v6到v8的一条链：,v6v1v2v3v4v9v8,V1是邮局,G1,显然G1不是最佳方案,G1是欧拉图，,第二步：调整可行方案，使重复边权和下降,重复边权和=,若图中某条边有两条或多于两条的重复边,同时去掉偶数条，,G2,使图中每一条边最多有一条重复边,G2的重复边权和=,步骤1、,可得到重复边权和较小的欧拉图。,4,51,21,G2是欧拉图，,
