研究生课程教学大纲 第七章：图的着色(10学时) 1本章教学内容： (1)图的边着色(2学时)，(2)图的顶点着色(2学时)，(3)与色数有关的几类图、完美 图(2学时)，(4)着色的计数与色多项式(2学时)，(5)List着色与全着色。 2本章教学要求： 通过本章课程的学习，要求学生理解图的着色问题的实际意义，掌握边着色、点着色、全着 色及其应用。 3本章教学重点：着色理论的应用。 4本章教学难点：全着色问题。 课程思政： (I)G.D.Birkhoff为了尝试证明四色定理而定义的一种多项式一即色多项式.图的色多项 式不但可以得到图的色数，而且其系数还有一些”美妙”的组合性质.1968年，Read猜 想色多项式的系数满足下面特点，如系数序列的绝对值满足：(1)单峰性（先增大后减 小)：(2)对数凹性.这个看似简单的问题困扰组合学界近50年，终于在2012年被韩国 新秀June Huh应用代数几何的方法解决（结果发表于J.Amer.Math.Soc.25(2012), 907-927).这表明要在某个方面做出突破性的成果，基础必须要扎实. (2)图的着色问题在图论研究的一个重要方面（包括理论与应用以及在其它学科的应用）， 图的点着色与独立集有深刻的联系，边着色与边独立集（匹配）有深刻的联系（通过确定 Petersen图的边色数给出直观的说明). 第八章：Ramsey定理(4学时) 1本章教学内容： (1)独立集与覆盖(2学时)，(2)Ramsey定理及其应用(2学时)。 2本章教学要求： 通过本章课程的学习，要求学生理解Ramsey问题的理论与实际意义，掌握加莱恒等式和 Ramsey定理的应用。 3本章教学重点：Ramsey问题的典型应用。 4本章教学难点：求Ramsey数。 课程思政： (I)Ramsey理论包含一个重要的哲学理念，即：完全的无序是不可能的.鸽笼原理是这一 6
研究生课程教学大纲 6 第七章：图的着色(10 学时) 1 本章教学内容： (1) 图的边着色（2 学时），(2) 图的顶点着色（2 学时），(3) 与色数有关的几类图、完美 图(2 学时），(4)着色的计数与色多项式（2 学时），(5) List 着色与全着色。 2 本章教学要求： 通过本章课程的学习，要求学生理解图的着色问题的实际意义，掌握边着色、点着色、全着 色及其应用。 3 本章教学重点：着色理论的应用。 4 本章教学难点：全着色问题。 课程思政: (1) G.D. Birkhoff 为了尝试证明四色定理而定义的一种多项式—即色多项式. 图的色多项 式不但可以得到图的色数, 而且其系数还有一些”美妙”的组合性质. 1968 年, Read 猜 想色多项式的系数满足下面特点, 如系数序列的绝对值满足: (1)单峰性(先增大后减 小); (2)对数凹性. 这个看似简单的问题困扰组合学界近 50 年, 终于在 2012 年被韩国 新秀 June Huh 应用代数几何的方法解决(结果发表于 J. Amer. Math. Soc. 25 (2012), 907-927). 这表明要在某个方面做出突破性的成果, 基础必须要扎实. (2) 图的着色问题在图论研究的一个重要方面(包括理论与应用以及在其它学科的应用). 图的点着色与独立集有深刻的联系, 边着色与边独立集(匹配)有深刻的联系(通过确定 Petersen 图的边色数给出直观的说明). 第八章：Ramsey 定理(4 学时) 1 本章教学内容： (1) 独立集与覆盖（2 学时），(2) Ramsey 定理及其应用（2 学时）。 2 本章教学要求： 通过本章课程的学习，要求学生理解 Ramsey 问题的理论与实际意义，掌握加莱恒等式和 Ramsey 定理的应用。 3 本章教学重点：Ramsey 问题的典型应用。 4 本章教学难点：求 Ramsey 数。 课程思政: (1) Ramsey 理论包含一个重要的哲学理念, 即: 完全的无序是不可能的. 鸽笼原理是这一
研究生课程教学大纲 哲学思想的一个简单体现， (2)R(3,3)的证明过程体现出了逻辑学，组合数学以及图论的完美结合. (3)Ramsey理论是是组合数学中历久弥新而又最有魅力的研究领域之一，原因之一不乏新 入门的研究者得到漂亮的研究成果.如2020年5月，MIT的本科生Ashwin Sah基于 2009年Conlon的论文对上界进行了改进，并给出了对角型Ramsey数的一个新上界. 第九章：有向图(4学时) 1本章教学内容： (1)有向图及其连通性(2学时)，(2)有向树、有向路与有向图、生成树的计数(2学时)。 2本章教学要求： 通过本章课程的学习，要求学生理解有向图的理论与实际意义，掌握有向图的基本结论和根 树的性质及其应用。 3本章教学重点：有向图的连通性，根树的性质及其应用。 4本章教学难点：有向图的连通性。 课程思政： (1)相对于无向图来看，有向图更加普遍，而且无向图可以理解为一条边同时有两个方向的 有向图.如城市的交通网络可以理解为一张有向图 (2)有向图的应用非常广泛，如解决流量问题的Ford-Fulkerson算法，有向图最短路问题的 Dijkstra算法，描述循环比赛中的竞赛图等. 三、教学方式 课程采取课堂讲授的教学方式。 四、考核方式与成绩评定 课程考核方式为考试，采取堂上闭卷笔试的方式。 成绩评定的考核比例为： (1)过程考核占20%，包括： 考勤：5%，课堂互动：5%，平时作业：10%。 (2)期末考核占80%。 五、教材及主要参考书目 教材： >
研究生课程教学大纲 7 哲学思想的一个简单体现. (2) R(3,3)的证明过程体现出了逻辑学, 组合数学以及图论的完美结合. (3) Ramsey 理论是是组合数学中历久弥新而又最有魅力的研究领域之一. 原因之一不乏新 入门的研究者得到漂亮的研究成果. 如 2020 年 5 月, MIT 的本科生 Ashwin Sah 基于 2009 年 Conlon 的论文对上界进行了改进, 并给出了对角型 Ramsey 数的一个新上界. 第九章：有向图(4 学时) 1 本章教学内容： (1) 有向图及其连通性（2 学时），(2) 有向树、有向路与有向图、生成树的计数（2 学时）。 2 本章教学要求： 通过本章课程的学习，要求学生理解有向图的理论与实际意义，掌握有向图的基本结论和根 树的性质及其应用。 3 本章教学重点：有向图的连通性，根树的性质及其应用。 4 本章教学难点：有向图的连通性。 课程思政: (1) 相对于无向图来看,有向图更加普遍,而且无向图可以理解为一条边同时有两个方向的 有向图.如城市的交通网络可以理解为一张有向图. (2) 有向图的应用非常广泛,如解决流量问题的 Ford-Fulkerson 算法,有向图最短路问题的 Dijkstra 算法,描述循环比赛中的竞赛图等. 三、教学方式 课程采取课堂讲授的教学方式。 四、考核方式与成绩评定 课程考核方式为考试，采取堂上闭卷笔试的方式。 成绩评定的考核比例为： （1）过程考核占 20%，包括： 考勤：5%，课堂互动：5%，平时作业：10%。 （2）期末考核占 80%。 五、教材及主要参考书目 教材：