运筹学图的基本概念与模型在一个棋盘中，若马马（马走日步）能否从某一点出发跳遍棋盘上对于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个顶点的完全图不 是平面图。平面图在印刷电路板中有重要的应用。 平面图与网络 图 的 基 本 概 念 与 模 型