凑数

图中有关路径的定义是

A.由顶点和相邻顶点序偶构成的边所形成的序列

B.由不同顶点所形成的序列

C.由不同边所形成的序列

D.上述定义都不是

解析

$\color{red}{\text{A.}}$由顶点和相邻顶点序偶构成的边所形成的序列

注意$\color{red}{\text{图}}$中$\color{green}{\text{路径}}$是$\color{red}{\text{顶点序列}}$，不是边序列

总结

题型	错因	教训	视频讲解
定义题	None		nan

一个有n个顶点和n条边的无向图一定是

A.连通的

B.不连通的

C．无环的

D.有环的

解析

$\color{red}{\text{D.有环的}}$

若一个无向图有n个顶点和n-1条边，可以使它连通但没有环(即生成树)，但再加一条边，在不考虑重边的情形下，则必然会构成环。

关于A选项，一个环+一个单独节点，不连通

总结

题型	错因	教训	视频讲解
性质题	None	举例子永远的神	nan

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

A.强连通图

B.连通图

C．有回路

D.一棵树

解析

$\color{red}{\text{B.连通图}}$

$\color{red}{\text{强连通图是有向图}}$，与题意矛盾，选项A错误;

对无向连通图做一次深度优先搜索，可以访问到该连通图的所有顶点，选项B正确;

有回路的无向图不一定是连通图，因为回路不一定包含图的所有结点，选项C错误;

连通图可能是$\color{red}{\text{树}}$，也可能存在$\color{red}{\text{环}}$，选项D错误。

总结

题型	错因	教训	视频讲解
None	性质题	强连通图是对于有向图而言的	nan

$\color{red}{\text{【2011统考真题】下列关于图的叙述中，正确的是（)。}}$

I回路是简单路径

II．存储稀疏图，用邻接矩阵比邻接表更省空间

III．若有向图中存在拓扑序列，则该图不存在回路

A.仅II

B.仅I、II

C．仅I

D.仅I、III

解析

$\color{red}{\text{C．仅I}}$

回路对应于路径，简单回路对应于简单路径，故Ⅰ错误;

稀疏图是边比较少的情况，此时用邻接矩阵必将浪费大量的空间，应选用邻接表，故Ⅱ错误。

存在回路的图不存在拓扑序列，Ⅲ正确。

II和Ⅲ中所涉知识点请参阅后面的内容。

总结

题型	错因	教训	视频讲解
性质题	None		nan

以下关于图的叙述中，正确的是（)。

A.图与树的区别在于图的边数大于等于顶点数

B．假设有图G={V,{E}}，顶点集$V’ \in V$,$E’ \in E$，则$V’$和{$E’$}构成G的子图

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

D.图的遍历就是从图中某一顶点出发访遍图中其余顶点

解析

$\color{red}{\text{C.}}$无向图的连通分量是指无向图中的极大连通子图

图与树的区别是$\color{red}{\text{逻辑上}}$的区别，而不是边数的区别，图的边数也可能小于树的边数，故选项A错;

若E中的边对应的顶点不是V的元素，V和{E}无法构成图，故选项B错;

无向图的$\color{red}{\text{极大连通子图}}$称为$\color{red}{\text{连通分量}}$，选项C正确;

图的遍历要求每个结点只能被访问一次，且若图$\color{red}{\text{非连通}}$，则从某一顶点出发$\color{red}{\text{无法}}$访问到其他全部顶点，选项D的说法不准确。

总结

题型	错因	教训	视频讲解
性质题	性质不清	考虑非连通的情况	nan

【2009统考真题】下列关于无向连通图特性的叙述中，正确的是（)。

I所有顶点的度之和为偶数

II.边数大于顶点个数减1

III.至少有一个顶点的度为1

A．只有Ⅰ

B.只有Ⅱ

C.I和II

D.Ⅰ和III

解析

$\color{red}{\text{A．}}$只有Ⅰ

无向连通图对应的$\color{red}{\text{生成树}}$也是无向连通图，但此时边数等于顶点数$\color{red}{\text{减1}}$，故Ⅱ错误。

考虑一个无向连通图的顶点恰好构成一个$\color{red}{\text{回路}}$的情况，此时每个顶点的度都是2，故Ⅲ错误。

在无向图中，所有顶点的度之和为边数的2倍，故Ⅰ正确。

总结

