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

admin2015-12-30 17

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

选项 A、存在，且唯一
B、存在，且不唯一
C、存在，可能不唯一
D、无法确定是否存在

答案C

解析对角线以下元素均为零，表明只有顶点i到顶点j(i＜j)可能有边，而顶点j到顶点i一定没有边，即有向图是一个无环图，因此一定存在拓扑序列。对于拓扑序列是否唯一，试举一例：设有向图的邻接矩阵

，则存在两个拓扑序列，因此该图存在可能不唯一的拓扑序列。
结论：对于任一有向图，如果它的邻接矩阵中对角线以下(或以上)的元素均为零，则存在拓扑序列(可能不唯一)。反正，若图存在拓扑序列，却不一定能满足邻接矩阵中主对角线以下的元素均为零，但是可以通过适当地调整结点编号，使其邻接矩阵满足前述性质。

转载请注明原文地址:https://kaotiyun.com/show/UBRi777K

计算机408

相关试题推荐

随机试题

最新回复(0)