中国矿业大学：《运筹学》课程教学课件（讲稿）Chapter 8 图与网络分析

运筹学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 显然这样的路线存在且不唯一 图 的 基 本 概 念 与 模 型

运筹学图的基本概念与模型在一个棋盘中，若马马（马走日步）能否从某一点出发跳遍棋盘上对于4×4，5×5，或8×8的每一点恰好一次，再回到出发点？又棋盘上马的跳动如何？11246314372650352312253415386251492140271064133692252332839166148412971205460859453217424532441955647573035315846564318-6-宋China University of Mining and Technology

China University of Mining and Technology -6- 运 筹 学 50 11 24 63 14 37 26 35 23 62 51 12 25 34 15 38 10 49 64 21 40 13 36 27 61 22 9 52 33 28 39 16 48 7 60 1 20 41 54 29 59 4 45 8 53 32 17 42 6 47 2 57 44 19 30 55 3 58 5 46 31 56 43 18 在一个棋盘中，若马（马走日步）能否从某一点出发跳遍棋盘上 每一点恰好一次，再回到出发点？对于4×4，5×5，或8×8的 棋盘上马的跳动如何？ 图 的 基 本 概 念 与 模 型

运筹学图的基本概念与模型幻方问题11948102530399381827297478461737626355141625453436151315424334442131410821623123243441351222231220404911187161913-7-China University of Mining and Technology

China University of Mining and Technology -7- 运 筹 学           8 1 6 3 5 7 4 9 2                       22 31 40 49 2 11 20 21 23 32 41 43 3 12 13 15 24 33 42 44 4 5 14 16 25 34 36 45 46 6 8 17 26 35 37 38 47 7 9 18 27 29 30 39 48 1 10 19 25 幻方问题 图 的 基 本 概 念 与 模 型

运筹学图的基本概念与模型鸽笼原理和Ramsey数某团体举行舞会，其中有n个男士与n个女士，每个男士恰好认识r个女士，每个女士也恰好认识r个男士·问：在这个团中，能否做到：每个男士与其认识的女士跳舞，每个女士也与其认识的男士跳舞。。比如：任意6个人，一定有3个人相互认识或者有3个人相互不认识-8-China Universityof Mining and Technolog)

China University of Mining and Technology -8- 运 筹 学 某团体举行舞会，其中有n 个男士与n 个女士，每个男 士恰好认识 r 个女士，每个女士也恰好认识 r 个男士。 问：在这个团中，能否做到：每个男士与其认识的女士 跳舞，每个女士也与其认识的男士跳舞。 比如：任意6个人，一定有3个人相 互认识或者有3个人相互不认识 鸽笼原理和Ramsey数 图 的 基 本 概 念 与 模 型

运筹学图的基本概念与模型四色猜想能否用四种颜色给地图染色：使相邻的国家有不同的颜色。·问题：能否用四种颜色给平面图的点染色，使有公共边的点有G不同的颜色。-24-9-China University of Mining and Technology

China University of Mining and Technology -9- 运 筹 学 四色猜想 能否用四种颜色给地图染色， 使相邻的国家有不同的颜色。 问题：能否用四种颜色给平面 图的点染色，使有公共边的点有 不同的颜色。 图 的 基 本 概 念 与 模 型

运筹学图的基本概念与模型平面图与网络Mobius在1840年的一次演讲中提出如下问题：一个国王有五个儿子，要求在他死后将国土分成五部分，每个儿子占一部分并建立各自的宫殿。要求每座宫殿之间都有（平面的）路相连且互不相交（不允许立体交叉）。oTietze研究后指出这是不可能的。因为5个顶点的完全图不是平面图。平面图在印刷电路板中有重要的应用。-10-米China Universityof Mining and Technolog)

China University of Mining and Technology -10- 运 筹 学 •Möbius在1840年的一次演讲中提出如下问题：一个国王有五 个儿子，要求在他死后将国土分成五部分，每个儿子占一部分 并建立各自的宫殿。要求每座宫殿之间都有（平面的）路相连 且互不相交（不允许立体交叉）。 Tietze研究后指出这是不可能的。因为5个顶点的完全图不 是平面图。平面图在印刷电路板中有重要的应用。 平面图与网络 图 的 基 本 概 念 与 模 型