第10章图论.ppt

《第10章图论.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图与网络分析GraphTheoryandNetworkAnalysis图论运筹学的重要分支主要应用领域物理学、化学、控制论、信息论、科学管理、电子计算机等图论理论和方法应用实例在组织生产中，为完成某项生产任务，各工序之间怎样衔接，才能使生产任务完成得既快又好。一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按照怎样的路线走，所走的路程最短。各种通信网络的合理架设，交通网络的合理分布等问题，应用图论的方法求解都很简便。1图与网络分析GraphTheoryandNetworkAnalysis图与网络分析十八世纪的哥尼斯堡城中流过一条河（普雷.

2、格尔河），河上有7座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样一个游戏：一个游者怎样才能一次连续走过这7座桥，回到原出发点，而每座桥只允许走一次。没有人想出走法，又无法说明走法不存在，这就是著名的“哥尼斯堡7桥”难题。2图与网络分析GraphTheoryandNetworkAnalysis图与网络分析Euler用4个点表示连接着河的两岸和河中的两个小岛，7条线表示7座桥，将“哥尼斯堡7桥”问题抽象为一个图论模型。如图，从而抽象为一个数学问题：能否从某一点出发，经过图中每条边一次且仅一次，并回到出发点，即一笔画问题，也称之为Euler回路。3图

3、与网络分析GraphTheoryandNetworkAnalysis图与网络分析“哥尼斯堡7桥”难题最终在1736年由数学家Euler的一篇论文给予了完满的解决，这是图论的第一篇论文。在后来的两百年间图论的发展是缓慢的，直到1936年匈牙利数学家O.König写出了图论的第一本专著《有限图与无限图的理论》。4图与网络分析GraphTheoryandNetworkAnalysis图与网络分析图论的历史上最具有传奇色彩的问题也许要数著名的“四色猜想”了——历史上许许多多数学猜想之一。它描述对一张地图着色的问题，曾经有一位数学家这样说：“对于这个问题，一位数学家可

4、以用不到五分钟的时间向马路上任何一位行人讲述清楚它，然后，两人都明白这一问题，但是，两人都无能为力。”幸运的是在1970’s终于由美国的两位数学家借助大型计算机将其证明了。5图与网络分析GraphTheoryandNetworkAnalysis图与网络的基本概念图论与网络分析理论所研究的问题十分广泛，内容极其丰富。正如一位数学家所说：“可以说，图论为任何一个包含了某种二元关系的系统提供了一种分析和描述的模型。”下面我们来看一个案例——国庆大假期间旅游非常火爆，机票早已订购一空。成都一家旅行社由于信誉好、服务好，所策划的国庆首都游的行情看好，要求参加的游客众多

5、，游客甚至不惜多花机票钱暂转取道它地也愿参加此游。旅行社只好紧急电传他在全国各地的办事处要求协助解决此问题。很快，各办事处将其已订购机票的情况传到了总社。根据此资料，总社要作出计划，最多能将多少游客从成都送往北京以及如何取道转机。下面是各办事处已订购机票的详细情况表：6图与网络分析GraphTheoryandNetworkAnalysis图与网络的基本概念各办事处已订购机票情况表：成都重庆武汉上海西安郑州沈阳昆明广州北京成都1015158121030重庆561525武汉10上海158西安86郑州148沈阳18昆明810广州826107图与网络分析GraphT

6、heoryandNetworkAnalysis图与网络的基本概念将此问题通过图的模型描述：下图中，点——各城市，带箭头连线——从箭尾城市到箭头城市已订购有机票，带箭头连线旁的数字——机票数量。成重武昆上广西郑沈京8郑州办事处已订有的到北京的机票数量。8图与网络分析GraphTheoryandNetworkAnalysis图与网络的基本概念案例——某单位储存八种化学药品，其中有些药品是不能存放在同一个库房里的，为了反映这个情况，可以用点vi表示八种药品，若药品vi和vj是不能放在同一个库房的，则在他们之间联一条线。9图与网络分析GraphTheoryandNe

7、tworkAnalysisv1v8v7v6v5v4v3v210图与网络分析GraphTheoryandNetworkAnalysis图与网络的基本概念图论中所研究的图并非几何学中的图，也不是绘画中的图。在这里我们所关心的仅仅是图中有多少个点，点与点之间有无线来连接，也就是说我们研究的是某个系统中的元素——点，以及这些元素之间的某种关系——连线。定义：图——一个图G是一个有序二元组（V，E），记为G=（V，E）其中（1）V是一个有限非空的集合，其元素称为G的点或顶点，而称V为G的点集V={v1，v2，···，vn}；（2）E是V中元素的无序对(vi，vj)所构

8、成的一个集合，其元素称为G的边，一般表示为e=(vi