有n个顶点的强连通图最多有多少条边,最少有多少条边

发布网友 发布时间：2022-06-05 11:09

我来回答

共5个回答

热心网友 时间：2023-11-18 05:16

有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，并不是强连通图。

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

热心网友 时间：2023-11-18 05:16

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

解释如下：

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

举例：

如下图ABCD四个点构成强连通图

边数最多有4×3=12条，图如下：

边数最少有4条，图如下：

热心网友 时间：2023-11-18 05:17

热心网友 时间：2023-11-18 05:17

热心网友 时间：2023-11-18 05:18