在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是( )。

admin2019-12-10 20

问题在有向图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的前面，显然矛盾。

转载请注明原文地址:https://kaotiyun.com/show/Ls3i777K

本试题收录于：计算机408题库学硕统考专业分类