任意n个结点的有向无环图都可以得到一个拓扑序列。设拓扑序列为v0v1v2…vn-1，我们来证明此时的邻接矩阵A为上三角矩阵。证明采用反证法。
假设此时的邻接矩阵不是上三角矩阵，那么，存在下标i和j（i>j），使得A[i][j]不等于零，即图中存在从vi到vj的一条有向边。由拓扑序列的定义可知，在任意拓扑序列中，vi的位置一定在vj之前，而在上述拓扑序列v0v1v2…vn-1中，由于i>j，即vi的位置在vj之后，导致矛盾。因此命题正确。
（简答题）
证明：只要适当地排列顶点的次序，就能使有向无环图的邻接矩阵中主对角线以下的元素全部为0。
正确答案
答案解析
略
相似试题
（简答题）
不同人的计算思维具有很大差别，请举例说明只要具有思维品质中的独创性，就能创造性地解决问题。
（判断题）
可从任意有向图中得到关于所有顶点的拓扑次序。
（填空题）
用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度（）的次序来得到最短路径的。
（单选题）
用深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈次序打印出相应的顶点，则输出的顶点序列是（）。
（填空题）
在一个有向图中，若存在弧，则在其拓扑序列中，顶点vi，vj，vk的相对次序为（）。
（单选题）
Adobe公司为描述页面排版开发了一种语言，事实上成为了页面排版第二代标准，它能使每个像素都清晰地排列并组成各种图形和文本。这个语言就是（）。
（填空题）
如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。
（简答题）
对于下图G4和G5，按下列条件试分别写出从顶点v0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 （1）假定它们均采用邻接矩阵表示； （2）假定它们均采用邻接表表示，并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。
（判断题）
异常处理器的排列次序影响处理异常的方法。
