Question

n个顶点的强连通图的边数至少有n个，那n个连通图的边数至少有n-1个，为什么

Answer 1

因为有n个定点的连通图的生成树有n-1条边，少于它，则图非连通了。

1、强连通图，指有向图中，任意两点之间都有路径。则最少情况是这N个点排成环。

2、连通图，是无向图中，任意两点间有路径，只需要这N点排成一条线然后相邻的连接起来。

定理及其证明

定理：一个有向图是强连通的，当且仅当G中有一个回路，它至少包含每个节点一次。

（1）充分性：如果G中有一个回路，它至少包含每个节点一次，则G中任两个节点都是互相可达的，故G是强连通图。

（2）必要性：如果有向图是强连通的，则任两个节点都是相互可达。故必可做一回路经过图中所有各点。若不然则必有一回路不包含某一结点v，并且v与回路上的个节点就不是相互可达，与强连通条件矛盾。

Answer 2

1、强连通图，指有向图中，任意两点之间都有路径。则最少情况是这N个点排成环。
2、连通图，是无向图中，任意两点间有路径，只需要这N点排成一条线然后相邻的连接起来。

Answer 3

因为有n个定点的连通图的生成树有n-1条边，少于它，则图非连通了