🏷️ 知识点：三角矩阵

若一个有向图具有有序的拓扑排序序列，则它的邻接矩阵必定为（ ）。

A. 对称 B. 稀疏 C. 三角 D. 一般

正确答案：C

结论

C。按拓扑序给顶点编号后，邻接矩阵必为严格上三角或严格下三角矩阵。

推导

拓扑序要求每条边都从序号较小顶点指向序号较大顶点，所以一种编号方向下非零元素只在主对角线上方；若反向编号，则只在下方。无自环时主对角线为 0。

易错点

A 对称性属于无向图；B 拓扑序不限制边数，不能推出稀疏；D 忽略了拓扑序带来的方向约束。