运筹学6(图与网络分析)

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

1、西安理工大学工商管理学院运筹学OperationsResearch运筹学Operations ResearchChapter8图与网络分析GraphandNetwork1.图与网络的基本知识树3.最短路问题4.最大流问题ACBDCBA引例：哥尼斯堡七桥问题您能从A、B、C或D任意一点出发走遍7座桥并且每座桥只走一次最后回到原出发点吗？DE.Euler提出(1736年）：中国邮路问题：管梅谷（1962年）提出一个邮递员，负责某一地区的信件投递。他每天要从邮局出发，走遍该地区所有街道再返回邮局，问应如何安排送信的路线可以使所走的总路程最短？245563344494我们在实际生活、

2、生产和科研活动中经常看到许多的网络，如互联网、通信网、公路网、管道网、销售网等。对网络进行研究是希望解决其中的一些优化问题，网络最优化能为人们管理和控制这些网络系统提供一套有效的方法。ACBD例某家电配送中心需要为多个销售点送货，配送中心与销售点以及销售点之间的相对位置和运输情况可以用图来表示。其中，点v1，v2，…，v7代表销售点，边表示运输路线。若已知每条路线行走所需的时间，请帮助配送中心管理人员设计一条送货路线，使送货车辆用最短的时间送完货物，并回到配送中心。v9v7v8v6v4v5v3配送中心v2v1基本的网络最优化问题有4个，即最小树问题，最短路问题、最大流问题、最

3、小费用最大流问题。这些问题的数学模型实际上大都是线性规划问题，但使用线性规划的单纯形法去求解，过程非常繁琐，本章介绍的网络分析方法能有效的解决这些问题。图Ｇ可定义为点和边的集合，记作式中Ｖ是点的集合，Ｅ是边的集合。注意上面定义的图Ｇ区别于几何学中的图。在几何学中，图中点的位置、线的长度和斜率等都十分重要，而这里只关心图中有多少点以及哪些点之间有线相连，如果给图中的点和边赋以具体的含义和权数，如距离、费用、容量等，把这样的图称为网络图，记作Ｎ。图和网络分析的方法已广泛应用于物理、化学、控制论、信息论、计算机科学和经济管理等各个领域。ACBD8.1图与网络的基本知识v3e7e4e

4、8e5e6e1e2e3v1v2v4v5如图8-1定义1端点，关联边，相邻若有边e可表示为e=[vi,vj],称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。若点vi、vj与同一边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边ei和ej相邻。例如图8－1，v2和v4是边e6的端点，反之边e6是点v2、v4的关联边。点v2、v4相邻；边e6与e5、e4相邻。图8－1e2可记作：一、图与网络的基本概念定义2环，多重边，简单图如果边e的两个端点相重，称该边为环。如图8－１中边e1为环。如果两个点之间的边多于一条，称为多重边，如图8－１中的e4和e5，对无环、

5、无多重边的图称作简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5定义3次，奇点，偶点，孤立点与某一个点vi相关联的边的数目称为点vi的次（也叫做度），记作d(vi)。图６－１中d(v1)＝４,d(v3)=5,d(v5)=1。次为奇数的点称作奇点，次为偶数的点称作偶点，次为0的点称作孤立点。定理1任何图中，顶点次数的总和等于边数的2倍。v1v2v3定理2任何图中，次为奇数的顶点必为偶数个。v3e7e4e8e5e6e1e2e3v1v2v4v5定义4有向图：如果图的每条边都有一个方向则称为有向图定义5混合图：如何图G中部分边有方向则称为混合图①②③④⑤⑥有向图定义6有向

6、图中，以Vi为起始点的边数称为点Vi的出次，用表示；有向图中，以Vi为终点的边数称为点Vi的入次，用表示。结论1：Vi点的出次与入次之和就是该点的次。结论2：有向图中，所有顶点的入次之和等于所有顶点的出次之和。①②③④⑤⑥定义7：子图、生成子图（支撑子图）图G1={V1、E1}和图G2={V2，E2}如果称G1是G2的一个子图。若有　则称G1是G2的一个支撑子图（部分图）。图8-2（a）是图6-1的一个子图，图8-2（b）是图8-1的支撑子图，注意支撑子图也是子图,子图不一定是支撑子图。e4v3e8e5e6v2v4v5图８－2(a)v3e7e4e8e5e6e1e2e3v1v2

7、v4v5v3e7e6e1e2e3v1v2v4v5图２－2(b)定义8网络（赋权图）：设图G＝（V，E），对G的每一条边(vi,vj)相应的有一条数w(vi,vj)(或记为wij)，wij称为边(vi,vj)的权,赋有权的图G称为网络（赋权图）。这里的权数可以是时间、费用、距离等，视不同背景代表不同的含义。①②③④⑤⑥910201571419256赋权图定义9链、路、回路（圈）▲无向图中有些点和边的交替序列对任意vi,t－1和vit(2≤t≤k)均相邻，称μ从v0到vk的链。v3e7e4e8e5e6e1e