《图论与网络优化dzmppt课件.ppt》由会员分享，可在线阅读，更多相关《图论与网络优化dzmppt课件.ppt（32页珍藏版）》请在三一文库上搜索。
1、主讲：段滋明,2012暑期数学建模,网 络 优 化,图是一种直观形象的描述已知信息的方式，它使事物之间的关系简介明了，是分析问题的有用工具。用点表示研究对象，用点之间的连续表示对象之间的相互关系。 图论与网络分析是运筹学的一个分支，内容十分丰富，应用非常广泛。,一、图,无向图 有向图,赋权图（网络）,完全图,K5,K3,3,二分图,二、几个著名问题,图论中著名问题. 1736年，图论的创始人Euler巧妙地将此问题化为图的不重复一笔画问题，并证明了该问题不存在肯定回答，发表了第一篇论文.,例：七桥问题,问题：一个散步者能否走过七座桥，且每座桥只走 过一次，最后回到出发点。,例：四色猜想,能否用
2、四种颜色给地图染色，使相邻的国家有不同的颜色。,点：国家； 边：两个国家有公共边界。,问题：能否用四种颜色给平面图的点染色，使有公共边的点有不同的颜色。,公元1852年，格里斯发现无论多么复杂的地图，只要用四种颜色就能将相邻的区域区分开来，这就是所谓“四色猜想”。 直到公元1976年，才由美国数学家同时操作三台超大型汁算机作了近200亿个逻辑判断，花费1200个机时，才取得了“四色猜想”的证明。,例：Hamilton图,哈密尔顿游戏：用正十二面体上20个顶点表示20个城市，要求参加游戏者沿着各边行走，走遍每一个城市且仅走一次，最后回到出发城市。,旅行商售货(TSP)问题： 在如上问题中，若已知
3、任意两城市间的旅行费用，问如何安排旅行路线使总费用最少？,例：中国邮路问题,一个邮递员送信，要走完他所负责的全部街道分送信件，最后返回邮局。邮递员都会本能地以尽可能少的行程完成送信任务。如何走路线最短。,点：路口； 边：两路口之间道路，第i条道路长ei。,1962年，由我国数学家管梅谷提出，国际上称为中国邮递员问题。 问题：求一个圈，过每边至少一次，并使圈的长度最 短。,三、最短路问题,最短路问题是网络理论中应用最广泛的问题之一. 许多优化问题可以使用这个模型如设备更新、管道铺设、线路安排、厂区布局等.,最短路问题：在一个赋权图G上，给定两个顶点u和 v，在所有连接顶点u和 v 的路中，寻找路
4、长最短的路（称为u和 v最短路.） u和 v最短路的路长也称为u和 v的距离-d(u,v).,有些最短路问题也可以求网络中某指定点到其余所有结点的最短路、或求网络中任意两点间的最短路.,1、网络无负权的最短路,本算法由Dijkstra于1959年提出，可用于求解指定两点间的最短路，或从指定点到其余各点的最短路，目前被认为是求无负权网络最短路问题的最好方法。,Dijkstra算法,Ford算法基本思想：为逐次逼近的方法。每次求出从出发点v0到其余点的有限制的最短路，逐次放宽条件。最多迭代|V|-1次.,2、网络有负权的最短路,Ford算法,3、网络上任意两点间的最短路Floyd算法,常用的几种解
5、法,例1 设备更新问题.,某工厂使用一台设备，每年年初工厂都要作出决定如果继续使用旧的，要付维路费；若购买一台新设备要付购买费。试制定一个5年的更新计划，使总支出最少。,若已知设备在各年年初的价格为：,还知使用不同年数的设备所需要的维修费用为：,可把这个问题化为最短路问题。,用点vi表示第i年年初购进一台新设备虚设一个点v6 ,表示第五年年底。 弧(vi ,vj)表示第i年初购进的设备一直使用到第j年年初(即第j-1年年底).,这样设备更新问题就变为：求从v到v6 的最短路。 求解得： v1 , v3 , v6 及 v1 , v4 , v6 均为最短路。 总的支付费用均为53。,已知某地区的交
6、通网络如图所示，其中点代表居民小区，便表示公路，wij为小区间公路距离问区中心医院应建在哪个小区，可使离医院最远的小区居民就诊时所走的路程最近?,例2 选址问题.,解 ：实际要求出图的中心，可以化为一系列求最短路问题。 先求出v1到其它各点的最短路长dj ,令D(v1)max(d1, d2 , , d7)表示若医院建在v1，则离医院最远的小区距离为D(v1) 。再依次计算v2 , v3 , , v7 到其余各点的最短路，类似求出D(v2),D(v3) , , D(v7) 。 D(vi)中最小者即为所求，计算结果见下表。,由于D(v6)48 最小，所以医院应建在v6，此时离医院最远的小区(v5)
7、 距离为48 .,树（tree）是一个不包含圈的简单连通图。 n个顶点的树有n-1条边。 树中度为1的点称为树叶，度大于1的点称为分枝点. 具有k个连通分支的不包含圈的图称为k-树，或森林.,四、最小生成树和最优连接,图的（最小）生成树,连通图G的子图T，如果它的顶点集与G的顶点集相同，且T是树，则称树T为图G的支撑树（生成树）。或简称为图G的树. 支撑树也称为连通图的极小连通支撑子图。 很显然，一个连通图只要本身不是一棵树，它的支撑树就不止一个。 如果图的边有权，则权的总和达到最小的生成树称为最小生成树(MST)。,最小树,最小树是网络优化中的一个重要问题，在网络设计中有广泛应用。许多网络问
8、题都可以归结为最小树问题。例如: 设计长度最小的公路网把若干城市联系起来; 设计用料最省的电话线网把有关单位联系起来等. 这些应用问题统称为最优连线问题。 也可将最优连线问题转化为整数规划求解。,许多系统包含了流量问题。例如在交通运输网络中有人流、车流、货物流；供水网络中有水流；金融系统中有现金流；通讯系统中有信息流，等等。不同网络中流的意义不同，流本身是一种输送，可以把它们统称为运输网络的流。,五、最大流问题,1. 网络与流,给一个有向连通图D=(V,A)，在V 中指定了一个点，称为发点(或源，记为vs，其入度为0)，和另一个点，称为收点(或汇，记为vt，其出度为0)，其余点叫中间点， 对D
9、的每条弧(vi ,vj)对应有一个非负数cij ,称为弧的容量，这样的网络D称为容量网络（或运输网络），常记做D =(V,A,C)。 对任一D中的弧(vi ,vj)有流量fij ，称集合 f= fij 为网络D上的一个流。,例 网络 D 及其一个流,vs为发点(源)，vt为收点(汇)，其余点为中间点。 对每条弧(vi ,vj)，有弧的容量cij ，弧的流量fij ， 常记做(fij , cij ).,如 fs1 = 5， f12 = 4 ， f42 = 2.,集合 f= fij 称为网络D上的一个流.,2. 可行流与最大流,称满足下列条件的流 f 为可行流： (1)容量限制条件：对所有弧(vi
10、 ,vj) ，成立 (2)平衡条件：对所有中间顶点 v ，成立 其中，f +(v)是流出v 的总流量， f -(v)是流入v的总流量， 对于源点v s和汇点 vt ，流出源点vs 的流量等于流入汇点v t的流量.,称之为流 f 的值，记为val f 或v( f ).,可行流总是存在的。 例如令所有弧的流量 fij=0，就得到一个可行流 f = 0 (称为零流)，其流量 v(f)=0. 所谓最大流问题就是在容量网络中，寻找流量最大的可行流。,最大流问题实际是个线性规划问题，但是利用它与图的紧密关系，能更为直观简便地求解。,v(f)=7.,3. 割集,设S、S是网络D的两个顶点子集,且 且 , 定
11、义D的一个割集(简称割)为 也称为分离vs和vt一个割集，可简记为K .,割集,六、最小费用最大流问题,例：求如下网络的最小费用最大流，弧旁为,应用模型：无线电信道分配（MCM 2000 B）,寻找一个模型，把无线电信道分配到一个大的平面区域的一些传送站的均衡网络上，以避免干扰。一个基本的方法是将此区域分成正六边形的格子(蜂窝状)，如图。传送站安置在每个正六边形的中心点.,频谱的一个区间容许作为各传送站的频率，将这一区间规则地分割成一些空间信道，用整数1,2,3,来表示。每一个传送站将被配置一正整数信道.同一信道可以在许多传送站使用，前提是相邻近的传送站不相互干扰。,频谱需要根据某些限制来设定
12、信道，我们的目标是极小化频谱的这个区间宽度。这可以用跨度这一概念。跨度是在滿足限制的所有配置中，任何传送站使用的最大信道的最小值。在一个获得一定跨度的配置中不要求小于跨度的每一信道都被使用。令s为一个正六边形的边长.。我们集中考虑存在两种干扰水平的情况。 要求A: 频率配置有几个限制,第一,相距4s以内的传送站不能配给同一信道。第二，由于波谱的传播，相距2s以内的传送站不能配给相同或相邻的信道：它们至少差2.在這些限制下,关于跨度能说些什么.,要求B: 假定前述图中的格子在各方向延伸到任意远,重复要求A. 要求C: 更一般地，假定相距2s以内的传送站的信道至少相差一个给定的整数k，相距4s以内
13、的传送站的至少相差1。重复要求A和B。将跨度和设计配置的有效策略作为k的一个函数，能说点什么。 要求D: 考虑问题的一般化，比如各种干扰水平,或不规则的传送站布局。其他什么因素在考虑中是重要的。 要求E: 写一篇短文(不超过两页)给地方报纸,阐述你的发现。,这个问题本质上是一个图论中的染色问题，但问题B 又与传统的染色问题不尽相同，它不仅限制了相邻的传送站的信道，并且还增加了对“隔开一点”的传送站的信道限制， 用经典染色理论的方法无法彻底解决。,图1. 六边形蜂窝系统 图2. 无限六正则格子图,定义：对简单图 ,设 , 若对任意两个顶点 ，有 则称 f 为 G 的一个 L(2,1)-标号或 L(2,1)-染色。,图的 L(2,1)- 标号：,更一般地，归结为图的 L(k1,k2, , kp)-标号问题。,