n个顶点n条边的无向图一定连通的吗

Question

如题所述

Answer 1

n个顶点n条边的无向图不一定连指正通。

1、无向连通图成立最少边数：考虑一条链，n个顶点至少需要n-1条边来保证连通。

2、有向连通图成立最少边数：考虑一个大环，n个顶点至少需要n条边来构成一个大环，使得任意两点都是互相可达的。

3、无向图总是成立最少边数：我们可以先画出饥芹顶点较少时的情况来观察一下，一个较好的办法是，每次增加烂逗毕独立顶点后，新增边尽可能使新图不连通。

画了几种情况后就会发现，n顶点的临界条件情况总是可以视作一个（n-1）顶点的完全图和1个顶点用一条线连起来的图。 而n顶点完全图的边数为1~（n-1）求和，即（n-1）n/2。 那么n-1顶点完全图边数再加上与这个独立顶点构成连通的边，最终结果就是（n-2）（n-1）/2+1。

4、有向图总是成立最少边数：按照无向图的思路，也就是一个（n-1）顶点完全连通图与一个孤立顶点联通，但是仔细思考这里有一个坑：有向图的互通是需要这个孤立顶点与完全图有一来一回两条边才能强连通的，而我们如果只给出两条边，万一这两条边都是去边或者回边那就不构成连通了。

无向图的边

1、无向图的最多边是无向完全图：包含n（n-1）/2条边。因为一条边关联两个结点，有向完全图的才有n（n-1）条弧。而无向图变联通至少边数：n-1。有向图变连通图至少需要边数：n。

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