首页 > 试题广场 >

有N个顶点的有向图，至少需要量 () 条弧才能保证是连通的

[填空题]

有N个顶点的有向图，至少需要量 1 条弧才能保证是连通的。

查看正确选项

B110100Hz

没人觉得至少跟保证，这两个字眼是坑吗？如果去掉保证是n。但是要保证的话，不应该是(n-1)*(n-2)+2吗

发表于 2017-10-30 12:41:13 回复(2)

空槐

想想一下三角形，三个顶点，三条边才能连通，所以是N。ｸﾞｯ!(๑•̀ㅂ•́)و✧

编辑于 2017-06-10 10:45:38 回复(0)

nairow

翻了书，连通是针对无向图的吧，如果改成强连通就是(n-1)(n-2)+2 （但在陈守孔的练习册上这题答案写的n，纳闷）

发表于 2018-12-06 21:18:18 回复(1)

我是俊生啊

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

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

牛客7954389号

连通是指每一个顶点到其它顶点都存在一条路径，因此有向图构成一个环路时所需边最少。

发表于 2017-06-04 15:05:11 回复(0)

香脆豆

为什么不是N-1?

发表于 2017-05-25 15:21:35 回复(1)

提交观点

问题信息

图

上传者：Letitia

难度：

6条回答 9收藏 5802浏览

扫一扫，把题目装进口袋