《运筹学(图与网络分析)》由会员分享，可在线阅读，更多相关《运筹学(图与网络分析)（69页珍藏版）》请在金锄头文库上搜索。
1、西安理工大学工商管理学院,运筹学Operations Research,运 筹 学 Operations Research,Chapter 8 图与网络分析Graph and Network,1. 图与网络的基本知识树 3. 最短路问题4. 最大流问题,C,B,A,引例：哥尼斯堡七桥问题,您能从A、B、C或D任意一点出发走遍7座桥并且每座桥只走一次最后回到原出发点吗？,D,E.Euler提出(1736年）：,中国邮路问题：管梅谷（1962年）提出一个邮递员，负责某一地区的信件投递。他每天要从邮局出发，走遍该地区所有街道再返回邮局，问应如何安排送信的路线可以使所走的总路程最短？,我们在实际生活、
2、生产和科研活动中经常看到许多的网络，如互联网、通信网、公路网、管道网、销售网等。对网络进行研究是希望解决其中的一些优化问题，网络最优化能为人们管理和控制这些网络系统提供一套有效的方法。,例 某家电配送中心需要为多个销售点送货，配送中心与销售点以及销售点之间的相对位置和运输情况可以用图来表示。其中，点v1，v2，v7代表销售点，边表示运输路线。若已知每条路线行走所需的时间，请帮助配送中心管理人员设计一条送货路线，使送货车辆用最短的时间送完货物，并回到配送中心。,基本的网络最优化问题有4个，即最小树问题，最短路问题、最大流问题、最小费用最大流问题。这些问题的数学模型实际上大都是线性规划问题，但使用
3、线性规划的单纯形法去求解，过程非常繁琐，本章介绍的网络分析方法能有效的解决这些问题。,图可 定义为点和边的集合，记作,式中是点的集合，是边的集合。注意上面定义的图区别于几何学中的图。在几何学中，图中点的位置、线的长度和斜率等都十分重要，而这里只关心图中有多少点以及哪些点之间有线相连，如果给图中的点和边赋以具体的含义和权数，如距离、费用、容量等，把这样的图称为网络图，记作。图和网络分析的方法已广泛应用于物理、化学、控制论、信息论、计算机科学和经济管理等各个领域。,8.1图与网络的基本知识,如图8-1,定义1 端点，关联边，相邻 若有边e可表示为e=vi,vj,称vi和vj是边e的端点，反之称边e
4、为点vi或vj的关联边。若点vi、vj与同一边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边ei和ej相邻。,例如图81，,v2和v4是边e6的端点，反之边e6是点v2、v4的关联边。点v2、v4相邻；边e6与e5、 e4相邻。,图81,e2可记作：,一、图与网络的基本概念,定义2 环，多重边，简单图 如果边e的两个端点相重，称该边为环。如图8中边e1为环。如果两个点之间的边多于一条，称为多重边，如图8中的e4和e5，对无环、无多重边的图称作简单图。,定义3 次，奇点，偶点，孤立点 与某一个点vi相关联的边的数目称为点vi的次（也叫做度），记作d(vi)。图中d(v1),d(v3
5、)=5,d(v5)=1。次为奇数的点称作奇点，次为偶数的点称作偶点，次为0的点称作孤立点。,定理1 任何图中，顶点次数的总和等于边数的2倍。,定理2 任何图中，次为奇数的顶点必为偶数个。,定义4 有向图： 如果图的每条边都有一个方向则称为有向图,定义5 混合图： 如何图G中部分边有方向则称为混合图,有向图,定义6 有向图中，以Vi为起始点的边数称为点Vi的出次，用 表示；有向图中，以Vi为终点的边数称为点Vi的入次，用 表示。,结论1： Vi点的出次与入次之和就是该点的次。,结论2：有向图中，所有顶点的入次之和等于所有顶点的出次之和。,定义7：子图、生成子图（支撑子图）,图G1=V1、E1和图
6、G2=V2，E2如果 称G1是G2的一个子图。若有 则称 G1是G2的一个支撑子图（部分图）。图8-2（a）是图 6-1的一个子图，图8-2（b）是图 8-1的支撑子图，注意支撑子图也是子图,子图不一定是支撑子图。,定义8 网络（赋权图）：,设图G（V，E），对G的每一条边(vi,vj)相应的有一条数w (vi,vj) (或记为wij)，wij称为边(vi,vj)的权,赋有权的图G称为网络（赋权图）。,这里的权数可以是时间、费用、距离等，视不同背景代表不同的含义。,赋权图,定义9 链、路、回路（圈） 无向图中有些点和边的交替序列对任意vi,t1 和vit(2tk)均相邻，称从v0到vk的链。,
7、图81中， 1=v5,e8,v3,e3,v1,e2,v2,e4,v3,e7,v5是一条链，1中因顶点v3重复出现，不能称作路。,二、连通图,如果链中所有的顶点v0，v1，vk也不相同，这样的链称初等链（或路）。,如果链中各边e1,e2,ek互不相同称为简单链。,当v0与vk重合时称为回路（或圈），如果边不重复称为简单回路，如果边不重复点也不重复则称为初等回路。,是一条链也是一条路。是一条回路并且是简单回路。,定义10 连通图,若在一个图中，如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称该图是不连通的。图81是连通图。,3=v4,e7,v3,e3,v1,e2,v2,e6,v4,欧拉
8、回路,定义11 连通图G中，若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路。 具有欧拉回路的图称为欧拉图（E图）。,哥尼斯堡七桥问题：寻找一条欧拉回路,定理3 无向连通图G是欧拉图，当且仅当G中无奇点。,七桥问题：d(A)=3, d(B)=3, d(C)=5, d(D)=3有四个奇点，故不是欧拉图,定理4 有向连通图G是欧拉图，当且仅当G中每个顶点的出次等于入次。,中国邮路问题,讨论：奇偶点图上作业法,v1,v2,v3,v4,v5,v6,v7,v8,v9,8.2 树,树的概念,树是图论中结构最简单但又十分重要的图，在许多领域都有应用。如：运动员抽签结构图,定义 树、生成树：,无圈
9、的连通图称为树； 若G1是G2的一个支撑子图并且是一棵树，则称G1是G2的一棵生成树。,图83(a)是一棵树，图83(b)是图81的一棵生成树。,v1,v1,图81,图83(a),图83(b),定理： 图G=（V，E）有生成树的充分必要条件为G是连通图。,生成树的寻求方法,在图中，每步选出一条边使它与已选边不构成圈，直到选够n-1 条边为止。,（）深探法步骤：任取一点v，给v以标号； 若某点u已得标号i，检查其端点w是否已标号； 若端点w未标号，则给w以标号i+1;重复 若端点均已标号，则退到标号i1的点，重复。,(2) 广探法,任取一点v，给v以标号；检查其所有端点wi是否已标号；若端点w未
10、标号，则给所有wi以标号i+1;对标号i+1的点重复。,（3）破圈法在图中任意取一个圈，从圈上任意舍弃一条边，将这个圈破掉；重复上述步骤，直到图中没有圈为止。,例：某乡有9个自然村，其乡间道路如下图，要求：以v0村为中心沿道路架设有线广播网络，应如何架设？,最小生成树,定义：设GV,E是一个连通图，每一条边eiE具有长度C(ei) 0, G的任意生成树T各条边的长度之和称为树T的长度，记为C（T）。长度最小的生成树称为最小树。,最小树的应用： 电信网络（计算机网络、电话专用线网络、有线电视网络等等）的设计 低负荷运输网络的设计，使得网络中提供链接的部分（如铁路、公路等 等）的总成本最小 高压输
11、电线路网络的设计电器设备线路网络（如数字计算机系统）的设计，使得线路总长度最短 连接多个场所的管道网络设计,求最小树是在一个无向连通图G中求一棵最小生成树。,避圈法（加边法）：去掉G中所有边，得到n个孤立点；然后加边；,加边的原则：从最短边开始添加，加边的过程中不能形成圈，直到连通（n1条边）。,v1,v2,v3,v4,v5,v6,4,3,5,2,1,Min C(T)=15,求最小树的方法：避圈法和破圈法,破圈法：任取一圈，去掉圈中最长边，直到无圈。,v1,v2,v3,v4,v5,v6,4,3,5,2,1,得到最小树：,Min C(T)=15,根树及其应用,定义 有向树：若一个有向图是一棵树，
12、则称这个有向图为有向树。,定义 若有向树T恰有一个结点的入次为0，其余各点入次均为1，则称T为根树。,入次为0的点，称为根,出次为0的点，称为叶,其它顶点，称为分枝点,根到某顶点vi的道路长度，称为vi点的层次。,定义 在根树T中，若每个顶点的出次小于或等于m，则称T为m叉树。 若每个顶点的出次恰好等于m或零，则称T为完全m叉树。,当m=2时，称为二叉树、完全二叉树。,记二叉树各叶子的权为pi，根到各叶子的距离（层次）为 li二叉树的总权数：,最优二叉树：满足总权最小的二叉树称为最优二叉树。霍夫曼（D A Huffman)给出了一个求最优二叉树的算法，又称霍夫曼树。,例：最优检索问题用计算机进
13、行图书分类。现有五类图书共100万册，其中有A类50万册，有B类20万册，C类5万册，D类10万册，E类15万册。问如何安排分检过程，可使总的运算次数最小？,算法步骤：1.将s个叶子按权由小至大排序；2.将二个具有最小权的叶子合并成一个分枝点，其权为p1+p2；将新的分枝点作为一个叶子，合并，,解：构造一棵具有5个叶子的最优二叉树，其叶子的权分别为50，20，5，10，15. 步骤如下： 1.将5个叶子按权由小到大排序：5，10，15，20，50 2.找出二个最小权的叶子，合并成一个分枝点，其权为15；,依次，继续。,总权为：,分检过程是：先把A类50万册从总数中分检出来，其次将B类20万册分
14、检出来，然后再将E类15万册分检出来，最后再将D、C分检出来。,8.3最短路问题,有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。,求最短路有两种算法，一是求从某一点至其它各点之间最短离的狄克斯屈拉(Dijkstra)算法；另一种是求网图上任意两点之间最短的矩阵算法。,最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路 .,渡河问题,一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法解决。,设：M人 W狼 S羊 V白菜,渡河方案共有10种，构造如下一个图，每条边的距离为1，问题变为求一条从MWSV到的最短路。,北岸,南岸,狄克斯屈拉(Dijkstra)标号算法,点标号：b(j) 起点vs到点vj的最短路长；,边标号：k(i，j)=b(i)+dij，,步骤：1.令起点的标号；b(s)0。,先求有向图的最短路，设网络图的起点是vs,终点是vt ,以vi为起点vj为终点的弧记为（i，j）,距离为dij,
