A-A+

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

2022-08-12 16:06:14 问答库阅读 196 次

问题详情

在有向图G的拓扑序列中，若顶点vi在顶点vj之前，则下列情形不可能出现的是()。
A．G中有弧＜口i，vj＞
B．G中有一条从vi到vj的路径
C．G中没有弧<＜vi，vj＞
D．G中有一条从vj到vi的路径

请帮忙给出正确答案和分析，谢谢！

正确答案：D
此题考查的知识点是图的拓扑排序。根据拓扑排序的定义，若顶点vi与顶点vj有一条弧，则拓扑序列中顶点vi必在顶点vj之前。若有一条从vi到vj的路径，则顶点vi不可能在顶点vj之前。所以应选D。