我要招人

去企业版

首页 > 试题广场 >

具有 7 个顶点的有向图至少应有多少条边才可能成为一个强连通

[单选题]

具有 7 个顶点的有向图至少应有多少条边才可能成为一个强连通图?

```
6
```
```
7
```
```
8
```
```
12
```

查看正确选项

SunburstRun

答案是B

强连通图是每个点都能到达另外一个点,因而需要7条边,这个题目也说的只是可能,如果是保证的话,那就需要更多了

编辑于 2015-11-07 14:34:08 回复(3)

脱氧核糖核酸

发表于 2016-06-30 09:23:26 回复(2)

yayamma

强连通图必须从任何一点出发都可以回到原处，每个节点至少要一条出路(单节点除外)至少有n条边，正好可以组成一个环

编辑于 2015-11-19 10:57:23 回复(0)

牛客561351号

注意题目所说的是有向图，因此是7条边，若为无向图，则是6条边

发表于 2016-03-24 19:46:44 回复(3)

josan

晕。最少啊可能啊把题目想复杂了，直接没选，认为题目错了尴尬。。。

有向图：强连通性

具有7个顶点的有向图至少应有多少条边才可能成为一个强连通图? 7 key: n

问题同：已知一个有向图具有7个顶点，且是一个强联通图，问至少多少条弧？ 7 key: n

具有7个顶点的有向图至少应有多少条边一定成为一个强连通图? 37 key:(n-1)(n-1) + 1

已知一个有向图具有7个顶点，且是一个强联通图，问至多多少条弧？ 42 key:(n-1)*n

无向图：连通性

具有7个顶点的无向图至少应有多少条边才可能成为一个连通图? 6 key:n-1

问题同：已知一个无向图具有7个顶点，且是一个连通图，问至少多少条边？ 6 key: n-1

具有7个顶点的无向图至少应有多少条边一定成为一个连通图? 16 key:(n-1)(n-2)/2 + 1

已知一个有向图具有7个顶点，且是一个强联通图，问至多多少条弧？ 21 key:(n-1)*n/2

发表于 2017-07-08 22:39:39 回复(0)

小虎牙

选B

直接构成一个环，这样就能强连通

发表于 2015-11-26 10:00:41 回复(0)

AAS48

环

发表于 2021-12-14 22:29:11 回复(0)

辉小歌

形成一个环，便可以任意的俩点都可以互相到达。

发表于 2022-07-06 19:09:38 回复(0)

牛客218196695号

强连通图: 若对于每一对顶点v1和v2, 都存在一条从v1到v2和从v1到v2的路径,则称此图是强连通图. 最少的边是形成一个环， n 条边，多是一个完全图n*(n-1) 条边

编辑于 2020-06-05 22:15:25 回复(0)

清歌幻愉

至少n条边，最多n(n-1)

发表于 2019-06-12 16:09:19 回复(0)

我是俊生啊

n个节点的强联通图至少要n条边

发表于 2017-06-20 10:45:14 回复(0)

wanlanwalan

有 n 个顶点的强连通图最多有 n （ n-1 ）条边，最少有 n 条边。

解释如下：

强连通图（ Strongly Connected Graph ）是指一个有向图（ Directed Graph ）中任意两点 v1 、 v2 间存在 v1 到 v2 的路径（ path ）及 v2 到 v1 的路径的图。

最多的情况：

即 n 个顶点中两两相连，若不计方向， n 个点两两相连有 n （ n-1 ） /2 条边，而由于强连通图是有向图，故每条边有两个方向， n （ n-1 ） /2 × 2=n （ n-1 ），故有 n 个顶点的强连通图最多有 n （ n-1 ）条边。

最少的情况：

即 n 个顶点围成一个圈，且圈上各边方向一致，即均为顺时针或者逆时针，此时有 n 条边。

发表于 2017-04-07 09:58:43 回复(0)

倒悬的橙子

强连通图：如果对于每一对顶点Vi和Vj，从Vi到Vj和Vj到Vi都有路径，则称该图为强连通图。

在能够成最小生成树的情况下，在最终结点连一条线到初始结点，，这种情况是最好的。也是需要的边树最少的。

发表于 2016-12-26 09:43:23 回复(0)

细雨湿身

强连通图必须从任何一点出发都可以回到原处，每个节点至少要一条出路(单节点除外)至少有n条边，正好可以组成一个环

发表于 2016-10-01 09:38:52 回复(0)

珠珠~

发表于 2016-05-26 21:07:44 回复(0)

huixieqingchun

强连通图必须要从任何一个结点出发可以回到原处。

发表于 2016-05-08 13:35:55 回复(0)

gdhvevedhd

没注意题目…是有向图

发表于 2016-04-21 20:54:33 回复(0)

提交观点

问题信息

C++工程师运维工程师美团前端工程师算法工程师图 PHP工程师 2016 Java工程师

来自：美团2016研发工程师...

难度：

17条回答 566收藏 20950浏览

具有 7 个顶点的有向图至少应有多少条边才可能成为一个强连通

问题信息

热门推荐

相关试题