2. 考研
  3. 以下关于图的说法正确的是( )。 ． I在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧 Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O，则该图的拓扑序列必定存在 Ⅲ在．AOE网中一定只有一条

以下关于图的说法正确的是( )。 ． I在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧 Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O，则该图的拓扑序列必定存在 Ⅲ在．AOE网中一定只有一条

admin2012-06-26  80
问题 以下关于图的说法正确的是(          )。    ．
    I在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧
    Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O，则该图的拓扑序列必定存在
    Ⅲ在．AOE网中一定只有一条关键路径
选项 A、I、Ⅱ
B、Ⅱ、Ⅲ
C、I、Ⅲ
D、仅有Ⅱ
答案D
解析 说法I是错误的，在一个有向图的拓扑序列中，若顶点a在顶点b之前，只能说明顶点a到顶点b有一条路径。
    说法Ⅲ是错误的，AOE网中可能有不止一条关键路径，它们的路径长度相同。
    说法Ⅱ是正确的。任意n个顶点的有向无环图都可以得到一个拓扑序列。设拓扑序列为v0，v1，…，vn-1，证明此时的邻接矩阵A为上三角矩阵，可用反证法证明。假设此时的邻接矩阵不是上三角矩阵，那么，存在下标i和j(i>j)，使得A[j]不等于0，即图中存在从vi到vj的一条有向边。由拓扑序列的定义可知，在任意拓扑序列中，vi的位置一定在vj之前，而上述拓扑序列v0，v1，…，vn-1中，由于i>j，即vi的位置在vj之后，导致矛盾。因此说法Ⅱ是正确的。
转载请注明原文地址:https://kaotiyun.com/show/ryxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)