图的基本概念

2022.09.14

概念

有向图、无向图

简单图(无重复边，无自己到自己的边)、多重图

完全图(任意两结点中间都有边(单向两条，无向一条))

子图

连通、连通图、连通分量=极大连通子图（对于无向图）

强连通图、强连通分量（对于有向图，所有ij均双向连通）

生成树，生成森林

顶点的度、入度、出度

边的权和网（网：带权图）

稠密图、稀疏图

路径、路径长度、回路

简单路径、简单回路（无重复结点）

距离：不存在是无穷

有向树：顶点入度为0，其余结点均为1的有向图

例题

1. 图中有关路径的定义是（）. A.由顶点和相邻顶点序偶构成的边所形成的序列 B. 由不同顶点所形成的序列 C.由不同边所形成的序列 D.上述定义都不是

【答案】：A

2. 一个有n个结点和n条边的无向图一定是（） A. 连通的 B.不连通的 C.无环的 D.有环的

   【答案】：D

3. 若从无向图的任意顶,点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。

   A.强连通图 B.连通图 C.有回路 D.一棵树

   【答案】：B

4. 以下关于图的叙述中，正确的是（ ） A. 图与树的区别在于图的边数大于等于顶点数 B. 假设有图G={V，{E}}，顶点集V'$\subseteq$$\subseteq$V，E'$\subseteq$$\subseteq$E，则V'和{E'}构成G的子图 C. 无向图的连通分量是指无向图中的极大连通子图 D. 图的遍历就是从图中某一顶点出发访遍图中其余顶点

   【答案】：D(图可能非肥连通结点) -> C

5. 以下关于图的叙述中，正确的是（ ） A. 强连通有向图的任何顶点到其他所有顶点都有弧 B. 困的任意顶点的入度等于出度 C.有向完全图一定是强连通有向图 D. 有向图的边集的子集和顶点集的子集可构成原有向图的子图

   【答案】：C

6. 一个有28条边的非连通无向图至少有（ ）个顶点。 A. 7 B. 8 C. 9 D. 10

   【答案】：1+2+3+4+5+6+7=28, 8，C

7. 对于一个有n个顶点的图：若是连通无向图，其边的个数至少为（ ）；若是强连通有向图，其边的个数至少为（ ）。 A. n-1,n B. n-1,n(n-1) C. n,n D. n .nin-1

   【答案】：A

8. 无向图G有23条边，度为4的顶点有5个，度为3的顶点有4个，其余都是度为2的顶点，则图G有（）个顶点。 A. 11 B. 12 C. 15 D. 16

   【答案】：n。20+12+(n-9)2 = 46 -> n-9 = 46-32=14/2 = 7 -> n=16，D

9. 在有n个顶点的有向图中，每个顶点的度最大可达（）。 A. n B. n-1 C. 2n D. 2n-2

   【答案】：D

10. 具有6个顶点的无向图，当有（ ）条边时能确保是一个连通图。 A. 8 B. 9 C. 10 D. 11

    【答案】：1+2+3+4+1 = 11, D

11. 设有无向图 G=(V,E) , G'=(V',E')，若G'是G的生成树，则下列不正确的是（ ）。 I. G'为G的连通分量 II. G'为G的无环子图 III. G'为G的极小连通子图且 V'=V A. I、II B. 只有III C. II、III D. 只有I

    【答案】：B -> D，注意连通分量是极大连通子图

12. 若具有n个顶点的图是一个环，則它有（）棵生成树. A. n^2 B. n C. n-1 D. 1

    【答案】：B

13. 若一个具有n个顶点、e条边的无向图是一个森林，则该森林中必有（）棵树。 A. n B. e C. n-e D. 1

    【答案】：C

14. 【2009 统考真题】下列关于无向连通图特性的叙述中，正确的是 I. 所有顶点的度之和为偶数 II.边数大于顶点个数减 1 III. 至少有一个顶点的度为1 A. I B. II C. I、II D. I、III

    【答案】：A

15. 【2010統考真题】若无向图 G =(V,E)，中含有7个顶点，要保证写在任何情况下都是连通的，則需要的边数最少是（）。 A. 6 B. 15 C. 16 D. 21

    【答案】：1+2+3+4+5+1=16, C

16. 【2011 统考真题】下列关于图的叙述中，正确的是(）。

    I.回路是简单路径 II. 存储稀疏图，用邻接矩阵比邻接表更省空间 III. 若有向图中存在拓扑序列，则该图不存在回路 A.仅II B.仅I、II C.仅III D.仅I、III

    【答案】：C 简单回路是简单路径，回路是路径！

17. 【2013 统考真题】设图的邻接短阵A如下所示，各项点的度依次是（）。

    $$\begin{array}{}\text{(1)}& \left[\begin{array}{cccc}0& 1& 0& 1\\ 0& 0& 1& 1\\ 0& 1& 0& 0\\ 1& 0& 0& 0\end{array}\right]\end{array}$$

    A. 1,2, 1, 2 B. 2, 2, 1, 1 C. 3,4, 2,3 D. 4,4,2,2

    【答案】：C

18. 【2017统考真题】已知无向图G含有16条边，其中度为4的顶点个数为3，度为3的顶点个数为4，其他顶点的度均小于 3。图G所含的项点个数至少是（）， A. 10 B. 11 C. 13 D. 15

    【答案】：32 = 12 + 12 + (n-7)2 => 8 = 2n - 14，B