研究生课程教学大纲 《图论及应用》教学大纲 课程 课程中 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 从实际问题出发建立二部图模型首先研究, 并在刻画非平面 图方面有重要的应用