《图论及应用》教学大纲

1、 图论及应用教学大纲前 言图论及其应用课程是数学学院应用数学专业和信息与计算科学专业的专业基础课程,也是应用性很强的一门数学课.图论是组合数学的一个分支，主要研究离散对象二元关系系统，与其他的数学分支，如群论，矩阵论，概率论，拓扑学，数值分析等有着密切的联系.设置本课程的目的是：使学习者在全面了解图论历史、现状与发展趋势的基础上，系统掌握图论及其应用中的基本概念，基本理论，和基本方法，了解一些基本的图论算法及其实现方式.学习本课程的要求是：掌握图的基本概念和图论的基本理论，图论中一些重要的结论以及一些基本的图论算法.要求学生能将图论理论应用于一些简单的离散数学问题.先修课程要求：高等代数本课程

2、计划72学时，3学分选用教材：范益政，汪毅等,图论导引，人民邮电出版社, 2007.教学手段：课堂讲授为主，习题课与讨论课为辅考核方法：考试教学进程安排表周次学时数教学主要内容教学环节备注12图论的发展进程,图的定义,图模型讲课12子图,图的运算,连通图的基本概念讲课22连通图的基本性质,图的直径,半径讲课22一些特殊的图,完全图,二部图,二部图的判定定理,多部图讲课与习题课相结合32多重图,有向图的基本概念,度的概念图论第一定理讲课32度的相关定理,连通图的度条件讲课42正则图,正则图的存在性讲课42度序列,可图的判定定理讲课与习题课相结合52图的矩阵表示,邻接矩阵,关联矩阵,Laplace

3、矩阵及其基本性质.讲课52不规则图讲课与讨论62图的同构,同构的判定讲课62割点,割边及其相关性质讲课72连通块及其性质讲课72边连通度,点连通度的引入及性质讲课82Whitney定理及其推论讲课82Menger定理及其推论讲课92可靠通讯网络的构造，Harary图讲课92最短路问题及其应用讲课102树的基本性质,树的五个等价定义讲课102森林的基本性质,生成树的概念与求法弦集和余树讲课112保距生成树,生成树个数的求法Cayley树公式,矩阵树定理讲课112最优生成树的定义Kruskal算法Prim算法,破圈法,树形图简介讲课与习题课相结合122Konigsberg七桥问题,Euler图概念

4、与性, Fleury算法讲课122Hamilton图, Hamilton图的充分条件Hamilton图的必要条件,讲课132Euler图的应用,中国邮路问题讲课132Hamilton图的应用,旅行售货问题讲课习题课相结合142匹配的基本概念,二部图的匹配讲课142Hall定理,最大匹配与完美匹配讲课152可扩路,二部图最大匹配的求法匈牙利算法讲课152点独立数,点覆盖,边独立数,边覆盖Galli恒等式讲课1621-因子分解,Tutte定理,讲课1622-因子分解,Petersen定理Remsey数简介讲课172图的染色,顶点染色,边染色的基本概念与性质讲课172平面图,平面图的基本性质与刻画讲

5、课182平面图的染色,四色定理,五色定理讲课182复习习题课第一章图的基本概念一、学习目的通过本章的学习，明确图论的研究对象，了解图论的产生与发展过程，熟练掌握图论的基本概念和基本运算，能够将实际问题转化为图论问题，能够利用图的度来研究和刻画图的性质，学会用图的矩阵来研究图.本章计划22学时.二、课程内容11图论发展史图论的发展史以及图论发展中的几个标志性问题，如七桥问题，Hamilton问题，四色问题等.12图的定义图的定义及表示，实际问题的图模型的建立方法，同构图的定义及其判别方法.13顶点的度顶点度的定义，图论第一定理的证明及其应用，关于顶点度的一些相关定理，利用度刻画图的性质的方式.有

6、向图与多重图的度.正则图以及其存在性的讨论.度序列以及可图的判定.利用顶点的度及其相关定理解决实际问题.不规则图.14子图与图的运算子图，诱导子图，生成子图的定义.图的一些运算，如补、并、和、积等15一些特殊的图完全图的定义及性质.二部图的定义及判定定理.多部图的定义及简单性质.利用特殊图类来解决实际问题.16图的矩阵表示图的邻接矩阵的定义及简单性质.图的关联矩阵的定义及简单性质.图的Laplace矩阵的简介.有向图关联矩阵与邻接矩阵的简介.三、教学基本要求了解：图论的发展现状.理解：图的概念，度的概念，图的邻接矩阵和关联矩阵.掌握：将实际问题转化为图论模型，度的有关定理，非负整数序列可图的判

