若用邻接矩阵存储有向图,矩阵中主对角线及以下的元素均为零,则关于该图拓扑序列的结论是()。
存在,且唯一
存在,且不唯一
存在,可能不唯一
无法确定是否存在
对角线以下元素均为零,表明只有顶点i到顶点j(i<j)可能有边,而顶点j到顶点i一定没有边,即有向图是一个无环图,因此一定存在拓扑序列。对于拓扑序列是否唯一,试举一例:设有向图的邻接矩阵,则存在两个拓扑序列,因此该图存在可能不唯一的拓扑序列。
结论:对于任一有向图,如果它的邻接矩阵中对角线以下(或以上)的元素均为零,则存在拓扑序列(可能不唯一)。反正,若图存在拓扑序列,却不一定能满足邻接矩阵中主对角线以下的元素均为零,但是可以通过适当地调整结点编号,使其邻接矩阵满足前述性质。
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题
对角线以下元素均为零,表明只有顶点i到顶点j(i<j)可能有边,而顶点j到顶点i一定没有边,即有向图是一个无环图,因此一定存在拓扑序列。对于拓扑序列是否唯一,试举一例:设有向图的邻接矩阵,则存在两个拓扑序列,因此该图存在可能不唯一的拓扑序列。
结论:对于任一有向图,如果它的邻接矩阵中对角线以下(或以上)的元素均为零,则存在拓扑序列(可能不唯一)。反正,若图存在拓扑序列,却不一定能满足邻接矩阵中主对角线以下的元素均为零,但是可以通过适当地调整结点编号,使其邻接矩阵满足前述性质。