《图论》复习提纲

1、图

（1）图的概念：图的定义；空图；平凡图；简单图；完全图；二部图；完全二部图；星；轮；补图；正则图（k--正则图）；同构；图的分类。

（2）子图：子图的概念；真子图；G的生成子图；G的导出子图；主子图；G的边导出子图。

（3）顶点的度：顶点v的度；奇顶点；偶顶点；握手定理；握手定理的推论。

（4）道路与连通性：途径；链；道路；圈；圈的分类；连通图；非连通图；测地线；u与v之间的距离；G的围长；G的周长；G的直径；G是二部图的充要条件。

（5）图的运算： 图   和    的并；交；差；环和。 

2、树

（1）   树的特性：树的定义；树的六个等价命题。

（2）   割边与割点：割边；割点；圈和割边的关系；树和割边的关系；如何判断树中的割点；不可分图；割点的三个等价命题；割边的三个等价命题。

（3） 生成树：生成树的定义；图有生成树的充要条件；判断一棵生成树的充要条件；求生成树的两种方法。

3、欧拉图和哈密顿图

（1）环路：环路；环路中顶点的度满足什么条件；图G是连通环路的充要条件；什么是开链；多个环路的环和。

（2）  欧拉图：欧拉图和欧拉链；闭链、环路和欧拉图的关系；图G是连通欧拉图的充要条件；两个欧拉图的环和。

（3）  哈密顿图：哈密顿圈和哈密顿图；哈密顿图的必要条件；哈密顿图的充分条件；满足什么条件G是哈密顿图的充要条件是G+uv为哈密顿图；图G的闭包；简单图的闭包和哈密顿图的关系。

4、割集

（1）割集与断集：割集；断集；设T是连通图G的一棵生成树，并且e是任一树枝，则：连枝集中是否包含G的割集，包含G的几个割集；割集和生成树之间的关系是什么？

（2）关联集：关联集；任一断集和关联集的关系；任一顶点的关联集和其余顶点关联集的关系。

5、连通性

   （1）连通度和边连通度：顶点割；点连通度；边连通度；点连通度、边连通度和最小度之间有什么关系；点连通度和边连通度的范围是多少；在什么条件下，边连通度和最小度相等；

（2）2-- 连通图：块；P和Q是内部不相交的；图G是2—连通的充要条件；图是不可分的几个等价命题。

6、匹配

   （1） 最大匹配：匹配；最大匹配；M-交错道路；M-增广道路；图G的一个匹配M是最大匹配的充要条件；设和是简单图的两个匹配，记是以为边集的边导出子图，则的每个分支分支具备什么情况。

（2） 二部图的匹配与覆盖：邻集；对于二部图G，有饱和的每个顶点的匹配的充要条件是什么？对于一个二部图，能否找到一个匹配饱和和；对于一个二部图，是否存在一个匹配饱和G中所有最大度的顶点；具有最大度为的二部图可分解多少个匹配；覆盖；最小覆盖；最大匹配和最小覆盖的关系。

（3） 完美匹配：完美匹配；k-正则二部图是否有完美匹配；有完美匹配的充要条件；3-正则图是否有完美匹配。

（4） 完美匹配的算法：匈牙利算法的基本思想是什么？

7、色数

（1） 集：集；数；集和覆盖的关系；数和最小覆盖数的关系。

（2） 顶点着色： -顶点着色；G的色数；二部图是几色的；图G的色数最大是多少？图G是临界的和图G是-临界的；图G是-临界的其最小度满足什么条件？每个-图至少有多少个度不小于的顶点；设是图G的两个不邻接的顶点，则色数是那两个图的最小值。

（3） 边着色：图G的一个边着色；边色数；二部图的边色数，边色数的范围。

8、平面图

（1）平面图的概念：图G被嵌入曲面S上；G是可平面图；一个图是可平面的两个充要条件；外部面和内部面；平面地图；最大可平面图；最大可平面图G的面是什么形状；顶点数≥4的最大可平面图，其顶点的最小度满足什么条件；外可平面图；最大外可平面图；设G（p≥3）是最大外可平面图，则G有多少个内部面。