在一个有向图G的拓扑序列中,顶点Vi排列在Vj之前,说明图G中(59)。A.一定存在弧

Question

在一个有向图G的拓扑序列中，顶点Vi排列在Vj之前，说明图G中（59）。

A.一定存在弧＜vi,vj＞

B.一定存在弧＜vj,vi＞

C.可能存在vi到vj的路径，而不可能存在vj到vi的路径

D.可能存在vj到vi的路径，而不可能存在vi到vj的路径

Answer 1

正确答案：C
拓扑序列是拓扑排序的产出物。对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。由此可见，如果Vi排列在Vj之前，说明可能存在vi到vj的路径，而不可能存在vj到vi的路径。