题21

题21

题目

下列关于图的说法中, 正确的是 ( ).
I. 有向图中顶点 的度等于其邻接矩阵中第 行中 1 的个数
II. 无向图的邻接矩阵一定是对称矩阵, 有向图的邻接矩阵一定是非对称矩阵
III. 在带权图 的最小生成树 中,某条边的权值可能会超过未选边的权值
IV. 若有向无环图的拓扑序列唯一, 则可以唯一确定该图
A. I、 II 和 III
B. III 和 IV
C. III
D. IV

分析

有向图的度同时包含了入度和出度，所以1还要加上它对应的列
第四个这个说法，因为存在一种情况，就是有两个节点的入度和出度都是0，这样的话，拓扑序列就不唯一了
对于第二个说话，比如这是一个自环，那么这个对角线上的元素就不是0，或者说，每两个点都互相指向

解

C
有向图邻接矩阵的第 行中 1 的个数是顶点 的出度,而有向图中顶点的度为入度与出度之和, I 错。
无向图的邻接矩阵一定是对称矩阵, 但当有向图中任意两个顶点之间有边相连, 且是两条方向相反的有向边时, 有向图的邻接矩阵也是一个对称矩阵, II 错。
最小生成树中的 条边不能保证是图中权值最小的 条边,因为权值最小的 条边并不一定能使图连通。
在下图中, 左图的最小生成树如下图所示, 权值为 3 的边不在其最小生成树中。


有向无环图的拓扑序列唯一并不能唯一确定该图。在下图所示的两个有向无环图中, 拓扑序列都为 错。注意,很多辅导书对该命题的判断是错误的。