运筹学Chapter8图与网络分析(Graph Theory and Network Analysis本章主要内容图的基本概念与模型树与图的最小树最短路问题网络的最大流米China University of Mining and Technology
China University of Mining and Technology 运 筹 学 Chapter8 图与网络分析 ( Graph Theory and Network Analysis ) 图的基本概念与模型 树与图的最小树 最短路问题 网络的最大流 本章主要内容：
运筹学学习要点：1.掌握一般图论及其基本概念；2.能够应用最短路算法求解实际问题；3.掌握最大流最小割理论。-2-China University of Mining and Technology
China University of Mining and Technology -2- 运 筹 学 学习要点： 1.掌握一般图论及其基本概念； 2.能够应用最短路算法求解实际问题； 3.掌握最大流最小割理论
运筹学图的基本概念与模型七桥问题（现为加里宁格勒）。市内18世纪，Konigsberg是俄罗斯的一个城市有七座桥。人们在此散步，问：“能否从某处出发，经过每座桥一次万且恰好一次又回到出发点？KONINGSBEKGA1736年，Euler巧妙地将此问题化为图的不重复一笔画问题，并证明了该问题不存在肯定回答，发表了第一篇论文2-3-China University of Mining and Technology
China University of Mining and Technology -3- 运 筹 学 18世纪，Königsberg是俄罗斯的一个城市（现为加里宁格勒）。市内 有七座桥。人们在此散步，问：“能否从某处出发，经过每座桥一次 且恰好一次又回到出发点？” 1736年，Euler 巧妙地将此问 题化为图的不 重复一笔画问 题，并证明了 该问题不存在 肯定回答，发 表了第一篇论 文。 七桥问题 图 的 基 本 概 念 与 模 型
运筹学图的基本概念与模型中国邮路问题一邮递员送信，要走完他所负责的全部街道分送信件最后返回邮局。邮递员都会本能地以尽可能少的行程完成送信任务。如何走路线最短。O1962年，由我国数学家管梅谷提出，国国际上称为中国邮递员问题〇问题：求一个圈，过每边至少一次，并使圈的长度最短。-4-ChinaUniversityof Mining and Technolog)
China University of Mining and Technology -4- 运 筹 学 中国邮路问题 一邮递员送信，要走完他所负责的全部街道分送信件， 最后返回邮局。邮递员都会本能地以尽可能少的行程 完成送信任务。如何走路线最短。 1962年，由我国数学家管梅谷提出，国际上称为中国邮 递员问题。 问题：求一个圈，过每边至少一次，并使圈的长度最短。 图 的 基 本 概 念 与 模 型
运筹学图的基本概念与模型Hamilton图游戏：用正十二面体上20个顶点表示20个城市，要求参加游戏者沿着各边行走，走遍每一个城市且仅走一次，最后回到出发城市。问题：如何判断一个图是否具有这样的性质。如果有，这样的行走路线如何确定。显然这样的路线存在且不唯一the dodecahedron is Hamiltonian5-米China University of Mining and Technology
China University of Mining and Technology -5- 运 筹 学 Hamilton图 游戏：用正十二面体上20个顶点表示20个城市，要求参加游 戏者沿着各边行走，走遍每一个城市且仅走一次，最后回到 出发城市。 问题：如何判断一个图是否具有 这样的性质。如果有，这样的行 走路线如何确定。 the dodecahedron is Hamiltonian 显然这样的路线存在且不唯一 图 的 基 本 概 念 与 模 型