n个顶点的强连通图的边数至少有______

Question

如题所述

Answer 1

n个顶点的强连通图的边数至少有N条。

对于1个顶点的强连通图 至少有一个边，假设 n个顶点的强连通图 至少有n个边，则如果新加一个顶点 至少要增加一边。

强连通图（Strongly Connected Graph）是指在有向图G中，如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。

相关信息：

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

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

Answer 2

对于1个顶点的强连通图
至少有一个边
假设
n个顶点的强连通图
至少有n个边
则如果新加一个顶点
至少要增加一边