研究生课程教学大纲 无环路的逻辑拓扑结构.从而避免了广播风暴 (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 本章教学内容：