研究生课程教学大纲 (1)匹配理论是图论的一个重要研究分支，研究内容已经很丰富，学科发展体系相对成熟 2009年，Lovasz和Plummer合作出版了Matching Theory,2ed,是该领域非常重要的专 著.匹配理论在化学图论，统计物理，经济学，互连网络中都有方法应用 (2)图的最小点覆盖可以理解为，在一个道路交通网络中（路都是直线，且没有孤立的点）， 用最少的警察（或摄像头）去监控整个系统 (3)Tutte定理：图G有完美匹配当且仅当对V(G)的任意子集S,都有G-S的奇分支的个 数不超过SL.需要说明的是，子集S是G的任意真子集（可以为空集）.Tute定理在处 理非二部图的完美匹配存在性相关问题有强大的作用.更加值得一提的是，由Tue定 理可以得出Petersen定理：3-正则无桥图都有完美匹配.20世纪70年代，Lovasz和 Plummer猜想，3-正则无桥图的完美匹配个数是阶数的指数函数. 第六章：平面图(8学时) 1本章教学内容： (1)平面图的概念与性质(2学时)，(2)特殊平面图与平面图的对偶图(2学时)，(3)平 面图的判定与涉及平面性不变量(2学时)，(4)平面性算法(2学时)。 2本章教学要求： 通过本章课程的学习，要求学生理解图的平面性问题的实际意义，掌握平面图的性质，平面 图的判定，平面性算法。 3本章教学重点：平面图的性质和平面性算法。 4本章教学难点：平面图的判定。 课程思政： (1)在电路板设计时，需要考虑的问题之一是连接电路元件间的导线间不能交叉（导线未绝 缘).否则，会出现短路故障.显然，电路板可以模型为一个图，“要求电路元件间连接 导线互不交叉”，对应于“要求图中的边不能相互交叉”， (2)波兰数学家Kasimir Kuratowski最早(20世纪30年代)给出图的平面性判定充要条件. 后来，美国数学家Whitney,加拿大数学家Tutte,我国数学家吴文俊等都给出了不同的 充要条件 (3)如何刻画非可平面图的差别，即不可平面性的程度呢？有如下几个常见的指标：)将 图嵌入到一些曲面，通过曲面的拓扑不变量来衡量图的可平面性；b)印刷电路板的厚 度与对应图的厚度有直接的关系：c)图的交叉数（在VLSI设计和关联几何中也有应用） 由匈牙利数学家Pal Tura从实际问题出发建立二部图模型首先研究，并在刻画非平面 图方面有重要的应用。 5研究生课程教学大纲 5 (1) 匹配理论是图论的一个重要研究分支, 研究内容已经很丰富, 学科发展体系相对成熟. 2009 年, Lovász 和 Plummer 合作出版了 Matching Theory, 2ed, 是该领域非常重要的专 著. 匹配理论在化学图论, 统计物理, 经济学, 互连网络中都有方法应用. (2) 图的最小点覆盖可以理解为, 在一个道路交通网络中(路都是直线, 且没有孤立的点), 用最少的警察(或摄像头)去监控整个系统. (3) Tutte 定理: 图 G 有完美匹配当且仅当对 V(G)的任意子集 S, 都有 G−S 的奇分支的个 数不超过|S|. 需要说明的是, 子集 S 是 G 的任意真子集(可以为空集). Tutte 定理在处 理非二部图的完美匹配存在性相关问题有强大的作用. 更加值得一提的是, 由 Tutte 定 理可以得出 Petersen 定理: 3-正则无桥图都有完美匹配. 20 世纪 70 年代, Lovász 和 Plummer 猜想, 3-正则无桥图的完美匹配个数是阶数的指数函数. 第六章：平面图(8 学时) 1 本章教学内容： (1) 平面图的概念与性质（2 学时），(2) 特殊平面图与平面图的对偶图（2 学时），(3) 平 面图的判定与涉及平面性不变量（2 学时），(4)平面性算法（2 学时）。 2 本章教学要求： 通过本章课程的学习，要求学生理解图的平面性问题的实际意义，掌握平面图的性质，平面 图的判定，平面性算法。 3 本章教学重点：平面图的性质和平面性算法。 4 本章教学难点：平面图的判定。 课程思政: (1) 在电路板设计时，需要考虑的问题之一是连接电路元件间的导线间不能交叉(导线未绝 缘). 否则，会出现短路故障. 显然，电路板可以模型为一个图，“要求电路元件间连接 导线互不交叉”，对应于“要求图中的边不能相互交叉”. (2) 波兰数学家 Kasimir Kuratowski 最早(20 世纪 30 年代)给出图的平面性判定充要条件. 后来，美国数学家 Whitney, 加拿大数学家 Tutte, 我国数学家吴文俊等都给出了不同的 充要条件. (3) 如何刻画非可平面图的差别, 即不可平面性的程度呢? 有如下几个常见的指标: a) 将 图嵌入到一些曲面, 通过曲面的拓扑不变量来衡量图的可平面性; b) 印刷电路板的厚 度与对应图的厚度有直接的关系; c) 图的交叉数(在VLSI设计和关联几何中也有应用) 由匈牙利数学家 Pál Turán 从实际问题出发建立二部图模型首先研究, 并在刻画非平面 图方面有重要的应用