《图论及应用》教学大纲.docx
《《图论及应用》教学大纲.docx》由会员分享，可在线阅读，更多相关《《图论及应用》教学大纲.docx（16页珍藏版）》请在冰点文库上搜索。
《图论及应用》教学大纲
《图论及应用》教学大纲
前言
《图论及其应用》课程是数学学院应用数学专业和信息与计算科学专业的专业基础课程, 也是应用性很强的一门数学课.图论是组合数学的一个分支，主要研究离散对象二元关系系统，与其他的数学分支，如群论，矩阵论，概率论，拓扑学，数值分析等有着密切的联系.
设置本课程的目的是：
使学习者在全面了解图论历史、现状与发展趋势的基础上，系统掌握图论及其应用中的基本概念，基本理论，和基本方法，了解一些基本的图论算法及其实现方式.
学习本课程的要求是：
掌握图的基本概念和图论的基本理论，图论中一些重要的结论以及一些基本的图论算法. 要求学生能将图论理论应用于一些简单的离散数学问题.
先修课程要求：
高等代数
本课程计划72学时，3学分
选用教材：
范益政，汪毅等,《图论导引》，人民邮电出版社,2007.
教学手段：
课堂讲授为主，习题课与讨论课为辅
考核方法：
考试
教学进程安排表
周次
学时数
教 学 主 要 内 容
教学环节
备注
1
2
图论的发展进程, 图的定义, 图模型
讲课
1
2
子图, 图的运算, 连通图的基本概念
讲课
2
2
连通图的基本性质, 图的直径, 半径
讲课
2
2
一些特殊的图, 完全图, 二部图, 二部图的判定定理, 多部图
讲课与习题课相结合
3
2
多重图, 有向图的基本概念, 度的概念
图论第一定理
讲课
3
2
度的相关定理, 连通图的度条件
讲课
4
2
正则图, 正则图的存在性
讲课
4
2
度序列, 可图的判定定理
讲课与习题课相结合
5
2
图的矩阵表示, 邻接矩阵, 关联矩阵,
Laplace矩阵及其基本性质.
讲课
5
2
不规则图
讲课与讨论
6
2
图的同构, 同构的判定
讲课
6
2
割点, 割边及其相关性质
讲课
7
2
连通块及其性质
讲课
7
2
边连通度, 点连通度的引入及性质
讲课
8
2
Whitney定理及其推论
讲课
8
2
Menger 定理及其推论
讲课
9
2
可靠通讯网络的构造，Harary图
讲课
9
2
最短路问题及其应用
讲课
10
2
树的基本性质, 树的五个等价定义
讲课
10
2
森林的基本性质, 生成树的概念与求法
弦集和余树
讲课
11
2
保距生成树, 生成树个数的求法
Cayley树公式, 矩阵树定理
讲课
11
2
最优生成树的定义Kruskal算法
Prim算法, 破圈法, 树形图简介
讲课与习题课相结合
12
2
Konigsberg七桥问题, Euler图概念与性,Fleury算法
讲课
12
2
Hamilton图,Hamilton图的充分条件
Hamilton图的必要条件,
讲课
13
2
Euler图的应用, 中国邮路问题
讲课
13
2
Hamilton图的应用, 旅行售货问题
讲课习题课相结合
14
2
匹配的基本概念, 二部图的匹配
讲课
14
2
Hall定理, 最大匹配与完美匹配
讲课
15
2
可扩路, 二部图最大匹配的求法
匈牙利算法
讲课
15
2
点独立数, 点覆盖, 边独立数, 边覆盖
Galli恒等式
讲课
16
2
1-因子分解, Tutte定理,
讲课
16
2
2-因子分解, Petersen定理
Remsey数简介
讲课
17
2
图的染色, 顶点染色, 边染色的基本概念与性质
讲课
17
2
平面图, 平面图的基本性质与刻画
讲课
18
2
平面图的染色, 四色定理, 五色定理
讲课
18
2
复习
习题课
第一章 图的基本概念
一、学习目的
通过本章的学习，明确图论的研究对象，了解图论的产生与发展过程，熟练掌握图论的基本概念和基本运算，能够将实际问题转化为图论问题，能够利用图的度来研究和刻画图的性质，学会用图的矩阵来研究图.本章计划22学时.
二、课程内容
§1．1 图论发展史
图论的发展史以及图论发展中的几个标志性问题，如七桥问题，Hamilton问题， 四色问题等.
§1．2 图的定义
图的定义及表示，实际问题的图模型的建立方法，同构图的定义及其判别方法.
§1．3 顶点的度
顶点度的定义， 图论第一定理的证明及其应用，关于顶点度的一些相关定理， 利用度刻画图的性质的方式.有向图与多重图的度. 正则图以及其存在性的讨论. 度序列以及可图的判定.利用顶点的度及其相关定理解决实际问题.不规则图.
§1．4 子图与图的运算
子图， 诱导子图， 生成子图的定义. 图的一些运算， 如补、并、和、积等
§1．5 一些特殊的图
完全图的定义及性质. 二部图的定义及判定定理.多部图的定义及简单性质.利用特殊图类来解决实际问题.
§1．6 图的矩阵表示
图的邻接矩阵的定义及简单性质.图的关联矩阵的定义及简单性质.图的Laplace矩阵的简介.有向图关联矩阵与邻接矩阵的简介.
三、教学基本要求
了解：
图论的发展现状.
理解：
图的概念，度的概念， 图的邻接矩阵和关联矩阵.
掌握：
将实际问题转化为图论模型，度的有关定理， 非负整数序列可图的判定，利用图的矩阵表示研究图的性质.
熟练掌握：
图的基本运算.
四、重点、难点提示和教学手段
（一）本章重点
对于简单的实际问题转化成图模型，利用相应理论解决问题.判断非负整数序列是否是某个图的度序列. 建立图与矩阵之间的一一对应关系，利用矩阵解决图论问题.
（二）本章难点
序列可图的判定.
（三）教学手段
课堂讲授与习题课相结合
五、思考与练习
思考：
图是否存在其他的矩阵表示， 来反映图的性质？
练习由授课老师自行确定
第二章 图的连通性
一、学习目的
通过本章的学习，理解点连通度和边连通度是如何刻画图的连通程度的. 掌握图的割点，割边，点连通度，边连通度的定义，以及一些相关定理，会利用连通图及连通度的一些结果来解决实际问题.本章计划14学时.
二、课程内容
§2．1 路和回路
途径、迹、路、回路，距离，半径，直径的概念.回路和距离的相关定理.将上述概念和性质解决的一些实际问题.
§2．2 连通图
连通图和连通分支的概念和基本性质，连通图的刻画.有向图的连通与强连通.
§2．3 连通度
连通度引入的意义. 割点，割边的定义及基本性质.块的定义及基本性质.顶点割、边割、连通度、边连通度的定义. k连通和k边连通图的刻画.点连通度和边连通度之间的关系，Whitney定理.Menger定理及应用.
§2．4 可靠通讯网络的构造
Harary图的构造过程，联系可靠通讯网络的构造思想，解决可靠通讯网络的构造中的一类特殊问题.
§2．4 最短路问题
最短路问题的背景和引入.最短路问题的一个有效算法Dijkatra算法.Dijkatra算法合理性分析.最短路问题的一些实际应用.
三、教学基本要求
了解：
途径、迹、路、回路，距离，半径，直径的概念以及相关定理. 三种Harary图的构造过程，最短路问题的背景.
理解：
连通图和连通分支的概念. 连通度引入的必要性，点连通度和边连通度是如何刻画图的连通程度的.
掌握：
连通图和连通分支的基本性质.割点，割边之间的关系与基本性质. 块的基本性质.利用Dijkatra算法求最短路，并由此解决实际问题.
四、重点、难点提示和教学手段
（一）本章重点
割点，割边， 割点数，割边数之间的关系.图的连通性的刻画方式，即连通度和边连通度的引入，实际问题转化为连通图和连通度问题的方法和解决方案的设计.
（二）本章难点
Whitney定理，Menger定理的证明和Menger定理的一些有趣推论. k连通和k边连通图的刻画.
（三）教学手段
课堂讲授与习题课相结合
五、思考与练习
思考：
1，能否定义极小顶点割和极小边割？
2， 除点连通度，边连通度外，能否定义一个新的参数来刻画图的连通程度？
练习由授课老师自行确定
第三章 树
一、学习目的
通过本章的学习，掌握树的基本性质和五种等价定义，了解最优生成树提出的实际应用背景. 能够熟练利用求最优生成树几种算法求解给定图的最优生成树，并解决实际问题.本章计划8学时.
二、课程内容
§3．1 树的基本性质
树的基本性质，树的五种等价定义及其相互推导.
§3．2 生成树
生成树的引入及相关概念.生成树，弦集，余树的相关性质.保距生成树的概念及求法. 生成树个数的确定，Caylay树公式，矩阵树定理.
§3．3 最优生成树
引入最优生成树的实际应用背景. 避圈法求最优生成树， Kruskal算法及其合理性分析.破圈法求最优生成树及其合理性分析.利用最优生成树求解实际问题.
§3．4 树形图
有向树和树形图的概念和基本性质, 有序树与最优二元树.树形图在计算机编码中的应用.
三、教学基本要求
了解：
引入最优生成树的实际应用背景.有向树和树形图的概念和基本性质.Caylay树公式，矩阵树定理.树形图在计算机编码中的应用.
理解：
树五种等价定义的内在联系, 生成树，弦集，余树的概念及相关性质.保距生成树的概念和求解方法.
掌握：
树五种等价定义的相互推导.图求解生成树个数的方法.
熟练掌握：
利用Kruskal算法和破圈法求解图的最优生成树.
四、重点、难点提示和教学手段
（一）本章重点
树的五种等价定义及其相互推导.判断连通图的最小生成树个数.
（二）本章难点
Kruskal算法和破圈法的合理性分析.利用最小生成树求解实际问题.
（三）教学手段
课堂讲授与习题课相结合
五、思考与练习
思考：
由树的等价定义能否得到单圈图，双圈图的一些等价定义？
练习由授课老师自行确定
第四章 Euler环游和Hamilton回路
一、学习目的
通过本章的学习，了解Euler图和Hamilton图定义.掌握Euler图和Hamilton图的充分、必要条件，学会判断给定的图是否是Euler图或Hamilton图，并可以利用Euler环游和Hamilton回路来解决一些实际问题.本章计划8学时.
二、课程内容
§4．1 Euler环游
Euler回路和Euler图的引入背景和定义.Euler图的等价条件.利用Fleury算法求 Euler回路.Euler迹和Euler回路的应用，一笔画问题.
§4．2 中国邮递员问题
中国邮递员问题的图论模型. 最优环游的引入及概念.最优环游的求解算法与合理性分析.
§4．3 Hamilton 图
Hamilton图的引入背景及定义.Hamilton图的充分条件.Hamilton图的必要条件.Hamilton图等价描述.Hamilton图的各种判断方法与优缺点分析.
§4．4 旅行售货员问题
旅行售货员问题的图论模型.最优Hamilton回路的近似求解算法，最邻近算法.旅行售货员问题的应用
三、教学基本要求
了解：
Euler图和Hamilton图的引入背景.
理解：
Euler图和Hamilton图的概念，中国邮递员问题和旅行售货员问题的图论意义.Fleury算法和最邻近算法求解思想.最优环游的求解思想.
掌握：
Euler图的充要条件，Hamilton图的充分，必要条件和等价描述.判断Euler图和Hamilton图的方法.用Fleury算法求Euler回路.用最邻近算法求最优Hamilton回路
四、重点、难点提示和教学手段
（一）本章重点
Euler图的充要条件及其证明.Hamilton图的判断方法. 利用Fleury求解欧拉回路，并可设计一些相关实际问题的解决方案.
（二）本章难点
将一些实际问题转化为中国邮递员问题和旅行售货员问题，并给出解决方案.
（三）教学手段
课堂讲授与习题课相结合
五、思考与练习
思考：
1，对于Hamilton图能否给出其他的充分或必要条件？
2，是否可以找到比最邻近算法更为优秀的算法求解最优Hamilton回路问题？
练习由授课老师自行确定
第五章 图的匹配与独立集
一、学习目的
通过本章的学习，了解和掌握匹配（最大匹配、完美匹配）的定义及相关结论，能够求解二部图的最大匹配，具有解决一些相关的分配问题的能力.掌握点独立数、边独立数、点覆盖数、边覆盖数的定义和相互关系.了解因子分解的想法和Ramsey数.本章计划12学时.
二、课程内容
§5．1 二部图
二部图的引入及概念.二部图的等价条件.
§5．2 对集
匹配（最大匹配、完美匹配）的定义及相关概念.交错路与可扩路的概念.Tutte 定理及其证明过程.
§5．3 二部图对集
二部图的最大匹配.Hall定理及其推论.二分图最大匹配的判别方法.
§5．4 二部图最大对集算法
匈牙利算法的引入与具体步骤.利用匈牙利算法求解一些实际问题，例如分配问题.最优分配问题简介， Kuhn-Munkres算法.
§5．5 独立集和覆盖
点独立数、边独立数、点覆盖数、边覆盖数的引入背景及定义.Galli恒等式.二部图中点覆盖数和边独立数之间的关系.
§5．6 Remsey数
Remsey数的引入及定义. 判断一些特殊情形的Remsey数.
三、教学基本要求
了解：
因子分解的思想， Remsey数的引入及定义.
理解：
匹配（最大匹配、完美匹配）的定义及相关概念.交错路与可扩路的概念.点独立数、边独立数、点覆盖数、边覆盖数的概念和Galli恒等式的证明思想.
掌握：
Hall定理及其推论.Tutte 定理. 二部图求解最大匹配的方法. 利用二部图求最大匹配求解实际问题.
四、重点、难点提示和教学手段
（一）本章重点
二分图的等价条件.二分图最大匹配的判别与求法， 匈牙利算法.讨论点独立数和点覆盖数之间的关系，边独立数和边覆盖数之间的关系是采用的证明思想.
（二）本章难点
Tutte1－因子定理的证明.将一些实际问题转化为求Remsey数问题.
（三）教学手段
课堂讲授与习题课相结合
五、思考与练习
思考：
能否将1－因子分解和2－因子分解进一步推广？
练习由授课老师自行确定
第六章 图的染色
一、学习目的
通过本章的学习，了解平面图的概念，掌握平面图的基本性质.了解图的染色的想法与引入背景.了解平面图染色的四色定理和五色定理.本章计划6学时.
二、课程内容
§6．1 顶点染色
顶点染色的基本概念，正常k染色，色数的概念以及相关基本定理.
§6．2 平面图与五色定理
平面的嵌入，关于平面图的刻画， Euler公式及其推论.Wagner定理.平面图染色的四色定理与五色定理.
三、教学基本要求
了解：
平面图的基本概念，顶点染色的基本概念，想法和引入背景，四色定理和五色定理.
掌握：
平面图的刻画， Euler公式.
四、重点、难点提示和教学手段
（一）本章重点
Euler公式.平面图的刻画.
（二）本章难点
Wagner定理的证明.四色定理与五色定理的证明.
（三）教学手段
课堂讲授与习题课相结合
五、思考与练习
练习由授课老师自行确定
阅读书目
（一）J．A.Bondy，U.S.R.Murty著, 吴望祖译, 图论及其应用，北京：
科学出版社，1984.
（二）卢开澄，卢华明，图论及其应用（第二版），北京：
清华大学出版社，1995.
（三）徐俊明，图论及其应用（第二版），合肥：
中国科技大学出版社，2004.
（四）D.Reinhard,GraphTheory（SecondEdition）,Springer-verlag,2000.
升级会员 