admin 管理员组

文章数量: 1086019


2024年3月10日发(作者：java虚拟机内存设置)

《图论》复习提纲

1、 图

（1） 图的概念：图的定义；空图；平凡图；简单图；完全图；二部图；完全二部图；

星；轮；补图；正则图（k--正则图）；同构；图的分类。

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

出子图。

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

（4） 道路与连通性：途径；链；道路；圈；圈的分类；连通图；非连通图；测地线；

u与v之间的距离；G的围长；G的周长；G的直径；G是二部图的充要条件。

（5） 图的运算： 图

G

2

的并；交；差；环和。

G

1

和

2、 树

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

（2） 割边与割点：割边；割点；圈和割边的关系；树和割边的关系；如何判断树中

的割点；不可分图；割点的三个等价命题；割边的三个等价命题。

（3） 生成树：生成树的定义；图有生成树的充要条件；判断一棵生成树的充要条件；

求生成树的两种方法。

3、 欧拉图和哈密顿图

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

是开链；多个环路的环和。

（2） 欧拉图：欧拉图和欧拉链；闭链、环路和欧拉图的关系；图G是连通欧拉图的充

要条件；两个欧拉图的环和。

（3） 哈密顿图：哈密顿圈和哈密顿图；哈密顿图的必要条件；哈密顿图的充分条件；

满足什么条件G是哈密顿图的充要条件是G+uv为哈密顿图；图G的闭包；简单图的闭包和

哈密顿图的关系。

4、 割集

（1）割集与断集：割集；断集；设T是连通图G的一棵生成树，并且e是任一树枝，则：

连枝集中是否包含G的割集，

Te

包含G的几个割集；割集和生成树之间的关系是什么？

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

的关系。

5、连通性

（1）连通度和边连通度：顶点割；点连通度；边连通度；点连通度、边连通度和最小度

之间有什么关系；点连通度和边连通度的范围是多少；在什么条件下，边连通度和最小度相

等；

（2）2-- 连通图：块；P和Q是内部不相交的；图G是2—连通的充要条件；图是不可

分的几个等价命题。

6、匹配

（1） 最大匹配：匹配；最大匹配；M-交错道路；M-增广道路；图G的一个匹配M是最

大匹配的充要条件；设

M

1

和

M

2

是简单图

G(V,E)

的两个匹配，记

G

(V

,E

)

是以

M

1

M

2

为边集的边导出子图，则

G

的每个分支分支具备什么情况。

（2） 二部图的匹配与覆盖：邻集；对于二部图G，有饱和

V

1

的每个顶点的匹配的充要

条件是什么？对于一个二部图，能否找到一个匹配

M

M

1

M

2

饱和

X

1

和

Y

2

；对于一个

二部图，是否存在一个匹配饱和G中所有最大度的顶点；具有最大度为

的二部图可分解多

少个匹配；覆盖；最小覆盖；最大匹配和最小覆盖的关系。

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

3-正则图是否有完美匹配。

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

7、色数

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

（2） 顶点着色：

n

-顶点着色；G的色数；二部图是几色的；图G的色数最大是多少？

图G是临界的和图G是

n

-临界的；图G是

n

-临界的其最小度满足什么条件？每个

n

-图至

少有多少个度不小于

n1

的顶点；设

u,v

是图G的两个不邻接的顶点，则色数是那两个图

的最小值。

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

8、平面图

（1） 平面图的概念：图G被嵌入曲面S上；G是可平面图；一个图是可平面的两个充

要条件；外部面和内部面；平面地图；最大可平面图；最大可平面图G的面是什

么形状；顶点数≥4的最大可平面图，其顶点的最小度满足什么条件；外可平面

图；最大外可平面图；设G（p≥3）是最大外可平面图，则G有多少个内部面。


本文标签： 顶点 匹配 割集 生成 关系

版权声明：本文标题：《图论》复习提纲 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1710075943a556573.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。