一个有N个顶点, N条边的连通图是多少?

Question

如题所述

Answer 1

N个顶点的有向强连通图最少有n条边。

强连通图必须从任何一点出发都可以回到原处,每个节点至少要一条出路。

所以至少有n条边,正好可以组成一个环。

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