第七章图与网络优化.pptVIP

引言 图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。 引言 随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。 引言 十八世纪的哥尼斯堡城中流过一条河（普雷.格尔河），河上有 7 座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样一个游戏：一个游者怎样才能一次连续走过这 7 座桥，回到原出发点，而每座桥只允许走一次。没有人想出走法，又无法说明走法不存在，这就是著名的“哥尼斯堡 7 桥”难题。 引言 引言 引言 为了寻找答案，1736年欧拉将这个问题抽象一笔画问题。 即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。 欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。 引言 下面我们来看一个案例—— 国庆大假期间旅游非常火爆，机票早已订购一空。 成都一家旅行社由于信誉好、服务好，所策划的国庆首都游的行情看好，要求参加的游客众多，游客甚至不惜多花机票钱暂转取道它地也愿参加此游。 旅行社只好紧急电传他在全国各地的办事处要求协助解决此问题。很快，各办事处将其已订购机票的情况传到了总社。 根据此资料，总社要作出计划，最多能将多少游客从成都送往北京以及如何取道转机。下面是各办事处已订购机票的详细情况表： 引言 各办事处已订购机票情况表： 引言 将此问题通过图的模型描述： 下图中，点——各城市， 带箭头连线——从箭尾城市到箭头城市已订购有机票，带箭头连线旁的数字——机票数量。 图的基本概念 在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。 例1:图7.2是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。 图的基本概念 图的基本概念 例2:有六支球队进行足球比赛，我们分别用点v1…v6表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用图7.3所示的有向图反映出来。 图的基本概念 图的基本概念 图及其分类和术语 图论中我们所关心的仅仅是图中有多少个点，点与点之间有无线来连接， 即我们研究的是某个系统中的元素——点， 以及这些元素之间的某种关系——连线。 图的基本概念 从以上的几个例子可以看出，我们用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。 一般来说，通常用点表示研究对象用点与点之间的线表示研究对象之间的特定关系。 由于在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要。 因此，图论中的图与几何图，工程图等本质上是不同的。 图的基本概念 图论中的图是由点和点与点之间的线所组成的。 把点与点之间不带箭头的线叫做边， 带箭头的线叫做弧。 如果一个图是由点和边所构成的，称为无向图，记作G =(V，E)， V ：表示图 G 的点集合，E：表示图G的边集合。 连接点vi,vj?V的边记作[vi,vj]，或者[vj,vi]。 图的基本概念 如果图是由点和弧所构成的，称为有向图，记作D =(V,A)， V 表示有向图D的点集合， A 表示有向图D的弧集合。 一条方向从vi指向vj的弧，记作(vi,vj)。 图的基本概念 例：图7-7 是一个无向图。在G=(V,E)中，V={v1,v2,v3,v4}， E={e1,e2,e3,e4 ,e5,e6,e7}。 图的基本概念 图的基本概念 图的基本概念 无向图G=(V,E)中 端点：若边e=[v,u]∈E，则称v,u是e的端点，也称 vi,vj是相邻的。 关连边：v,u是相邻的，称e是点v及点u的关连边。 环：若图G中，某条边的两个端点相同，则称e是环。 图的基本概念 图的基本概念 图的基本概念 图的基本概念 定理2：任意一个图中，奇点的个数为偶数。 证明：设V1和V2分别是G中奇点和偶点的集合，由定理1，有 图的基本概念 图的基本概念 图的基本概念 例：图7-9中 (v1，v2， v3，v4 ， v5， v3， v6，v7