第10单元图论.pptVIP

图与网络分析 Graph Theory and Network Analysis 图论 运筹学的重要分支 主要应用领域 物理学、化学、控制论、信息论、科学管理、电子计算机等 图论理论和方法应用实例 在组织生产中，为完成某项生产任务，各工序之间怎样衔接，才能使生产任务完成得既快又好。 一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按照怎样的路线走，所走的路程最短。 各种通信网络的合理架设，交通网络的合理分布等问题，应用图论的方法求解都很简便。 图与网络分析 Graph Theory and Network Analysis 图与网络分析 十八世纪的哥尼斯堡城中流过一条河（普雷.格尔河），河上有 7 座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样一个游戏：一个游者怎样才能一次连续走过这 7 座桥，回到原出发点，而每座桥只允许走一次。没有人想出走法，又无法说明走法不存在，这就是著名的“哥尼斯堡 7 桥”难题。 图与网络分析 Graph Theory and Network Analysis 图与网络分析 Euler用4个点表示连接着河的两岸和河中的两个小岛，7条线表示7 座桥， 将“哥尼斯堡 7 桥”问题抽象为一个图论模型。如图，从而抽象为一个数学问题：能否从某一点出发，经过图中每条边一次且仅一次，并回到出发点，即一笔画问题，也称之为Euler回路。 图与网络分析 Graph Theory and Network Analysis 图与网络分析 “哥尼斯堡 7 桥”难题最终在 1736 年由数学家 Euler 的一篇论文给予了完满的解决，这是图论的第一篇论文。在后来的两百年间图论的发展是缓慢的，直到 1936 年匈牙利数学家 O.K?nig写出了图论的第一本专著《有限图与无限图的理论》。 图与网络分析 Graph Theory and Network Analysis 图与网络分析 图论的历史上最具有传奇色彩的问题也许要数著名的“四色猜想”了——历史上许许多多数学猜想之一。它描述对一张地图着色的问题，曾经有一位数学家这样说：“对于这个问题，一位数学家可以用不到五分钟的时间向马路上任何一位行人讲述清楚它，然后，两人都明白这一问题，但是，两人都无能为力。”幸运的是在 1970’s 终于由美国的两位数学家借助大型计算机将其证明了。 图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 图论与网络分析理论所研究的问题十分广泛，内容极其丰富。正如一位数学家所说：“可以说，图论为任何一个包含了某种二元关系的系统提供了一种分析和描述的模型。” 下面我们来看一个案例—— 国庆大假期间旅游非常火爆，机票早已订购一空。成都一家旅行社由于信誉好、服务好，所策划的国庆首都游的行情看好，要求参加的游客众多，游客甚至不惜多花机票钱暂转取道它地也愿参加此游。旅行社只好紧急电传他在全国各地的办事处要求协助解决此问题。很快，各办事处将其已订购机票的情况传到了总社。根据此资料，总社要作出计划，最多能将多少游客从成都送往北京以及如何取道转机。下面是各办事处已订购机票的详细情况表： 图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 各办事处已订购机票情况表： 图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 将此问题通过图的模型描述： 下图中，点——各城市，带箭头连线——从箭尾城市到箭头城市已订购有机票，带箭头连线旁的数字——机票数量。 图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 案例—— 某单位储存八种化学药品，其中有些药品是不能存放在同一个库房里的，为了反映这个情况，可以用点vi表示八种药品，若药品vi和vj是不能放在同一个库房的，则在他们之间联一条线。 图与网络分析 Graph Theory and Network Analysis 图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 图论中所研究的图并非几何学中的图，也不是绘画中的图。在这里我们所关心的仅仅是图中有多少个点，点与点之间有无线来连接，也就是说我们研究的是某个系统中的元素——点，以及这些元素之间的某种关系——连线。 定义：图——一个图G 是一个有序二元组（V，E），记为 G =（V，E）其中（1） V 是一个有限非空的集