1、以下关于图的叙述中，正确的是（）。

• ? A：强连通有向图的任何顶点到其他所有顶点都有弧
• ? B：图的任意顶点的入度等于出度
• ? C：有向完全图一定是强连通有向图
• ? D：有向图的边集的子集和顶点集的子集可构成原有向图的子图

解析

强连通有向图的任何顶点到其他所有顶点都有路径，但未必有弧；无向图任意顶点的入度等于出度，但有向图未必满足；若边集中的某条边对应的某个顶点不在对应的顶点集中，则有向图的边集的子集和顶点集的子集无法构成子图。

答案：C

2、一个有28条边的非连通无向图至少有（）个顶点。

• ? A：7
• ? B：8
• ? C：9
• ? D：10

解析

考虑非连通图最极端的情况，即它由一个完全图加一个独立的顶点构成，此时若再加一条边，则必然使图变成连通图。在28=n(n-1)/2=8x7/2条边的完全无向图中，总共有8个顶点，再加上1个不连通的顶点，共9个顶点。

答案：C

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

• ? A：11
• ? B：12
• ? C：15
• ? D：16

解析

由于在具有n个顶点、e条边的无向图中，有=2e，可求得度为2的顶点数为7，从而共有16个（5+4+7）顶点。

答案：D

4、设有无向图G=(V,E)和G'=(V',E')，若G'是G的生成树，则下列不正确的是（）。

Ⅰ.G'为G的连通分量 Ⅱ. G'为G的无环子图 Ⅲ. G'为G的极小连通子图且V'=V

• ? A：Ⅰ、Ⅱ
• ? B：只有Ⅲ
• ? C：Ⅱ、Ⅲ
• ? D：只有Ⅰ

解析

一个连通图的生成树是一个极小连通子图，显然它是无环的，故Ⅰ、Ⅲ正确。极大连通子图称为连通分量，G'连通但非连通分量。 极大连通子图：如果图本来就不是连通的，那么每个子部分若包含它本身的所有顶点和边，则它就是极大连通子图。

答案：D

5、若具有n个顶点的图是一个环，则它有（）棵生成树。

• ? A：
  
• ? B：n
• ? C：n-1
• ? D：1

解析

n个顶点的生成树是具有n-1条边的极小连通子图，因为n个顶点构成的环共有n条边，去掉任意一条边就是一棵生成树，所以共有n种情况，所以可以有n棵不同的生成树。

答案：B

6、下列关于无向连通图特性的叙述中，正确的是（）。

Ⅰ. 所有顶点的度之和为偶数 Ⅱ. 边数大于顶点个数减1 Ⅲ. 至少有一个顶点的度为1

• ? A：只有Ⅰ
• ? B：只有Ⅱ
• ? C：Ⅰ和Ⅱ
• ? D：Ⅰ和Ⅲ

解析

无向连通图对应的生成树也是无向连通图，但此时边数等于顶点数减1，故Ⅱ错误。考虑一个无向连通图的顶点恰好构成一个回路的情况，此时每个顶点的度都是2，故Ⅲ错误。在无向图中，所有顶点的度之和为边数的2倍，故Ⅰ正确。

答案：A

7、若无向图G=（V，E）中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是（）。

• ? A：6
• ? B：15
• ? C：16
• ? D：21

解析

答案：C

8、一个有n个顶点的图用邻接矩阵A表示，若图为有向图，顶点的入度是（）；若图为无向图，顶点的度是（）。

在这里插入图片描述

解析

有向图的入度是其第i列的非0元素之和，无向图的度是第i行或第i列的非0元素之和。

答案：B、D

9、n个顶点的无向图的邻接表最多有（）个边表结点。

• ? A：
  
• ? B：n(n-1)
• ? C：n(n+1)
• ? D：n(n-1)/2

解析

n个顶点的无向图最多有n(n-1)/2条边，每条边在邻接表中存储两次，所以边表结点最多为n(n-1)个。

答案：B

10、对邻接表的叙述中，（）是正确的。

• ? A：无向图的邻接表中，第i个顶点的度为第i个链表中结点数的两倍
• ? B：邻接表比邻接矩阵的操作更简便
• ? C：邻接矩阵比邻接表的操作更简便
• ? D：求有向图结点的度，必须遍历整个邻接表

解析

无向图的邻接表中，第i个顶点的度为第i个链表中的结点数，故A错。 邻接表和邻接矩阵对于不同的操作各有优势，B和C都不准确。 有向图结点的度包括出度和入读，对于出度，需要遍历顶点表结点所对应的边表；对于入读，则需要遍历剩下的全部边表，故D正确。

答案：D

学海无涯苦作舟