题型	错因	教训	视频讲解
性质题	None		nan

【2010统考真题】若无向图G=(V,E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是（)。

A. 6

B.15

C. 16

D.21

解析

$\color{red}{\text{C. 16}}$

题干要求在“$\color{red}{\text{任何情况}}$”下都是连通的，考虑最极端的情形，即图G的6个顶点构成一个完全无向图，再加上一条边后，第7个顶点必然与此完全无向图构成一个连通图，所以最少边数=6×5/2+1=16。若边数n小于等于15，可以使这n条边仅连接图G中的某6个顶点，从而导致第7个顶点无法与这6个顶点构成连通图（不满足“任何情况”)。

总结

题型	错因	教训	视频讲解
计算题	因素考虑完全	注意又要任何情况又要连通	nan

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

A．强连通有向图的任何顶点到其他所有顶点都有弧

B．图的任意顶点的入度等于出度

C．有向完全图一定是强连通有向图

D.有向图的边集的子集和顶点集的子集可构成原有向图的子图

解析

$\color{red}{\text{C．}}$有向完全图一定是强连通有向图

强连通有向图的任何顶点到其他所有顶点都有$\color{red}{\text{路径}}$，但未必有$\color{red}{\text{弧}}$;

无向图任意顶点的入度等于出度，但有向图未必满足;

若边集中的某条边对应的某个顶点不在对应的顶点集中，则有向图的边集的子集和顶点集的子集无法构成子图。

总结

题型	错因	教训	视频讲解
性质题			nan

9.【2013统考真题】设图的邻接矩阵A如下所示，各顶点的度依次是（ )。

A. 1,2,1,2

B.2,2,1,1

C.3,4,2,3

D.4,4,2,2

解析

$\color{red}{\text{C}}$.3,4,2,3

邻接矩阵A为$\color{red}{\text{非对称矩阵}}$，说明图是有向图，度为入度与出度之和。各顶点的度是矩阵中此结点对应的行（对应出度）和列(对应入度）的非零元素之和。

总结

题型	错因	教训	视频讲解
定义题	None		nan

10.一个有28条边的非连通无向图至少有（)个顶点。

A.7

B.8

C.9

D.10

解析

此题的解题思路和第7题的恰好相反。考查至少有多少个顶点的情形，我们考虑该非连通图最极端的情况，即它由一个完全图加一个独立的顶点构成，此时若再加一条边，则必然使图变成连通图。在28=n(n-1)/2=8×7/2条边的完全无向图中，总共有8个顶点，再加上1个不连通的顶点，共9个顶点。

无向完全图,边数与顶点关系

总结

题型	错因	教训	视频讲解
性质题	Null		nan

11.对于一个有n个顶点的图:若是连通无向图，其边的个数至少为();若是强连通有向图，其边的个数至少为().

A. n -1,n

B. n -1, n(n -1)

C. n, n

D. n, n(n - 1)

解析

对于连通无向图，边最少即构成一棵树的情形;对于强连通有向图，边最少即构成一个有向环的情形。

总结

题型	错因	教训	视频讲解
性质题	因素考虑完全	强连通有向图最少是环	nan

12．无向图G有23条边，度为4的顶点有5个，度为3的顶点有4个，其余都是度为2的顶点，则图G最多有（)个顶点。

A. 11

B.12

C.15

D.16

解析

$\color{red}{\text{D.}}$16

由于在具有n个顶点、e条边的无向图中，有艺TD(v,)=2e，故可求得度为2的顶点数为7，从而最多有16个顶点。

无向图的度的性质

总结

题型	错因	教训	视频讲解
性质题	None		nan

13．在有n个顶点的有向图中，每个顶点的度最大可达()。

A. n

B. n -1

C. 2n

D. 2n-2

解析

$\color{red}{\text{D.}}$ 2n-2

在有向图中，顶点的度等于入度与出度之和。n个顶点的有向图中，任意一个顶点最多还可以与其他n-1个顶点有一对指向相反的边相连。

总结

题型	错因	教训	视频讲解
性质题	因素考虑完全	没看清楚题目说的是有向图	nan

14．具有6个顶点的无向图，当有（）条边时能确保是一个连通图。

A. 8

B.9

C.10

D. 11

解析

解题思路与第7题类似。5个顶点构成一个完全无向图，需要10条边;再加上1条边后，能保证第6个顶点必然与此完全无向图构成一个连通图，故共需11条边。

