请说明,只要适当地排列顶点的次序,就能使有向无环图的邻接矩阵中主对角线以下的元素全部为0
时间: 2024-02-26 10:53:11 浏览: 112
邻接矩阵无向图
对于任何一个有向无环图,都存在拓扑排序,即将图中的顶点排成一个序列,使得所有的有向边从排在前面的顶点指向排在后面的顶点。这个序列就是一个拓扑序。对于任何一条有向边 (i, j),在拓扑序中,顶点 i 出现在顶点 j 的前面。因此,如果我们将拓扑序中排在前面的顶点放在矩阵的前面,排在后面的顶点放在矩阵的后面,那么矩阵中主对角线以下的元素全部为0。这是因为,在拓扑序中排在前面的顶点不可能指向排在后面的顶点,因此在矩阵中主对角线以下的元素就是0。因此,只要适当地排列顶点的次序,就能使有向无环图的邻接矩阵中主对角线以下的元素全部为0。
阅读全文