题19
题目
若一个有向图具有有序的拓扑排序序列, 则它的邻接矩阵必定为 ( ).
A. 对称
B. 稀疏
C. 三角
D. 一般
分析
此题一直以来争议较大, 因为有些书中漏掉了 “有序” 二字。可以证明, 对有向图中的顶点适当地编号, 使其邻接矩阵为三角矩阵且主对角元素全为零的充分必要条件是, 该有向图可以进行拓扑排序。若这个题目把 “有序” 二字去掉, 显然应选 D。但此题题干中已经指出是 “有序的拓扑序列”, 因此应选 C。需要注意的是, 若一个有向图的邻接矩阵为三角矩阵 (对角线以上或以下的元素为 0 ), 则图中必不存在环, 因此其拓扑序列必然存在。
解
C