OR-chapter 6 图与网络分析.pdfVIP

Chapter 6 图与网络分析 本章主要内容： 图与网络的基本知识 中国邮路问题（略） 最短路问题 最大流问题 图与网络的基本知识 图论起源——哥尼斯堡七桥问题 A A 一 笔 C D C D 画 问 B 题 问题：一个散步者能否从任一 B 块陆地出发，走过七座桥，且 每座桥只走过一次，最后回到 出发点？ 结论：不能。每个结点关联的 边数要均为偶数。 补充：图论发展史 图论是组合数学的一个分支，也是近几十年来最活跃的 数学分支之一.到目前为止，它已有二百六十多年的发展历 史.图论的发展历史大体可以分为三个阶段： 第一阶段是图论的萌芽阶段，它从十八世纪中叶到十九世纪 中叶.这时，图论的多数问题是围绕游戏而产生的，其代表 性的工作就是Königsberg七桥问题.1736年L.Euler发表了 他著名的Königsberg七桥问题的论文，这是图论的第一篇文 章. 第二阶段从十九世纪中叶到二十世纪中叶.在此阶段， 图论问题大量出现.如著名的四色问题、Hamilton问题 以及图的可平面问题等. 在第二个阶段还应该特别提 到Cayley把树应用于化学领域，Kirchhoff用树去研究 电网络的分析问题.在漫长的300年中，图论几乎停留 在数学游戏阶段.虽然这阶段里21岁的G.Kirchhoff在 1847年从电网络问题，A.Cayley在1857年从计算有机 化学的同分异构等不止一次地建立起图论的基本概念 ，但是直到1936年D.König发表的经典著作有限图与 无限图理论才有了图论的第一本专著. 二十世纪中叶以后是图论发展的第三阶段，即图论的 应用阶段.由于生产管理、军事、交通运输、计算机 网络、计算机科学、数字通讯、线性规划、运筹学等 方面提出的实际问题的需要，特别是许多离散性问题 的出现、刺激和推动，以及由于有了大型电子计算机 ，而使大规模问题的求解成为可能，图论及其应用的 研究得到了飞速的发展.这个阶段的开创性工作是以 Ford和Fulkerson建立的网络流理论为代表的.图论与 其它学科的相互渗透，以及图论在生产实际中广泛地 应用，都使图论的发展更加充满活力. 图与网络的基本知识 图论中图是由点和边构成，可以反映一些对象之间的关系。 一般情况下图中点的相对位置如何、点与点之间联线的长短 曲直，对于反映对象之间的关系并不是重要的。 图的定义： 若用点表示研究的对象，用边表示这些对象之间的联系， 则图G可以定义为点(顶点)和边的集合，记作： G {V, E } 其中: V——点集 E——边集 ※图G区别于几何学中的图。这里只关心图中有多少个点以 及哪些点之间有连线。 图与网络的基本知识 例如：在一个人群中，对相互认识这个关系我们可以用图来 表示。 e (v )孙 (v ) 2 3 1 赵 (v ) 5