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

admin2019-05-20  39

问题 在有向图G的拓扑序列中,若顶点vi在顶点vj之前,则下列情形不可能出现的是(    )。

选项 A、G中有弧i,vh>
B、G中有一条从vi到vj的路径
C、G中没有弧i,vj>
D、G中有一条从vj到vi的路径

答案D

解析 此题考查的知识点是图的拓扑排序。根据拓扑排序的定义,若顶点vi与顶点vj有一条弧,则拓扑序列中顶点vi必在顶点vj之前。若有一条从vj到vi的路径,则顶点vi不可能在顶点vj之前。所以应选D。
转载请注明原文地址:https://jikaoti.com/ti/JOGjFFFM
0

最新回复(0)