【数据结构】图 常见题型汇总

数据结构 图

定义

无向图的连通分量是指无向图中的极大连通子图。

图的遍历是指从图中顶点出发，每个顶点只能被访问一次，如果图不是连通则从某一顶点出发无法访问到其他全部结点。

无向连通图的所有顶点度之和为偶数

邻接矩阵行对应入度，列对应出度，顶点的度为对应入度+出度。

习题

题型1

1.一个有28条边的非连通无向图至少有（）个结点

假设一种情况 一个完全图+一个结点 设结点个数为n+1 有 n(n-1)/2=28 求出n为7所以至少有8个结点
1

2.对于一个有n个节点的图 连通无向图至少有n-1个边（至少构成一棵树） 强连通有向图至少n个边（至少构成一个环）

3.【2010】若无向图G =(V, E)中含7个顶点，则保证图G在任何连边方式下都是连通的，则需要的边数最少是（ ）

有6个顶点相互连接成环 另外一个顶点连接在其中一个顶点上
完全图边个数为 n(n-1)/2 加上单独的顶点那条边 代入为16条边

（个人理解的方法）
1
2
3
4

题型2

1.无向图G有23个边 度为4的顶点有5个 度为3的顶点有4个 其余都是度为2的顶点 则图G有（）个顶点

在n个顶点 e条边的无向图中 顶点x对应度数之和为2e 故4*5+3*4+2*x=2*23 x=7 故一共16个顶点
1

2.【2014】无向图G有16个边，其中度为4的顶点个数为3，度为3的顶点个数为4，其他顶点度均小于3，则G所含顶点个数至少是（18）

题型3.

1.n个结点的有向图中，每个顶点的度最大为（2n-2）

（n-1）*2 （即入度+出度）
1

2.n个定点的图是一个环，则有n棵生成树

——————写在后面————————

考研对应的书题还是很不错的，做的头秃，总结出来了一些知识点后就很容易理解了。令人感慨。