1、China University of Mining and Technology运筹学 Chapter6 图与网络分析( Graph Theory and Network Analysis )图的基本概念与模型树与图的最小树最短路问题网络的最大流本章主要内容：本章主要内容：China University of Mining and Technology-2-运筹学 学习要点：1.掌握一般 图论及其基本概念；2.能够应用最短路算法求解实际问题；3.掌握最大流最小割理论。China University of Mining and Technology-3-运筹学 6.1 图的基本概念和模型C
2、hina University of Mining and Technology-4-运筹学 长 江汉江武昌武昌汉口汉口汉阳汉阳您能从武汉理工大学出发走过每座桥且只走一次然后回到学校吗 ?图的基本概念与模型China University of Mining and Technology-5-运筹学 18世纪， Knigsberg是俄罗斯的一个城市（现为加里宁格勒）。市内有七座桥。人们在此散步，问： “能否从某处出发，经过每座桥一次且恰好一次又回到出发点？ ”1736年， Euler巧妙地将此问题化为图的不重复 一笔画问题 ，并证明了该问题不存在肯定回答，发表了第一篇论文。七 桥 问题图的基本
3、概念与模型China University of Mining and Technology-6-运筹学 这个问题是基于一个现实生活中的事例 :位于当时东普鲁士柯尼斯堡 (今日俄罗斯加里宁格勒 )有一条河，河中心有两个小岛。小岛与河的两岸有七条桥连接。如何才能在所有桥都恰巧只走一遍的前提下，回到原出发点？ 图的基本概念与模型China University of Mining and Technology-7-运筹学 不少数学家都尝试去解析这个事例。而这些解析，最后发展成为了数学中的 图论 。莱昂哈德 欧拉 (Leonhard Euler)在 1736年圆满地解决了这一问题，证明这种方法 并不
4、存在 。他在圣彼得堡科学院发表了图论史上第一篇重要文献。欧拉把实际的抽象问题简化为平面上的 点与线 组合，每一座桥视为一条线，桥所连接的地区视为点。这样若从某点出发后最后再回到这点，则 这一点的线数必须是偶数 。 图的基本概念与模型China University of Mining and Technology-8-运筹学 ACBDACBD如何才能在所有桥都恰巧只走一遍的前提下，回到原出发点？求从图中任一点出发，通过每条边一次，最后回到起点。桥所连接的地区视为点每一座桥视为一条线图的基本概念与模型China University of Mining and Technology-9-运筹学
5、如果通奇数座桥的地方 不止两个 ，那么满足要求的路线便 不存在 了。如果 只有两个 地方通奇数座桥，则可从 其中一地 出发可找到经过所有桥的路线。若 没有一个地方 通奇数座桥，则从 任何一地 出发，所求的路线都能实现。图的基本概念与模型China University of Mining and Technology-10-运筹学 中国邮路问题中国邮路问题一邮递员送信，要走完他所负责的全部街道分送信件，最后返回邮局。邮递员都会本能地以尽可能少的行程完成送信任务。如何走路线最短。1962年，由我国数学家管梅谷提出，国际上称为 中国邮递员问题 。问题 ：求一个圈，过每边至少一次，并使圈的长度最短。图的基本概念与模型
