首页 > 试题广场 >

若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图

[单选题]

若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图（）。

```
是个有根有向图
```
```
含有多个入度为0的顶点
```
```
是个强连通图
```

含有顶点数目大于1的强连通分量

👿👻💀👽邹

答案是D,因为不能排成拓扑序列说明该有向图中有环路

A为有拓扑序列,B有环路并不能保证所有顶点都是连通,C不能确定有几个

发表于 2019-11-17 16:19:57 回复(1)

诸葛大大力力

对于一张有向图而言，它是强连通的当且仅当其上每两个顶点都相互可达。强连通图类似于嵌套的环，强连通图一定有环

发表于 2021-08-02 15:50:08 回复(1)

无法显示网名，请稍等......

对于C选项和D选项，可以用这张图来说明，此图显然不能排成拓扑排序，且此图不是强联通图(即不能判定C选项），但显然满足D选项。

发表于 2022-04-19 17:15:57 回复(2)

吉点

aov网定义不能以自己作为前驱或者后继

发表于 2022-11-29 21:36:26 回复(0)

cywang929

无法生成拓扑排序说明一定有环。

强连通图一定有环，但有环不一定是强连通图。

但是只要有环至少存在强连通分量。

发表于 2021-09-05 13:21:09 回复(4)

牛客538492765号

首先需要清楚的是有环的有向图是无法进行拓扑排序的，对于选项A,一个有根的和多个有根的（B、含有多个入度为0）有向图都是可以进行拓扑排序的；D说明的是该有向图中不存在一个或多个环，C说明该有向图中各个点到各个点都存在着环【D包含C】,故选D项

编辑于 2021-05-05 17:46:05 回复(1)

天尊墨宇

选D

拓扑序列是顶点活动网中将活动按发生的先后次序进行的一种排列。拓扑排序，是对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

强连通图（Strongly Connected Graph）是指在有向图G中，如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。

发表于 2020-07-08 10:56:02 回复(1)

提交观点

问题信息

图

上传者：星辰大海的碎片

难度：

7条回答 8收藏 10358浏览

若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图

问题信息

热门推荐

相关试题