研究生课程教学大纲 《图论及应用》教学大纲 课程 课程中 1100016003 图论及应用 学时 60 编号 文名称 √学位课 课程 课程英 口非学位课 Graph Theory and its Application 3 性质 口其他 文名称 学分 开课 √春 适用学科 适用 √硕士 理工科 时间口秋 (类别) 学生 √博士 先修课程 线性代数 开课单位 数学科学学院 大纲撰写人 杨春 大纲审稿人 向昭银 制（修）定时间 2019.5 一、教学目标 图论是众多学科领域的重要的基础性前沿学科，其应用领域十分广泛，它已广泛应用到 物理学、化学、通讯科学、计算机科学、电气与土木工程、运筹学、生物遗传学、心理学、 社会学、经济学、人类学和语言学等领域，特别地，图论是学习研究计算机科学、通讯信息 科学、电子电路的必不可少的重要的数学工具。通过教学，使学生掌握图论的基本概念和基 本理论，了解图论理论的基本研究方法，能用图论知识处理各自专业中遇到的相关具体问题， 并为相关课程做好必要的知识准备。 二、教学内容与要求 第一章：图的基本概念(8学时) 1本章教学内容： (1)图和简单图(2学时)，(2)子图与图的运算、路与图的连通性(2学时)，(3)最短路及算 法、图的代数表示及特征(2学时)，（④）极图、交图与团图(2学时)。 2本章教学要求： 通过本章课程的学习，要求学生理解图论的一些基础性结论及其与实际问题的对应关系，掌 握图、多重图、简单图、子图等概念，顶点的度和有关定理，通路与图的连通性、图的代数 表示。 3本章教学重点：度序列、图序列、最短路及其算法。 4本章教学难点：图的同构与极图理论。 课程思政： (1)图的邻接矩阵和关联矩阵是计算机存储图的重要方式.从矩阵的视角研究图很自然地
研究生课程教学大纲 1 《图论及应用》教学大纲 课程 编号 1100016003 课程中 文名称 图论及应用 学时 60 课程 性质 √学位课 □非学位课 □其他 课程英 文名称 Graph Theory and its Application 学分 3 开课 时间 √春 □秋 适用学科 (类别) 理工科 适用 学生 √硕士 √博士 先修课程 线性代数 开课单位 数学科学学院 大纲撰写人 杨春 大纲审稿人 向昭银 制(修)定时间 2019.5 一、教学目标 图论是众多学科领域的重要的基础性前沿学科，其应用领域十分广泛，它已广泛应用到 物理学、化学、通讯科学、计算机科学、电气与土木工程、运筹学、生物遗传学、心理学、 社会学、经济学、人类学和语言学等领域，特别地，图论是学习研究计算机科学、通讯信息 科学、电子电路的必不可少的重要的数学工具。通过教学，使学生掌握图论的基本概念和基 本理论，了解图论理论的基本研究方法，能用图论知识处理各自专业中遇到的相关具体问题, 并为相关课程做好必要的知识准备。 二、教学内容与要求 第一章：图的基本概念(8 学时) 1 本章教学内容： (1) 图和简单图(2 学时)，(2)子图与图的运算、路与图的连通性(2 学时)，(3) 最短路及算 法、图的代数表示及特征(2 学时)，(4) 极图、交图与团图(2 学时)。 2 本章教学要求： 通过本章课程的学习，要求学生理解图论的一些基础性结论及其与实际问题的对应关系，掌 握图、多重图、简单图、子图等概念，顶点的度和有关定理，通路与图的连通性﹑图的代数 表示。 3 本章教学重点：度序列、图序列﹑最短路及其算法。 4 本章教学难点：图的同构与极图理论。 课程思政: (1) 图的邻接矩阵和关联矩阵是计算机存储图的重要方式. 从矩阵的视角研究图很自然地
研究生课程教学大纲 把线性代数和矩阵理论的知识与图论联系起来，这是代数图论的一个主要研究方向， 如应用关联矩阵证明握手定理就是一个很好的例子 (2)通过应用图同构方法识别NaNiO2晶体的不同构型的例子说明图同构方法在其它学科也 有重要应用. (3)许多化学物质的结晶体呈正多面体的形状，如食盐的结晶体是正六面体，明矾的结晶 体是正八面体.正多面体的研究可以追溯到柏拉图时代.柏拉图视“四古典元素”为元 素，其形状如正多面体中的其中四个.正多面体的研究还与著名的欧拉多面体公式有关 (正多面体只有5种). (4)超立方是一种重要的图类（可由三种等价的方式定义，即集合方法，序列方法， Cartesian乘积方法).由于对称性好，连通度高等特点得到了广泛研究，特别是，超立 方还是一种互连网络拓扑结构. 第二章：树(6学时) 1本章教学内容： (1)树的概念与性质(2学时)，(2)生成树(2学时)，(2)最小生成树(2学时)。 2本章教学要求： 通过本章课程的学习，要求学生理解树的理论与实际意义，掌握树的概念与性质，生成树， 最小生成树算法。 3本章教学重点：(1)树的概念与性质，(2)最小生成树算法及应用。 4本章教学难点：克鲁斯克尔算法证明。 课程思政： (1)树不仅是一种结构相对简单的图类（很多时候作为一些结论是试验田），而且在其它领 域有应用.英国数学家Arthur Cayley 1875年用树的模型研究了化学同分异构体的计数 问题：早在l9世纪，物理学家Kirchhoff就己经注意到电路中的独立回路与该电路中 所谓生成树的关系，进而发现了Kirchhoff电流定律；树还是一种特殊的网络拓扑模型 与数据存储模型（特别是二叉树） (2)Jordan定理事实上给出一个算法可以求树的半径和中心（只有一个中心点时是剪叶的次 数，两个中心点时是剪叶的次数+1)，该定理对应该布局在区域中心的资源配置有指导 作用，如确定社区医院的修建位置，就可以建模求图的中心. (3)Radia Joy Perlman于1981年设计了生成树协议.该协议是工作在OSI网络模型中的第 二层（数据链路层）的通信协议，防止交换机冗余链路产生的环路.用于确保以太网中 2
研究生课程教学大纲 2 把线性代数和矩阵理论的知识与图论联系起来, 这是代数图论的一个主要研究方向, 如应用关联矩阵证明握手定理就是一个很好的例子. (2) 通过应用图同构方法识别 NaNiO2晶体的不同构型的例子说明图同构方法在其它学科也 有重要应用. (3) 许多化学物质的结晶体呈正多面体的形状, 如食盐的结晶体是正六面体, 明矾的结晶 体是正八面体. 正多面体的研究可以追溯到柏拉图时代. 柏拉图视“四古典元素”为元 素，其形状如正多面体中的其中四个. 正多面体的研究还与著名的欧拉多面体公式有关 (正多面体只有 5 种). (4) 超立方是一种重要的图类(可由三种等价的方式定义, 即集合方法, 序列方法, Cartesian 乘积方法). 由于对称性好, 连通度高等特点得到了广泛研究, 特别是, 超立 方还是一种互连网络拓扑结构. 第二章：树(6 学时) 1 本章教学内容： (1)树的概念与性质（2 学时），(2) 生成树（2 学时），(2) 最小生成树（2 学时）。 2 本章教学要求： 通过本章课程的学习，要求学生理解树的理论与实际意义，掌握树的概念与性质，生成树， 最小生成树算法。 3 本章教学重点：（1）树的概念与性质，（2）最小生成树算法及应用。 4 本章教学难点：克鲁斯克尔算法证明。 课程思政: (1) 树不仅是一种结构相对简单的图类(很多时候作为一些结论是试验田), 而且在其它领 域有应用. 英国数学家 Arthur Cayley 1875 年用树的模型研究了化学同分异构体的计数 问题; 早在 19 世纪，物理学家 Kirchhoff 就已经注意到电路中的独立回路与该电路中 所谓生成树的关系, 进而发现了 Kirchhoff 电流定律; 树还是一种特殊的网络拓扑模型 与数据存储模型(特别是二叉树). (2) Jordan 定理事实上给出一个算法可以求树的半径和中心(只有一个中心点时是剪叶的次 数, 两个中心点时是剪叶的次数+1), 该定理对应该布局在区域中心的资源配置有指导 作用, 如确定社区医院的修建位置，就可以建模求图的中心. (3) Radia Joy Perlman 于 1981 年设计了生成树协议. 该协议是工作在 OSI 网络模型中的第 二层(数据链路层)的通信协议, 防止交换机冗余链路产生的环路. 用于确保以太网中
研究生课程教学大纲 无环路的逻辑拓扑结构.从而避免了广播风暴 (4)用凯莱递推法求图的生成树的棵数时产生的子图会指数级的上升（指数爆炸），是一种 指数次的计算方法.当图的阶数较高时，一般无法计数。 (⑤)用破圈法求图的最小生成树时，通过贪心的办法每一步删除一个圈中的最大权值边而 得到生成树，该树即为最小生存树.若将问题变换为每一步都删除圈中一个点，删除 至少多少个点使得图变成无圈图呢？此即反馈点集(Feedback Vertex Set)问题.破圈法 和反馈点集问题，从外表上看类似，一个删边，一个删点，都使得剩余图没有圈.但 问题的复杂度大相径庭（差之毫厘，谬以千里）.事实上，对最大度不超过4的图G,该 问题是NP-困难的.在图论中有许多这样的问题，条件差别微小，但结论差别很大， 这是离散数学的与连续数学味道不同的一个特点. 第三章：图的连通度(6学时) 1本章教学内容：(1)割边、割点和块(2学时)，(2)连通度及其应用(2学时)，(3)图 的宽距离与宽直径(2学时)。 2本章教学要求： 通过本章课程的学习，要求学生理解连通度的图论与实际意义，掌握图的连通度性质，敏格 尔定理。 3本章教学重点：(1)连通性相关概念，(2)连通度概念及其性质。 4本章教学难点：图的宽直径相关概念与结论及其应用。 课程思政： (1)图的连通程度的高低，对应于通信网络“可靠性程度”的高低.一般地，“好”的网络不 易使其中断通信， (2)求图的连通度和边连通度均有多项式时间算法. (3)用连通度和边连通度来描述大型网络的可靠性有一定的不足.为了更好地衡量网络的可 靠性，提出了一些其它参数，如坚韧度，条件连通度，限制连通度等. (4)Menger定理分别将图的k-连通，k-边连通和k条内部不交路，k条边不交的路建立了等价 的联系.这样k连通，k边连通不再单调地定义为是不超过连通度，边连通度的两个非 负整数值，而是赋予了这样明显的实际意义 第四章：欧拉图与哈密尔顿图(8学时) 1本章教学内容： 3
研究生课程教学大纲 3 无环路的逻辑拓扑结构. 从而避免了广播风暴. (4) 用凯莱递推法求图的生成树的棵数时产生的子图会指数级的上升(指数爆炸), 是一种 指数次的计算方法. 当图的阶数较高时, 一般无法计数. (5) 用破圈法求图的最小生成树时, 通过贪心的办法每一步删除一个圈中的最大权值边而 得到生成树, 该树即为最小生存树. 若将问题变换为每一步都删除圈中一个点, 删除 至少多少个点使得图变成无圈图呢? 此即反馈点集(Feedback Vertex Set)问题. 破圈法 和反馈点集问题, 从外表上看类似, 一个删边, 一个删点, 都使得剩余图没有圈. 但 问题的复杂度大相径庭(差之毫厘, 谬以千里). 事实上, 对最大度不超过 4 的图 G, 该 问题是 NP-困难的. 在图论中有许多这样的问题, 条件差别微小, 但结论差别很大, 这是离散数学的与连续数学味道不同的一个特点. 第三章：图的连通度(6 学时) 1 本章教学内容：(1) 割边、割点和块（2 学时），(2) 连通度及其应用（2 学时），(3) 图 的宽距离与宽直径（2 学时）。 2 本章教学要求： 通过本章课程的学习，要求学生理解连通度的图论与实际意义，掌握图的连通度性质，敏格 尔定理。 3 本章教学重点：（1）连通性相关概念，（2）连通度概念及其性质。 4 本章教学难点：图的宽直径相关概念与结论及其应用。 课程思政: (1) 图的连通程度的高低, 对应于通信网络“可靠性程度”的高低.一般地, “好”的网络不 易使其中断通信. (2) 求图的连通度和边连通度均有多项式时间算法. (3) 用连通度和边连通度来描述大型网络的可靠性有一定的不足.为了更好地衡量网络的可 靠性,提出了一些其它参数,如坚韧度,条件连通度,限制连通度等. (4) Menger 定理分别将图的 k-连通, k-边连通和 k 条内部不交路, k 条边不交的路建立了等价 的联系. 这样 k-连通, k-边连通不再单调地定义为是不超过连通度, 边连通度的两个非 负整数值, 而是赋予了这样明显的实际意义. 第四章：欧拉图与哈密尔顿图(8 学时) 1 本章教学内容：
研究生课程教学大纲 (1)欧拉图与中国邮路问题(2学时)，(2)哈密尔顿图(2学时)，(3)度极大非哈密尔顿 图与TSP问题(2学时)，(4)超哈密尔顿图问题(2学时)。 2本章教学要求： 通过本章课程的学习，要求学生理解欧拉图与哈密尔顿图的实际意义，掌握欧拉图与哈密尔 顿图的判定以及它们的应用。 3本章教学重点：欧拉图与哈密尔顿图的概念及其判定。 4本章教学难点：哈密尔顿图的判定。 课程思政： (1)哥尼斯堡(Konigsberg,Prussia)),是德国东普鲁士的一部分.哥尼斯堡在欧拉的生活与 图论历史中扮演着非常重要角色.图论和拓扑学都产生于欧拉解决哥尼斯堡七桥问题. 哥尼斯堡镇名人辈出，如数学家Goldbach(1690-1764),哲学家康德(1724-1804)，物理 学家Gustav Kirchhoff(1824-1887和数学家David Hilbert(1862-1943).好的人文和科学 环境使得人们的思想比较活跃，对人才的成长非常重要， (2)一笔画--中国古老的民间游戏。对于一个图形G是否可以一笔画成？要求笔不离纸， 也不能重复笔迹.该问题与欧拉图有着十分相似的地方， (3)1857年，哈密尔顿发明了一个游戏(1 cosian Game).它是由一个木制的正十二面体构 成，在它的每个棱角处标有当时很有名的城市.游戏目的是“环球旅行”.该游戏促使 人们思考点线连接的图的结构特征.这就是图论历史上著名的哈密尔顿问题.哈密尔 顿(1805-1865)，爱尔兰数学家，他的主要贡献是在代数领域，提出了哈密尔顿-凯莱定 理，并发现了四元数（第一个非交换代数）： 第五章：匹配与因子分解(6学时) 1本章教学内容： (1)匹配、偶图的匹配与覆盖(2学时)，(2)托特定理与完美匹配、因子分解(2学时)， (3)最优匹配与匈牙利算法、匹配在矩阵理论中的应用(2学时)。 2本章教学要求： 通过本章课程的学习，要求学生理解偶图匹配问题的实际意义，掌握偶图匹配存在性判定定 理和最优匹配算法。 3本章教学重点：偶图匹配存在性判定定理与最优匹配算法。 4本章教学难点：最优匹配算法。 课程思政： 4
研究生课程教学大纲 4 (1) 欧拉图与中国邮路问题（2 学时），(2) 哈密尔顿图（2 学时），(3) 度极大非哈密尔顿 图与 TSP 问题（2 学时），(4) 超哈密尔顿图问题（2 学时）。 2 本章教学要求： 通过本章课程的学习，要求学生理解欧拉图与哈密尔顿图的实际意义，掌握欧拉图与哈密尔 顿图的判定以及它们的应用。 3 本章教学重点：欧拉图与哈密尔顿图的概念及其判定。 4 本章教学难点：哈密尔顿图的判定。 课程思政: (1) 哥尼斯堡 (Königsberg, Prussia), 是德国东普鲁士的一部分. 哥尼斯堡在欧拉的生活与 图论历史中扮演着非常重要角色. 图论和拓扑学都产生于欧拉解决哥尼斯堡七桥问题. 哥尼斯堡镇名人辈出, 如数学家 Goldbach(1690-1764), 哲学家康德(1724-1804), 物理 学家Gustav Kirchhoff (1824-1887) 和数学家David Hilbert(1862-1943). 好的人文和科学 环境使得人们的思想比较活跃, 对人才的成长非常重要. (2) 一笔画----中国古老的民间游戏. 对于一个图形G是否可以一笔画成? 要求笔不离纸, 也不能重复笔迹. 该问题与欧拉图有着十分相似的地方. (3) 1857 年, 哈密尔顿发明了一个游戏(Icosian Game). 它是由一个木制的正十二面体构 成，在它的每个棱角处标有当时很有名的城市. 游戏目的是“环球旅行”. 该游戏促使 人们思考点线连接的图的结构特征. 这就是图论历史上著名的哈密尔顿问题. 哈密尔 顿(1805-1865), 爱尔兰数学家, 他的主要贡献是在代数领域，提出了哈密尔顿-凯莱定 理, 并发现了四元数(第一个非交换代数). 第五章：匹配与因子分解(6 学时) 1 本章教学内容： (1) 匹配、偶图的匹配与覆盖（2 学时），(2) 托特定理与完美匹配、因子分解（2 学时）， (3) 最优匹配与匈牙利算法、匹配在矩阵理论中的应用（2 学时）。 2 本章教学要求： 通过本章课程的学习，要求学生理解偶图匹配问题的实际意义，掌握偶图匹配存在性判定定 理和最优匹配算法。 3 本章教学重点：偶图匹配存在性判定定理与最优匹配算法。 4 本章教学难点：最优匹配算法。 课程思政:
研究生课程教学大纲 (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 从实际问题出发建立二部图模型首先研究, 并在刻画非平面 图方面有重要的应用
研究生课程教学大纲 第七章：图的着色(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%。 五、教材及主要参考书目 教材：
研究生课程教学大纲 张先迪，李正良等，《图论及其应用》，高等教育出版社，2005年 参考书： [1]J.A.Bondy,U.S.R Murty,吴望名等译，图论及其应用，科学出版社，1984 [2]王树禾，图论（第二版），高等教育出版社，2009 [3]R.J.Wilson,Introduction to Graph Theory,4th Ed.Prentice Hall,1996. [4]D.B.West,Introduction to Graph Theory,Prentice Hall,2001 [5J.A.Bondy,U.S.R Murty,Graph Theory,Springer,2008
研究生课程教学大纲 8 张先迪，李正良等，《图论及其应用》，高等教育出版社，2005 年. 参考书： [1] J.A. Bondy, U.S.R Murty, 吴望名等译, 图论及其应用, 科学出版社,1984. [2]王树禾,图论(第二版), 高等教育出版社, 2009 [3]R.J. Wilson, Introduction to Graph Theory, 4th Ed. Prentice Hall, 1996. [4]D.B. West, Introduction to Graph Theory, Prentice Hall, 2001. [5J.A. Bondy, U.S.R Murty,Graph Theory, Springer, 2008
研究生课程教学大纲 课程代码Syllabus of课程名称 Course Class 1100016003 60 Code Hours Course ☑Degree Name Graph Theory and its Application Course ☐Non-Degree Credit 3 Nature ☐Others Semester )Fall/(√)Spring Students (√)Master/(√)Ph.D Discipline Linear Algebra Prerequisites School School of Mathematical Sciences Written by Chun Yang Reviewed by Zhaoyin Xiang Date 2019.5 1.Course Objectives Graph theory is an important and frontier discipline of numerous areas,and it has wide applications.It has been extensively used in physics,chemistry,telecommunication,computer science,electronics and civil engineering,operational research,biogenetics,psychology,sociology, economics,anthropology and etc.Especially,graph theory is a necessary mathematical tool of studying computer science,telecommunication,electronic circuit.By learning this course,one can grasp fundamental concepts and theories of graph theory,understand basic research methods of graph theory and use graph theory to cope with related problems in his/her own major,as well as do adequate preparation for related curriculum. 2.Course Content and Requirements Chapter 1.Basic concepts of graph(8 hr) (1).Teaching contents: a.Graph and simple graph(2 hr); b.Subgraph and operations of graphs,path and connectedness(2 hr); c.Shortest path algorithm,algebraic representation of graph and its characteristic(2 hr); d.Extremal graph,intersection graph and clique graph(2 hr). (2).Teaching requirements: By learning this chapter,students will understand some fundamental results and its relationship between practical problems,grasp the concepts of graph,multigraph,simple graph and subgraphs,as well as degree and its related theories,path and connectedness of graph, algebraic representation of graph. (3).Key points of teaching:Degree sequence of graph,graphic sequence,shortest path and its algorithm (4).Teaching difficulties:Isomorphism of graphs and extremal graph theory
研究生课程教学大纲 9 课程代码 Syllabus of 课程名称 Course Code 1100016003 Course Name Graph Theory and its Application Class Hours 60 Course Nature □√ Degree □Non-Degree □Others Credit 3 Semester ( )Fall/( √ )Spring Students (√) Master/(√) Ph.D Discipline Prerequisites Linear Algebra School School of Mathematical Sciences Written by Chun Yang Reviewed by Zhaoyin Xiang Date 2019. 5 1. Course Objectives Graph theory is an important and frontier discipline of numerous areas, and it has wide applications. It has been extensively used in physics, chemistry, telecommunication, computer science, electronics and civil engineering, operational research, biogenetics, psychology, sociology, economics, anthropology and etc. Especially, graph theory is a necessary mathematical tool of studying computer science, telecommunication, electronic circuit. By learning this course, one can grasp fundamental concepts and theories of graph theory, understand basic research methods of graph theory and use graph theory to cope with related problems in his/her own major, as well as do adequate preparation for related curriculum. 2. Course Content and Requirements Chapter 1. Basic concepts of graph (8 hr) (1). Teaching contents: a. Graph and simple graph (2 hr); b. Subgraph and operations of graphs, path and connectedness (2 hr); c. Shortest path algorithm, algebraic representation of graph and its characteristic (2 hr); d. Extremal graph, intersection graph and clique graph (2 hr). (2). Teaching requirements: By learning this chapter, students will understand some fundamental results and its relationship between practical problems, grasp the concepts of graph, multigraph, simple graph and subgraphs, as well as degree and its related theories, path and connectedness of graph, algebraic representation of graph. (3). Key points of teaching: Degree sequence of graph, graphic sequence, shortest path and its algorithm. (4). Teaching difficulties: Isomorphism of graphs and extremal graph theory
研究生课程教学大纲 Curriculum ideology: (1)The adjacency matrix and the incidence matrix of graphs are important ways for computers to store graphs.Studying graphs from the perspective of matrices naturally links the knowledge of linear algebra and matrix theory with graph theory,which is a major research direction of algebraic graph theory,such as the application of the incidence matrix to prove the handshake theorem is a good example. (2)The example of identifying different configurations of NaNiOz crystals by applying the graph isomorphism method illustrates that the graph isomorphism method also has important applications in other disciplines. (3)The crystals of many chemical substances are in the shape of a regular polyhedron.For example,the crystal of table salt is a regular hexahedron,and the crystal of alum is a regular octahedron.The study of regular polyhedrons can be traced back to the Plato era.Plato regards the "four classical elements"as elements,and its shape is like four regular polyhedrons.The study of regular polyhedrons is also related to the famous Euler polyhedron formula(there are only 5 types of regular polyhedrons). (4)Hypercube is an important graph class (it can be defined in three equivalent ways, namely set method,sequence method,Cartesian product method).Due to its good symmetry and high connectivity,it has been widely studied,especially,it is also an interconnection network topology. Chapter 2.Tree(6 hr) (1).Teaching contents: a.Definition and properties of tree(2 hr); b.Spanning tree(2 hr); c.Minimum spanning tree (2 hr); (2).Teaching requirements: By learning this chapter,students will understand practical significance and theories of tree, grasp the concepts of tree,spanning tree and algorithms of minimum spanning tree. (3).Key points of teaching: a.Definition and properties of tree; b.Algorithms of minimum spanning tree and their applications. (4).Teaching difficulties:Proof of Kruskal's algorithm. Curriculum ideology: (1)Trees are not only a relatively simple structure of graphs(in many cases as a test field for some conclusions),but also have applications in other fields.British mathematician Arthur Cayley used the tree model to study the counting of chemical isomers in 1875;As early as the 19th century,the physicist Kirchhoff had noticed the relationship between the independent circuits and 10
研究生课程教学大纲 10 Curriculum ideology: (1) The adjacency matrix and the incidence matrix of graphs are important ways for computers to store graphs. Studying graphs from the perspective of matrices naturally links the knowledge of linear algebra and matrix theory with graph theory, which is a major research direction of algebraic graph theory, such as the application of the incidence matrix to prove the handshake theorem is a good example. (2) The example of identifying different configurations of NaNiO2 crystals by applying the graph isomorphism method illustrates that the graph isomorphism method also has important applications in other disciplines. (3) The crystals of many chemical substances are in the shape of a regular polyhedron. For example, the crystal of table salt is a regular hexahedron, and the crystal of alum is a regular octahedron. The study of regular polyhedrons can be traced back to the Plato era. Plato regards the "four classical elements" as elements, and its shape is like four regular polyhedrons. The study of regular polyhedrons is also related to the famous Euler polyhedron formula (there are only 5 types of regular polyhedrons). (4) Hypercube is an important graph class (it can be defined in three equivalent ways, namely set method, sequence method, Cartesian product method). Due to its good symmetry and high connectivity, it has been widely studied, especially, it is also an interconnection network topology. Chapter 2. Tree (6 hr) (1). Teaching contents: a. Definition and properties of tree (2 hr); b. Spanning tree (2 hr); c. Minimum spanning tree (2 hr); (2). Teaching requirements: By learning this chapter, students will understand practical significance and theories of tree, grasp the concepts of tree, spanning tree and algorithms of minimum spanning tree. (3). Key points of teaching: a. Definition and properties of tree; b. Algorithms of minimum spanning tree and their applications. (4). Teaching difficulties: Proof of Kruskal’s algorithm. Curriculum ideology: (1) Trees are not only a relatively simple structure of graphs (in many cases as a test field for some conclusions), but also have applications in other fields. British mathematician Arthur Cayley used the tree model to study the counting of chemical isomers in 1875; As early as the 19th century, the physicist Kirchhoff had noticed the relationship between the independent circuits and
