N个顶点的有向强连通图最少有n条边。
强连通图必须从任何一点出发都可以回到原处,每个节点至少要一条出路。
所以至少有n条边,正好可以组成一个环。
强连通图是指在有向图G中，如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。
一、有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条；
参考资料来源：百度百科-强连通图
至少有n条边,正好可以组成一个环。本回答被提问者采纳