Question

一个有n个顶点的无向连通图，最少有几条边

Answer 1

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

首先，有向连通的一个必要条件是图的无向底图连通，这意味着E >= n-1。

其次，证明E > n-1。因当E=n-1时，无向底图为树，任取两顶点s，t，从s到t有且只有一条无向路径，若有向路径s->t连通，则有向路径t->s必不存在。得证：

再次，证明E可以=n。设n个顶点v1，v2，...vn,顺次连接有向边v1v2，v2v3...vn-1vn，vnv1,这个环是有向连通的。

因此最少有n条边。

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

扩展资料：

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

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

（2）最少的情况：即n个顶点围成一个圈，且圈上各边方向一致，即均为顺时针或者逆时针，此时有n条边。

下面举例说明：如图1所示，设ABCD四个点构成强连通图，则：

（1）边数最多有4×3=12条；

（2）边数最少有4条；

参考资料来源：百度百科-强连通图

Answer 2

一个有n个顶点的无向连通图最多有n（n-1）/2条边，最少有n-1条边。

有向图的强连通图才是最少n条边。看到两个回答都是错的。

Answer 3

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

强连通图是指一个有向图中任意两点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条边。

1、充分性：如果G中有一个回路，它至少包含每个节点一次，则G中任两个节点都是互相可达的，故G是强连通图。

2、必要性：如果有向图是强连通的，则任两个节点都是相互可达。故必可做一回路经过图中所有各点。若不然则必有一回路不包含某一结点v，并且v与回路上的个节点就不是相互可达，与强连通条件矛盾。

Answer 4

设边数为E
首先,有向连通的一个必要条件是图的无向底图连通,这意味着E
>=
n-1
其次,证明E
>
n-1.因当E=n-1时,无向底图为树,任取两顶点s,t,从s到t有且只有一条无向路径,若有向路径s->t连通,则有向路径t->s必不存在.得证
再次,证明E可以=n.设n个顶点v1,v2,...vn,顺次连接有向边v1v2,v2v3...vn-1vn,vnv1,这个环是有向连通的.
因此最少有n条边.