总结

题型	错因	教训	视频讲解
性质题	None		nan

15.【2017统考真题】已知无向图G含有16条边，其中度为4的顶点个数为3，度为3的顶点个数为4，其他顶点的度均小于3。图G所含的顶点个数至少是()。

A. 10

B.11

C.13

D. 15

解析

$\color{red}{\text{B}}$ 11

无向图边数的2倍等于各顶点度数的总和。由于其他顶点的度均小于3，设它们的度都为⒉，设它们的数量是x，列出这方程4×x3+3x4+2x = 16x2，解得x=4。4＋4+3= 11，选项B正确。

总结

题型	错因	教训	视频讲解
计算	None		nan

16.设有无向图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、II

D.只有Ⅰ

解析

$\color{green}{\text{D.}}$ 只有Ⅰ

一个连通图的生成树是一个极小连通子图，显然它是无环的，故II、III 正确。极大连通子图称为连通分量，G’连通但非连通分量。这里再补充一下“$\color{red}{\text{极大连通子图}}$”:如果图本来就不是连通的，那么每个子部分若包含它本身的所有顶点和边，则它就是极大连通子图。

总结

题型	错因	教训	视频讲解
性质题	概念不清	无向图的连通分量是极大连通子图，点边越多	nan

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

A. n2

B. n

C. n-1

D. 1

解析

因为n个顶点构成的环共有n条边，去掉其中任意一条便是一棵生成树,所以共有n种情况。

总结

题型	错因	教训	视频讲解
性质题	None		nan

18．若一个具有n个顶点、e条边的无向图是一个森林，则该森林中必有（)棵树。

A. n

B. e

C. n -e

D. 1

解析

n个结点的树有n-1条边，假设森林中有x棵树，将每棵树的根连到一个添加的结点，则成为一棵树，结点数是n+1，边数是e+x，从而可知x =n- e。

另解:设森林中有x棵树，则再用x-1条边就能把所有的树连接成一棵树，此时，边数+1=顶点数，即e +(x - 1)+1=n，故x =n-e。

总结

题型	错因	教训	视频讲解
性质题	None		nan

图G是一个非连通无向图，共有28条边，该图至少有多少个顶点?

解析

由于图G是一个非连通无向图，在边数固定时，顶点数最少的情况是该图由两个连通子图构成，且其中之一只含一个顶点，另一个为完全图。其中只含一个顶点的子图没有边，另一个完全图的边数为n(n-1)/2 = 28，得n=8。所以该图至少有1+8=9个顶点。

总结

题型	错因	教训	视频讲解
性质题	None		nan

如何对无环有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的1都集中到对角线以上?

解析

按各顶点的出度进行排序。n 个顶点的有向图，其顶点的最大出度是n-1，最小出度为0。这样排序后，出度最大的顶点编号为1，出度最小的顶点编号为n。之后，进行调整，即只要存在弧$<i,j>$，就不管顶点j的出度是否大于顶点i的出度，都把i编号在顶点j的编号之前，因为只有i≤j，弧$<i,j>$对应的1才能出现在邻接矩阵的上三角。

通过后面小节的学习，会发现采用拓扑排序并依次编号是一种更为简便的方法。

$\color{red}{\text{?????没看懂}}$

总结

题型	错因	教训	视频讲解
性质题	性质不清		nan

破圈法

下面是一种称为“破圈法”的求解最小生成树的方法:

所谓“破圈法”，是指“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。

试判断这种方法是否正确。若正确，说明理由;若不正确，举出反例（注:圈就是回路)。

解析

由于经过“破圈法”之后，最终没有回路，故一定可以构造出一棵生成树。

这里的前提是，没有回路就一定是最小生成树

下面证明这棵生成树是最小生成树。记“破圈法”生成的树为T，假设T不是最小生成树，则必然存在最小生成树T，使得它与T的公共边尽可能地多，则将T与T取并集，得到一个图，此图中必然存在回路，由于“破圈法”的定义就是从回路中去除权最大的边，此时生成的T的权必然是最小的，这与原假设T不是最小生成树矛盾，从而T是最小生成树。下图说明了“破圈法”的过程:

因为点是一样的，多了一条边，必然有环，而破圈法已经去掉了最大权值的边？：$\color{red}{\text{还是说不通}}$

总结

题型	错因	教训	视频讲解
			nan