96 KiB
图习题
基本概念
连通边数
例题 若无向图$G=(V,E)$中含有$7$个顶点，要保证图$G$在任何情况下都是连通的，则需要的边数最少是()。
A.6
B.15
C.16
D.21
解：$C$。题干要求在“任何情况”下都是连通的，考虑最极端的情形，即图$G$的$6$个顶点构成一个完全无向图，即在前六个顶点加上所有能加的边，一共需要$6\times5\div2$条（六个顶点连接其他五条，并且每条边连两个顶点）。再加上一条边后，第$7$个顶点必然与此完全无向图构成一个连通图，所以最少边数$=6\times5\div2+1=16$。若边数$n$小于等于$15$，可以使这$n$条边仅连接图$G$中的某$6$个顶点，从而导致第$7$个顶点无法与这$6$个顶点构成连通图，不满足“任何情况”。
例题 一个有$28$条边的非连通无向图至少有()个顶点。
A.7
B.8
C.9
D.10
解：$C$。考查至少有多少个顶点的情形，我们考虑该非连通图最极端的情况，即它由一个完全图加一个独立的顶点构成，此时若再加一条边，则必然使图变成连通图。在$28=n(n-1)\div2=8\times7\div2$条边的完全无向图中，总共有$8$个顶点，再加上$1$个不连通的顶点，共$9$个顶点。
顶点数
对于具有$n$个顶点，$e$条边的无向图，$\sum\limits_{i=1}^nTD(v_i)=2e$。无向图的边数两倍等于图各顶点度数的总和。
例题 无向图$G$有$23$条边，度为$4$的顶点有$5$个，度为$3$的顶点有$4$个，其余都是度为$2$的顶点，则图$G$最多有()个顶点。
A.11
B.12
C.15
D.16
解：$D$。由于$\sum\limits_{i=1}^nTD(v_i)=2e$，则$2\times23=4\times5+3\times4+2\times v_2$，则$v_2=7$，所以最多有$5+4+7=16$个顶点。
度数
例题 在有$n$个顶点的有向图中，每个顶点的度最大可达()。
A.n
B.n-1
C.2n
D.2n-2
解：$D$。在有向图中，顶点的度等于入度与出度之和。$n$个顶点的有向图中，任意一个顶点最多还可以与其他$n-1$个顶点有一对指向相反的边相连，所以一共$2(n-1)=2n-2$。
生成树与森林
例题 若具有$n$个顶点的图是一个环，则它有()棵生成树。
A.n^2
B.n
C.n-1
D.1
解：$B$。由于具有$n$个顶点的图是一个环，所以一共有$n$条边，而一个环去掉一条边就可以变成一棵生成树，所以可以去掉$n$种边得到$n$棵生成树。
例题 若一个具有$n$个顶点、$e$条边的无向图是一个森林，则该森林中必有()棵树。
A.n
B.e
C.n-e
D.1
解：$C$。$n$个结点的树有$n-1$条边，假设森林中有$x$棵树，将每棵树的根连到一个添加的结点，则成为一棵树，结点数是$n+1$，边数是$e+x=n$，从而可知$x=n-e$。另解设森林中有$x$棵树，则再用$x-1$条边就能把所有的树连接成一棵树，此时，边数$+1=$顶点数，即$e+(x-1)+1=n$，故$x=n-e$。
例题 设无向图$G=(V,E)$和$G'=(V',E')$，若$G'$是$G$的生成树，则下列说法中错误的是()。
$A.G'$为$G$的子图
$B.G'$为$G$的连通分量
$C.G'$为$G$的极小连通子图且V=V'
$D.G'$是$G$的一个无环子图
解：$B$。连通分量是无向图的极大连通子图，其中极大的含义是将依附于连通分量中顶点的所有边都加上，所以连通分量中可能存在回路，这样就不是生成树了。
例题 以下叙述中，正确的是()。
$A.$只要无向连通图中没有权值相同的边，则其最小生成树唯一
$B.$只要无向图中有权值相同的边，则其最小生成树一定不唯一
$C.$从$n$个顶点的连通图中选取$n-1$条权值最小的边，即可构成最小生成树
$D.$设连通图$G$含有$n$个顶点，则含有$n$个顶点、$n-1$条边的子图一定是$G$的生成树
解：$A$。选项$A$显然正确，图$G$中权值最小的边一定是最小生成树中的边。否则最小生成树加上权值最小的边后构成一个环，去掉环中任意一条非此边则形成了另一个权值更小的生成树。选项$B$，若无向图本身就是一棵树，则最小生成树就是它本身，这时就是唯一的。选项$C$，选取的$n-1$条边可能构成回路。选项$D$，含有$n$个顶点、$n-1$条边的子图可能构成回路，也可能不连通。
图的存储结构
邻接表
例题 若邻接表中有奇数个边表结点，则()。
$A.$图中有奇数个结点
$B.$图中有偶数个结点
$C.$图为无向图
$D.$图为有向图
解：$D$。无向图采用邻接表表示时，每条边存储两次，所以其边表结点的个数为偶数。题中边表结点为奇数个，故必然是有向图，且有奇数条边。
例题 假设有$n$个顶点、$e$条边的有向图用邻接表表示，则删除与某个顶点$v$相关的所有边的时间复杂度为()。
A.O(n)
B.O(e)
C.O(n+e)
D.O(ne)
解：$C$。删除与某顶点$v$相关的所有边的过程如下：先删除下标为$v$的顶点表结点的单链表，出边数最多为$n-1$，对应时间复杂度为$O(n)$；再扫描所有边表结点，删除所有的顶点$v$的入边，对应时间复杂度为$O(e)$。故总的时间复杂度为$O(n+e)$。
图的基本操作
图遍历
深度优先遍历
例题 无向图$G=(V,E)$，其中$V={a,b,c,d,e,f}$，$E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}$，对该图从$a$开始进行深度优先遍历，得到的顶点序列正确的是()。
A.a,b,e,c,d,f
B.a,c,f,e,b,d
C.a,e,b,c,f,d
D.a,e,d,f,c,b
解：$D$。可以画出$G$结构。$A$当遍历到$e$时应该遍历相邻且没有访问的$d$，而不是$c$。$B$访问到$f$应该访问$d$而不是$e$。$C$当访问完$a,e,b$这个序列后结束形成环，下一个访问的应该是与序列尾部$b$的父结点$e$相邻的没有访问的$d$而不是$c$。
例题 使用$DFS$算法递归地遍历一个无环有向图，并在退出递归时输出相应顶点，这样得到的顶点序列是()。
$A.$逆拓扑有序
$B.$拓扑有序
$C.$无序的
$D.$都不是
解：$A$。对一个有向图做深度优先遍历，并未专门判断有向图是否有环（有向回路）存在，无论图中是否有环，都得到一个顶点序列。若无环，在退出递归过程中输出的应是逆拓扑有序序列。（深度优先使用栈，先进后出）
图的应用
最短路径
Dijkstra算法
例题 对下图所示的有向带权图，若采用$Dijkstra$算法求从源点$a$到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是$b$，第二条最短路径的目标顶点是$c$，后续得到的其余各最短路径的目标顶点依次是()。
A.d,e,f
B.e,d,f
C.f,d,e
D.f,e,d
解：$C$。
| 顶点 | 第1轮 | 第2轮 | 第3轮 | 第4轮 | 第5轮 |
|---|---|---|---|---|---|
| b | (a,b)2 | ||||
| c | (a,c)5 | (a,b,c)3 | |||
| d | ∞ | (a,b,d)5 | (a,b,d)5 | (a,b,d)5 | |
| e | ∞ | ∞ | (a,b,c,e)7 | (a,b,c,e)7 | (a,b,d,e)6 |
| f | ∞ | ∞ | (a,b,c,f)4 | ||
| 集合S | {a,b} | {a,b,c} | {a,b,c,f} | {a,b,c,f,d} | {a,b,c,f,d,e} |
有向无环图
环路
例题 下面的()方法可以判断出一个有向图是否有环（回路）。
Ⅰ.深度优先遍历
Ⅱ.拓扑排序
Ⅲ.求最短路径
Ⅳ.求关键路径
$A.$Ⅰ、Ⅱ、Ⅳ
$B.$Ⅰ、Ⅲ、Ⅳ
$C.$Ⅰ、Ⅱ、Ⅲ
$D.$全部可以
解：$A$。使用深度优先遍历，若从有向图上的某个顶点$u$出发，在$DFS(u)$结束之前出现一条从顶点$v$到$u$的边，由于$v$在生成树上是$u$的子孙，则图中必定存在包含$u$和$v$的环，因此深度优先遍历方法可以检测出一个有向图是否有环。拓扑排序时，当某顶点不为任何边的头时才能加入序列，存在环路时环路中的顶点一直是某条边的头，不能加入拓扑序列。也就是说，还存在无法找到下一个可以加入拓扑序列的顶点，则说明此图存在回路。最短路径是允许有环的。至于关键路径能否判断一个图有环，则存在一些争议。关键路径本身虽然不允许有环，但求关键路径的算法本身无法判断是否有环，判断是否有环是关键路径的第一步——拓扑排序。所以这个问题的答案主要取决于你从哪个角度出发看问题，考生需要理解问题本身，真正统考时是不会涉及一些模棱两可的问题的。
拓扑序列
例题 一个有向图的顶点不能排成一个拓扑序列，则判定该有向图()。
$A.$含有多个出度为$0$的顶点
$B.$是个强连通图
$C.$含有多个入度为$0$的顶点
$D.$含有顶点数大于$1$的强连通分量
解：$D$。一个有向图中的顶点不能排成一个拓扑序列，表明其中存在一个顶点数目大于1的回路（环），该回路构成一个强连通分量。