2. 考研
  3. 若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是_______。

若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是_______。

admin2015-12-30  25
问题 若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是_______。
选项 A、存在，且唯一
B、存在，且不唯一
C、存在，可能不唯一
D、无法确定是否存在
答案C
解析 对角线以下元素均为零，表明只有顶点i到顶点j(i＜j)可能有边，而顶点j到顶点i一定没有边，即有向图是一个无环图，因此一定存在拓扑序列。对于拓扑序列是否唯一，试举一例：设有向图的邻接矩阵，则存在两个拓扑序列，因此该图存在可能不唯一的拓扑序列。
结论：对于任一有向图，如果它的邻接矩阵中对角线以下(或以上)的元素均为零，则存在拓扑序列(可能不唯一)。反正，若图存在拓扑序列，却不一定能满足邻接矩阵中主对角线以下的元素均为零，但是可以通过适当地调整结点编号，使其邻接矩阵满足前述性质。
转载请注明原文地址:https://jikaoti.com/ti/NXfjFFFM
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)