Question

若有向图具有拓扑排序序列，那么它的邻接矩阵必定为？

若一个有向图具有拓扑排序序列，那么它的邻接矩阵必定为？？？对称 稀疏 三角 一般

Answer 1

2->3->1这样顺序的图即可，直接就排除对称和三角了。

答案是三角。（这个三角不是特殊矩阵压缩存储时的三角矩阵，而是线性代数中的三角矩阵）

可以证明，对于有向图中顶点适当地编号，使其邻接矩阵为三角矩阵且主对角元全为零的充分必要条件是该有向图可以进行拓扑排序。

扩展资料：

给定有向图G=(VE)，并且给定该图G中的任意两个结点u和v，如果结点u与结点v相互可达，即至少存在一条路径可以由结点u开始，到结点v终止，同时存在至少有一条路径可以由结点v开始，到结点u终止，那么就称该有向图G是强连通图。

对于有向图最短路问题，计算步骤与求解无向图最短路问题相同，主要区别在于：无向图最短路问题使用单标号法。单标号法是对每一点赋予一个路权标号；而有向最短路问题使用双标号法．双标号法是对每一点赋予两个标号：路径和路权。

参考资料来源：百度百科-有向图

Answer 2

就此题来说，答案应该是一般。
另外给出另一方面的分析，希望能对此题有所帮助。
题目：若一个有向图具有有序的拓扑排序序列，那么它的邻接矩阵必定为？（比原题加了个有序的）
答案是三角。（这个三角不是特殊矩阵压缩存储时的三角矩阵，而是线性代数中的三角矩阵）
可以证明，对于有向图中顶点适当地编号，使其邻接矩阵为三角矩阵且主对角元全为零的充分必要条件是该有向图可以进行拓扑排序。

Answer 3

2->3->1这样顺序的图ok不？直接就排除对称和三角了

Answer 4

Answer 5

应该是3角吧，主要是有向图