单选题
21.
在有向图G的拓扑序列中,若顶点V
i
在顶点V
j
之前,则下列情形不可能出现的是( )。
A、
G中有弧<V
i
,V
j
>
B、
G中有一条从V
i
到V
j
的路径
C、
G中没有弧<V
i
,V
j
>
D、
G中有一条从V
j
到V
i
的路径
【正确答案】
D
【答案解析】
考查拓扑序列的性质。选项D中的情况是不可能出现的,因此若G中有一条V
i
到V
j
的路径,则要把V
j
消去以后才能消去V
i
,即在图的拓扑序列中顶点V
j
应该在顶点V
i
之前。以分析中的示例说明:若有一条V
j
到V
i
的路径,说明V
j
是V
i
的前驱,则拓扑排序V
j
应该在V
i
的前面,显然矛盾。
提交答案
关闭