单选题
在有向图G的拓扑序列中，若顶点所在顶点V
j
之前，则下列情形不可能出现的是( )。【南京理工大学2000一、9(1．5分)】【江苏大学2006一、1(2分)】
A、
G中有弧
j>
B、
G中有一条从V
i
到V
j
的路径
C、
G中没有弧
i，V
j
>
D、
G中有一条从V
j
到V
j
的路径
【正确答案】
D
【答案解析】
解析：若有向图G的拓扑序列中，顶点Vi在顶点Vj之前，不可能出现有一条从Vj到Vi的路径。因为若是有这样一条路径，说明图中存在回路，不可能拓扑排序成功。A、B和C都可能存在，即本题选择D。
提交答案
关闭