首页 > 试题广场 >

在一个有向图的拓扑序列中,若顶点 a 在顶点 b 之前,则图

[单选题]
在一个有向图的拓扑序列中,若顶点 a 在顶点 b 之前,则图中必有一条弧<a,b>。( )
  • 正确
  • 错误
推荐
选B。该题考察的是拓扑排序的概念,如果从 a 到 有一条有向路径,则 一定排在 之前,反过来也应该以“路径”更准确。
注意区分“路径”和“”:
  • :指的是有向图里面的边,有明确方向的。如果是无向图的边,直接叫做“边”。比如有向图的 v1 结点到 v2 结点的弧可能是:<v1, v2>;

  • 路径:指的是图(包括有向图和无向图)里面连接两个结点之间的边的集合,也就是一个顶点序列。比如:v1 到 v3 的路径可能这样表示:<v1, v2>、<v2, v3>;
如下图举例所示:顶点 a 在顶点 b 之前,但没有弧<a,b>,而是一条路径<a,c><c,b>


编辑于 2019-05-24 14:46:54 回复(2)
比如a→b→c,a在c前面,但不存在弧,弧是什么,是指直接相连
发表于 2022-04-17 18:22:00 回复(0)
有这个路径,不一定有这个弧
发表于 2019-07-02 09:29:17 回复(0)
选A

在一个有向图的拓扑序列中,若顶点a在顶点b之前,只能说明顶点a到顶点b有一条路径
发表于 2019-05-23 21:06:49 回复(0)
怎么看都是选A
发表于 2022-02-03 22:21:48 回复(0)