有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条边。
如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。强连通图具有如下定理：一个有向图G是强连通的，当且仅当G中有一个回路，它至少包含每个节点一次。
扩展资料：
如果G中有一个回路，它至少包含每个节点一次，则G中任两个节点都是互相可达的，故G是强连通图。
如果有向图是强连通的，则任两个节点都是相互可达。故必可做一回路经过图中所有各点。若不然则必有一回路不包含某一结点v，并且v与回路上的个节点就不是相互可达，与强连通条件矛盾
对于无向图则比较简单，只需要从某一个顶点出发，使用BFS或DFS搜索，如果可以遍历到所有的顶点，则给定的图是连通的。但这种方法对有向图并不适用，例如 ： 1 -> 2 -> 3 -> 4，并不是强连通图。
参考资料来源：百度百科——强连通图
温馨提示：答案为网友推荐，仅供参考
相似回答