7、定，利用图的矩阵表示研究图的性质.熟练掌握：图的基本运算.四、重点、难点提示和教学手段（一）本章重点对于简单的实际问题转化成图模型，利用相应理论解决问题.判断非负整数序列是否是某个图的度序列.建立图与矩阵之间的一一对应关系，利用矩阵解决图论问题.（二）本章难点序列可图的判定.（三）教学手段课堂讲授与习题课相结合五、思考与练习思考：图是否存在其他的矩阵表示，来反映图的性质？练习由授课老师自行确定第二章图的连通性一、学习目的通过本章的学习，理解点连通度和边连通度是如何刻画图的连通程度的.掌握图的割点，割边，点连通度，边连通度的定义，以及一些相关定理，会利用连通图及连通度的一些结果来解决实际问题.本

8、章计划14学时.二、课程内容21路和回路途径、迹、路、回路，距离，半径，直径的概念.回路和距离的相关定理.将上述概念和性质解决的一些实际问题.22连通图连通图和连通分支的概念和基本性质，连通图的刻画.有向图的连通与强连通.23连通度连通度引入的意义.割点，割边的定义及基本性质.块的定义及基本性质.顶点割、边割、连通度、边连通度的定义.k连通和k边连通图的刻画.点连通度和边连通度之间的关系，Whitney定理.Menger定理及应用.24可靠通讯网络的构造Harary图的构造过程， 联系可靠通讯网络的构造思想，解决可靠通讯网络的构造中的一类特殊问题.24最短路问题最短路问题的背景和引入.最短路问

9、题的一个有效算法Dijkatra算法.Dijkatra算法合理性分析.最短路问题的一些实际应用.三、教学基本要求了解：途径、迹、路、回路，距离，半径，直径的概念以及相关定理.三种Harary图的构造过程，最短路问题的背景.理解：连通图和连通分支的概念.连通度引入的必要性，点连通度和边连通度是如何刻画图的连通程度的.掌握：连通图和连通分支的基本性质.割点，割边之间的关系与基本性质.块的基本性质.利用Dijkatra算法求最短路，并由此解决实际问题.四、重点、难点提示和教学手段（一）本章重点割点，割边，割点数，割边数之间的关系.图的连通性的刻画方式，即连通度和边连通度的引入，实际问题转化为连通图和

10、连通度问题的方法和解决方案的设计.（二）本章难点Whitney定理，Menger定理的证明和Menger定理的一些有趣推论.k连通和k边连通图的刻画.（三）教学手段课堂讲授与习题课相结合五、思考与练习思考：1，能否定义极小顶点割和极小边割？2，除点连通度，边连通度外，能否定义一个新的参数来刻画图的连通程度？练习由授课老师自行确定第三章树一、学习目的通过本章的学习，掌握树的基本性质和五种等价定义，了解最优生成树提出的实际应用背景.能够熟练利用求最优生成树几种算法求解给定图的最优生成树，并解决实际问题.本章计划8学时.二、课程内容31树的基本性质树的基本性质，树的五种等价定义及其相互推导.32生成

11、树生成树的引入及相关概念.生成树，弦集，余树的相关性质.保距生成树的概念及求法.生成树个数的确定，Caylay树公式，矩阵树定理.33最优生成树引入最优生成树的实际应用背景.避圈法求最优生成树，Kruskal算法及其合理性分析.破圈法求最优生成树及其合理性分析.利用最优生成树求解实际问题.34树形图有向树和树形图的概念和基本性质,有序树与最优二元树.树形图在计算机编码中的应用.三、教学基本要求了解：引入最优生成树的实际应用背景.有向树和树形图的概念和基本性质. Caylay树公式，矩阵树定理.树形图在计算机编码中的应用.理解：树五种等价定义的内在联系,生成树，弦集，余树的概念及相关性质.保距生

12、成树的概念和求解方法.掌握：树五种等价定义的相互推导.图求解生成树个数的方法.熟练掌握：利用Kruskal算法和破圈法求解图的最优生成树.四、重点、难点提示和教学手段（一）本章重点树的五种等价定义及其相互推导.判断连通图的最小生成树个数.（二）本章难点Kruskal算法和破圈法的合理性分析.利用最小生成树求解实际问题.（三）教学手段课堂讲授与习题课相结合五、思考与练习思考：由树的等价定义能否得到单圈图，双圈图的一些等价定义？练习由授课老师自行确定第四章Euler环游和Hamilton回路一、学习目的通过本章的学习，了解Euler图和Hamilton图定义.掌握Euler图和Hamilton图的

