首页 > 试题广场 >

设某强连通有向图中有 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)
强连通图  --- 有向图
连通图、连通分量 --- 无向图
发表于 2020-06-19 15:40:57 回复(0)
 强连通图 :如果对于每一对vi、vj,vi≠vj,从vi到vj和从vj到vi都存在路径,区别于完全图:任意两点间都可直达,强连通图,可间接到达所以N 个结点的强连通图,至少有 N条边
发表于 2020-06-26 08:33:34 回复(0)
答案对吗???有谁可以给解释下
发表于 2017-06-14 08:40:20 回复(1)
强连通有向图中 至少有 n 条边。至多有 n(n-1) 条边。
连通无向图中 至少有 n-1 条边。至多有 n(n-1)/2 条边。
发表于 2023-04-18 17:36:47 回复(0)
最少n成环,最多完全图
发表于 2019-09-30 15:18:44 回复(0)
发表于 2023-11-22 16:11:09 回复(0)

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

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

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

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

发表于 2023-11-16 13:25:06 回复(0)
有向图中,区分强连通图和完全图需要的最少边数。
发表于 2022-11-12 16:43:49 回复(0)
大于n-1条边,则必有环
发表于 2022-07-11 21:43:15 回复(0)
他说至少
发表于 2020-03-18 20:43:13 回复(0)
1:强连通图的定义:
在有向图G中,如果对于每一对vi、vj,vi≠vj,从vi到vj和从vj到vi都存在路径,则称G是强连通图
发表于 2019-09-02 11:10:41 回复(0)