我要招人

去企业版

首页 > 试题广场 >

设某强连通有向图中有 n 个顶点，则该强连通图中至少有（

[单选题]

设某强连通有向图中有 n 个顶点，则该强连通图中至少有（）条边。

```
n(n-1)
```
```
n+1
```
```
n
```
```
n(n+1)
```

查看答案及解析

天涯咫尺

1：强连通图的定义：

在有向图G中，如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。

2：分析：

可知当n个节点的图构成一个环，任意两点之间存在着回路，于是最小的边数为n;最大边数为n(n-1);

发表于 2017-08-30 09:16:43 回复(4)

搞个好点的名字有那么难么。。。对。。。很难

强连通图中有n个顶点，当存在一个环时，需要的边的数目是最少的，所以有n个顶点的环最少需要n条边

发表于 2017-07-14 17:30:54 回复(1)

yanl_

强连通图 --- 有向图

连通图、连通分量 --- 无向图

发表于 2020-06-19 15:40:57 回复(0)

牛客218196695号

强连通图：如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，区别于完全图：任意两点间都可直达，强连通图，可间接到达所以N 个结点的强连通图，至少有 N条边

发表于 2020-06-26 08:33:34 回复(0)

sgbs

答案对吗？？？有谁可以给解释下

发表于 2017-06-14 08:40:20 回复(1)

袄一

强连通有向图中至少有 n 条边。至多有 n(n-1) 条边。

连通无向图中至少有 n-1 条边。至多有 n(n-1)/2 条边。

发表于 2023-04-18 17:36:47 回复(0)

hptc

最少n成环，最多完全图

发表于 2019-09-30 15:18:44 回复(0)

许愿接好运

发表于 2023-11-22 16:11:09 回复(0)

simon_free

在有向图中，如果存在一条从顶点u到顶点v的路径以及一条从顶点v到顶点u的路径，则称这两个顶点是强连通的。一个有向图被称为强连通图，如果图中的每一对顶点都是强连通的。

对于一个包含n个顶点的强连通有向图：

最少边的数量：我们可以找到一种构造方法使得边的数量最小。这种方法就是创建一个环形结构，所有的顶点都连接在一起形成一个循环。这样，每个顶点都有出度和入度至少为1，满足了强连通的条件。因此，在这种情况下，最少需要 n 条边来构成一个包含n个顶点的强连通有向图。

最多边的数量：我们可以通过构造一个完全有向图来使边的数量最多。在完全有向图中，每对不同的顶点之间都有一条方向任意的边。因此，在这种情况下，最多需要 n*(n-1) 条边来构成一个包含n个顶点的强连通有向图。

发表于 2023-11-16 13:25:06 回复(0)

牛客915976740号

有向图中，区分强连通图和完全图需要的最少边数。

发表于 2022-11-12 16:43:49 回复(0)

rosenne

大于n-1条边，则必有环

发表于 2022-07-11 21:43:15 回复(0)

修心不唯心

他说至少

发表于 2020-03-18 20:43:13 回复(0)

找工作拿offer

1：强连通图的定义：

在有向图G中，如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图

发表于 2019-09-02 11:10:41 回复(0)

提交观点

问题信息

图

上传者：阿奻_

难度：

13条回答 304收藏 18474浏览

设某强连通有向图中有 n 个顶点，则该强连通图中至少有（

问题信息

热门推荐

相关试题

设某强连通有向图中有 n 个顶点，则该强连通图中 至少有（

问题信息

热门推荐

相关试题

设某强连通有向图中有 n 个顶点，则该强连通图中至少有（