运筹学课件第8章 图与网络分析.

《运筹学课件第8章 图与网络分析.》由会员分享，可在线阅读，更多相关《运筹学课件第8章 图与网络分析.（59页珍藏版）》请在文档大全上搜索。

1、图与网络模型Graph Theory引言引言 十八世纪的哥尼斯堡城中流过一条河（普雷十八世纪的哥尼斯堡城中流过一条河（普雷.格尔河），河上有格尔河），河上有 7 座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样一个游戏：一个游者怎样才能一次连续走过这一个游戏：一个游者怎样才能一次连续走过这 7 座桥，回到原出发点，座桥，回到原出发点，而每座桥只允许走一次。没有人想出走法，又无法说明走法不存在，而每座桥只允许走一次。没有人想出走法，又无法说明走法不存在，这就是著名的这就是著名的“哥尼斯堡哥尼斯堡 7 桥桥”难题。难题。ABC

2、D图与网络模型Graph Theory引言引言 “哥尼斯堡哥尼斯堡 7 桥桥”难题最终在难题最终在 1736 年由数学家年由数学家 Euler 的一篇论文给的一篇论文给予了完满的解决，这是图论的第一篇论文。在后来的两百年间图论的予了完满的解决，这是图论的第一篇论文。在后来的两百年间图论的发展是缓慢的，直到发展是缓慢的，直到 1936 年匈牙利数学家年匈牙利数学家 O.Knig写出了写出了图论的第一图论的第一本专著本专著有限图与无限图的理论有限图与无限图的理论。 在图论的发展过程中还有两位著名科学家值得一提，他们是克希在图论的发展过程中还有两位著名科学家值得一提，他们是克希霍夫和凯莱。克希霍夫在

3、研究电网络时对图的独立回路理论作出了重霍夫和凯莱。克希霍夫在研究电网络时对图的独立回路理论作出了重要的贡献，而化学家凯莱在对碳氢化合物的同分异构体的数量进行计要的贡献，而化学家凯莱在对碳氢化合物的同分异构体的数量进行计数时推动了图论中树的计数问题的研究。数时推动了图论中树的计数问题的研究。 图论的历史上最具有传奇色彩的问题也许要数著名的图论的历史上最具有传奇色彩的问题也许要数著名的“四色猜想四色猜想”了了历史上许许多多数学猜想之一。它描述对一张地图着色的问题，历史上许许多多数学猜想之一。它描述对一张地图着色的问题，曾经有一位数学家这样说：曾经有一位数学家这样说：“对于这个问题，一位数学家可以用

4、不到对于这个问题，一位数学家可以用不到五分钟的时间向马路上任何一位行人讲述清楚它，然后，两人都明白五分钟的时间向马路上任何一位行人讲述清楚它，然后，两人都明白这一问题，但是，两人都无能为力。这一问题，但是，两人都无能为力。”幸运的是在幸运的是在 1970s 终于由美国终于由美国的的两位数学家借助大型计算机将其证明了。两位数学家借助大型计算机将其证明了。图与网络模型Graph Theory图与网络的基本概念图与网络的基本概念 图论与网络分析理论所研究的问题十分广泛，内容极其丰富。正图论与网络分析理论所研究的问题十分广泛，内容极其丰富。正如一位数学家所说：如一位数学家所说：“可以说，图论为任何一个

5、可以说，图论为任何一个包含了某种二元关系包含了某种二元关系的系统提供了一种分析和描述的模型。的系统提供了一种分析和描述的模型。” 下面我们来看一个案例下面我们来看一个案例 国庆大假期间旅游非常火爆，机票早已订购一空。成都一家旅行国庆大假期间旅游非常火爆，机票早已订购一空。成都一家旅行社由于信誉好、服务好，所策划的国庆首都游的行情看好，要求参加社由于信誉好、服务好，所策划的国庆首都游的行情看好，要求参加的游客众多，游客甚至不惜多花机票钱暂转取道它地也愿参加此游。的游客众多，游客甚至不惜多花机票钱暂转取道它地也愿参加此游。旅行社只好紧急电传他在全国各地的办事处要求协助解决此问题。很旅行社只好紧急电

