课件运筹学七.pptx

第八章图与网络分析哥尼斯堡“七桥”难题ACDB1736年，数学家欧拉把该问题归结为下图：ACDB主要内容：第一节 图与网络的基本知识第二节 树第三节 最短路问题第四节 最大流问题第五节 最小费用流问题第一节图与网络的基本知识一、图与网络的基本概念 1.图及其分类图：是由点集V={vi}和V中元素的无序对的一个集合E={ek}所构成的二元组，记为：G=（V,E）。V中的元素vi叫做顶点，E中的元素ek叫做边。m（G）=|E|称为G中的边数，简记为m；n（G）=|V|称为G中的顶点个数，简记为n。有限图无向图简单图：不含环或多重边的图无限图有向图多重图完全图：每一对顶点都有边相连的无向简单图称为完全图。有n个顶点的无向完全图记为Kn。有向完全图：每一对顶点间有且仅有一条有向边的简单图。二部图：图G（V,E）的点集V可以分为两个非空子集X,Y，即X∪Y=V，X∩Y=￠，使得E中每条边的两个端点必有一个属于X，另外一个属于Y，则称G为二部图。2.顶点的次顶点的次：以点v为端点的边数叫做点v的次，简记为d(v)。悬挂点孤立点奇点偶点定理1：任何图中，顶点次数的总和等于边数的2倍。定理2：任何图中，次为奇数的顶点必为偶数个。出次：有向图中，以点vi为始点的边数叫做点vi的出次，简记为d+(vi)。入次：有向图中，以点vi为终点的边数叫做点vi的入次，简记为d-(vi)。vi点的出次和入次之和就是该点的次。有向图中，所有顶点的入次之和等于所有顶点的初次之和。3.子图子图：图G =（V,E)，若E’是E的子集，V’是V的子集，且E’中的边仅与V’中的顶点相关联，则称G’=(V’,E’)是G的一个子图。生成子图（支撑子图）：若G’=(V’,E’)是G的一个子图，且有V’=V，则G’是G的一个生成子图。4.网络点或边带有某种数量指标的图称为网络（赋权图）。二、连通图链：如{v1,e1,v2,e6,v4,e7,v3,e3,v2,e5,v5}；如{v1,e1,v2,e6,v4,e10,v6,e9,v5}；初等链：圈：如{v1,e1,v2,e5,v5,e8,v4,e6,v2,e3,v3，e2，v1}；初等圈：如{v1,e1,v2,e6,v4,e7,v3，e2，v1}.v2e5v5e1e9e6e4v1e3e8v6e10e2v3e7v4道路：有向图中，链上的边方向相同时，称为道路。如：{v1,e2,v3,e7,v4,e8,v5}是一条道路； {v1,e1,v2,e5,v5,e8,v4}是一条链但不是一条道路。回路：有向图中，圈上的边方向相同时，称为回路。如：{v1,e2,v3,e4,v2,e1,v1}是一条回路； {v1,e1,v2,e6,v4,e7,v3，e2，v1}是圈但不是一条回路。 v2e5v5e1e6e8v1e3e4e2v3e7v4连通图：一个图中任意两点间至少有一条链相连，则称此图为连通图。每一个连通图都可以分为若干个连通子图。三、图的矩阵表示有权矩阵：网络（赋权图）G=（V,E），|V|=n，其边(vi,vj)有权wij，构造矩阵A=（aij）n×n ，其中：v5称矩阵A为网络G的有权矩阵。675v44v12894v23v3邻接矩阵：图G=（V,E），|V|=n，构造矩阵A=（aij）n×n ，其中：称矩阵A为图G的邻接矩阵。v2v5v1v3v4四、欧拉回路与中国邮路问题1.欧拉回路与道路欧拉道路：连通图G中，若存在一条道路，经过每边一次且仅一次，则称该道路为欧拉道路。欧拉回路：连通图G中，若存在一条回路，经过每边一次且仅一次，则称该回路为欧拉回路。欧拉图：具有欧拉回路的图称为欧拉图。定理3：无向连通图G是欧拉图，当且仅当G中无奇点。推论1：无向连通图G是欧拉图，当且仅当G的边集可划分为若干个初等回路。推论2：无向连通图G有欧拉道路，当且仅当G中恰有两个奇点。定理4：连通有向图G是欧拉图，当且仅当它的每个顶点的出次等于入次。2.中国邮路问题 一个邮递员，负责某一地区的信件投递。他每天从邮局出发，走遍该地区所有街道再返回邮局，如何安排送信的路线可以使所走的总路程最短？分析：此问题可归结为：给定一个连通图G，每边有非负权数，要求一条回路过每边至少一次，且满足总权最小。G图中若无奇点，则G是一个欧拉图，按欧拉回路走即可。G图中若有奇点，必然有某些边不止走一次，相当于给G图中某些边增加一些重复边，使得到的新图G’无奇点且满足总路程最短。又可以转化为如下问题：在连通图G(V,E)中，求一个边集 ,把G中属于E1的边均变为二重边，得到的新图G’=G+E1，且， 最小。要满足该条件，则有：对G中的初等圈来讲，重复边的长度和不超过圈长的一半。第二节树一、树的概念和性质分枝点树叶1、概念连通且不含圈的无向图称为树。树中次为1的点称为树叶树