题30

题30

题目

【2012 统考真题】若用邻接矩阵存储有向图, 矩阵中主对角线以下的元素均为零, 则关于该图拓扑序列的结论是 ( ).
A. 存在，且唯一
B. 存在, 且不唯一
C. 存在, 可能不唯一
D. 无法确定是否存在

分析

主对角元素以下都是0，这说明这是一个单向的图，两个点之间，只会有一个点指向另一个点
显然这个拓扑序是存在的，因为只有互相指也就是环，才会没有拓扑序，这里的不唯一是同级别的点造成的，比如a同时指向b和c，那么b和c的顺序是不确定的

解

C
对角线以下元素均为零,表明只有顶点 到 可能有边,而顶点 到 一定没有边, 即有向图是一个无环图, 因此一定存在拓扑序列。对于拓扑序列是否唯一, 试举一例: 设有向
图的邻接矩阵 ,存在两个拓扑序列,因此该图存在可能不唯一的拓扑序列。
结论: 对于任一有向图, 若它的邻接矩阵中对角线以下 (或以上) 的元素均为零, 则存在拓扑序列 (可能不唯一)。
反正, 若图存在拓扑序列, 却不一定能满足邻接矩阵中主对角线以下的元素均为零, 但是可以通过适当地调整结点编号, 使其邻接矩阵满足前述性质。