6、传他在全国各地的办事处要求协助解决此问题。很快，各办事处将其已订购机票的情况传到了总社。根据此资料，总社快，各办事处将其已订购机票的情况传到了总社。根据此资料，总社要作出计划，最多能将多少游客从成都送往北京以及如何取道转机。要作出计划，最多能将多少游客从成都送往北京以及如何取道转机。下面是各办事处已订购机票的详细情况表：下面是各办事处已订购机票的详细情况表：图与网络模型Graph Theory图与网络的基本概念图与网络的基本概念各办事处已订购机票情况表各办事处已订购机票情况表成都成都重庆重庆武汉武汉上海上海西安西安郑州郑州沈阳沈阳昆明昆明广州广州北京北京成都成都 重庆重庆 武汉武汉 上海上海

7、西安西安 郑州郑州 沈阳沈阳 昆明昆明 广州广州 北京北京10 5 15 8 12 10 3010 6 15 25 10 15 8 8 6 14 8 18 8 10 8 2 6 10 图与网络模型Graph Theory图与网络的基本概念图与网络的基本概念 将此问题通过图的模型描述：将此问题通过图的模型描述：下图中，点下图中，点各城市，带箭头连线各城市，带箭头连线从箭尾城市到箭头城市已订从箭尾城市到箭头城市已订购有机票，带箭头连线旁的数字购有机票，带箭头连线旁的数字机票数量。机票数量。成成重重武武昆昆上上广广西西郑郑沈沈京京8郑州办事处已订郑州办事处已订有的到北京的有的到北京的机票数量。机票数

8、量。图与网络模型Graph Theory图与网络的基本概念图与网络的基本概念一、一、图及其分类和术语图及其分类和术语 1、 图论中所研究的图并非几何学中的图，也不是绘画中的图。在这图论中所研究的图并非几何学中的图，也不是绘画中的图。在这里我们所关心的仅仅是图中有多少个点，点与点之间有无线来连接，里我们所关心的仅仅是图中有多少个点，点与点之间有无线来连接，也就是说我们研究的是某个系统中的元素也就是说我们研究的是某个系统中的元素点，以及这些元素之间点，以及这些元素之间的某种关系的某种关系连线。连线。定义：定义：图图一个图一个图G是一个有序二元组（是一个有序二元组（V，E），记为），记为G=（V，E

9、）其中（其中（1） V是一个有限非空的集合，其元素称为是一个有限非空的集合，其元素称为G的点或顶点，而称的点或顶点，而称V为为G的点集的点集 V=v1，v2，vn；（；（2）E是是V中元素的无序对中元素的无序对(vi，vj)所所构成的一个集合，其元素称为构成的一个集合，其元素称为G的边，一般表示为的边，一般表示为 e =(vi，vj)，而称，而称E是是G的边集。的边集。 边（无向边）边（无向边）没有方向的连线没有方向的连线弧（有向边）弧（有向边）带有方向的连线带有方向的连线无向图无向图 有向图有向图 简单图简单图 多重图多重图完全图完全图 二部图（偶图，双图）二部图（偶图，双图）图与网络模型G

10、raph Theory图与网络的基本概念图与网络的基本概念子图子图 真子图真子图生成子图生成子图 点生成子图点生成子图 边生成子图边生成子图点的次点的次 奇次点奇次点 偶次点偶次点链链 圈圈 路路 回路回路 赋权图赋权图2、连通图连通图 在众多各类图中有一类在实际应用中占有重要地位的图在众多各类图中有一类在实际应用中占有重要地位的图 连通图连通图在图中，任意两点间至少存在着一条链在图中，任意两点间至少存在着一条链连通图连通图不连通图不连通图图与网络模型Graph Theory图与网络的基本概念图与网络的基本概念3、图与矩阵图与矩阵 在图与网络分析的应用中，将面临一个问题在图与网络分析的应用中，

11、将面临一个问题如何分析、计算一如何分析、计算一个较大型的网络，这当然需借助快速的计算工具个较大型的网络，这当然需借助快速的计算工具计算机。那么，如计算机。那么，如何将一个图表示在计算机中，或者，如何在计算机中存储一个图呢？现何将一个图表示在计算机中，或者，如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有图的矩阵表示也根据所关心的问题不同而有邻接矩阵、关联矩阵、邻接矩阵、关联矩阵、权矩阵等。权矩阵等。邻接矩阵邻接矩阵对于图对于图G=（V，E），），| V