13、充分、必要条件，学会判断给定的图是否是Euler图或Hamilton图，并可以利用Euler环游和Hamilton回路来解决一些实际问题.本章计划8学时.二、课程内容41Euler环游Euler回路和Euler图的引入背景和定义.Euler图的等价条件.利用Fleury算法求Euler回路. Euler迹和Euler回路的应用，一笔画问题.42中国邮递员问题中国邮递员问题的图论模型.最优环游的引入及概念.最优环游的求解算法与合理性分析.43Hamilton图Hamilton图的引入背景及定义.Hamilton图的充分条件.Hamilton图的必要条件.Hamilton图等价描述.Hamilto

14、n图的各种判断方法与优缺点分析.44旅行售货员问题旅行售货员问题的图论模型.最优Hamilton回路的近似求解算法，最邻近算法.旅行售货员问题的应用三、教学基本要求了解：Euler图和Hamilton图的引入背景.理解：Euler图和Hamilton图的概念，中国邮递员问题和旅行售货员问题的图论意义.Fleury算法和最邻近算法求解思想.最优环游的求解思想.掌握：Euler图的充要条件，Hamilton图的充分，必要条件和等价描述.判断Euler图和Hamilton图的方法.用Fleury算法求Euler回路.用最邻近算法求最优Hamilton回路四、重点、难点提示和教学手段（一）本章重点Eu

15、ler图的充要条件及其证明.Hamilton图的判断方法.利用Fleury求解欧拉回路，并可设计一些相关实际问题的解决方案.（二）本章难点将一些实际问题转化为中国邮递员问题和旅行售货员问题，并给出解决方案.（三）教学手段课堂讲授与习题课相结合五、思考与练习思考：1，对于Hamilton图能否给出其他的充分或必要条件？2，是否可以找到比最邻近算法更为优秀的算法求解最优Hamilton回路问题？练习由授课老师自行确定第五章图的匹配与独立集一、学习目的通过本章的学习，了解和掌握匹配（最大匹配、完美匹配）的定义及相关结论，能够求解二部图的最大匹配，具有解决一些相关的分配问题的能力.掌握点独立数、边独立

16、数、点覆盖数、边覆盖数的定义和相互关系.了解因子分解的想法和Ramsey数.本章计划12学时.二、课程内容51二部图二部图的引入及概念.二部图的等价条件.52对集匹配（最大匹配、完美匹配）的定义及相关概念.交错路与可扩路的概念.Tutte定理及其证明过程.53二部图对集二部图的最大匹配.Hall定理及其推论.二分图最大匹配的判别方法.54二部图最大对集算法匈牙利算法的引入与具体步骤.利用匈牙利算法求解一些实际问题，例如分配问题.最优分配问题简介，Kuhn-Munkres算法.55独立集和覆盖点独立数、边独立数、点覆盖数、边覆盖数的引入背景及定义. Galli恒等式.二部图中点覆盖数和边独立数之

17、间的关系.56Remsey数Remsey数的引入及定义.判断一些特殊情形的Remsey数.三、教学基本要求了解：因子分解的思想，Remsey数的引入及定义.理解：匹配（最大匹配、完美匹配）的定义及相关概念.交错路与可扩路的概念.点独立数、边独立数、点覆盖数、边覆盖数的概念和Galli恒等式的证明思想.掌握：Hall定理及其推论. Tutte定理.二部图求解最大匹配的方法.利用二部图求最大匹配求解实际问题.四、重点、难点提示和教学手段（一）本章重点二分图的等价条件.二分图最大匹配的判别与求法，匈牙利算法.讨论点独立数和点覆盖数之间的关系，边独立数和边覆盖数之间的关系是采用的证明思想.（二）本章难

18、点Tutte 1因子定理的证明.将一些实际问题转化为求Remsey数问题.（三）教学手段课堂讲授与习题课相结合五、思考与练习思考：能否将1因子分解和2因子分解进一步推广？练习由授课老师自行确定第六章图的染色一、学习目的通过本章的学习，了解平面图的概念，掌握平面图的基本性质.了解图的染色的想法与引入背景.了解平面图染色的四色定理和五色定理.本章计划6学时.二、课程内容61顶点染色顶点染色的基本概念，正常k染色，色数的概念以及相关基本定理.62平面图与五色定理平面的嵌入，关于平面图的刻画，Euler公式及其推论. Wagner定理.平面图染色的四色定理与五色定理.三、教学基本要求了解：平面图的基本概念，顶点染色的基本概念，想法和引入背景，四色定理和五色定理.掌握： 平面图的刻画，Euler公式.四、重点、难点提示和教学手段（一）