无向连通图至少有n-1条边，为什么说4个顶点的连通图有四条边，n-1是怎么来的呢

更新时间2021-06-14 06:10:52

无向连通图至少有n-1条边，为什么说4个顶点的连通图有四条边，n-1是怎么来的呢

一、有n个顶点的强连通图最多有n（n-1）条边，最少有n条边。 首先，有向连通的一个必要条件是图的无向底图连通，这意味着E >= n-1。 其次，证明E > n-1。因当E=n-1时，无向底图为树，任取两顶点s，t，从s到t有且只有一条无向路径，若有向路径s->t连通，则有向路径t->s必不存在。得证： 再次，证明E可以=n。设n个顶点v1，v2，...vn,顺次连接有向边v1v2，v2v3...vn-1vn，vnv1,这个环是有向连通的。 因此最少有n条边。 二、最多的情况：即n个顶点中两两相连，若不计方向，n个点两两相连有n（n-1）/2条边，而由于强连通图是有向图，故每条边有两个方向，n（n-1）/2×2=n（n-1），故有n个顶点的强连通图最多有n（n-1）条边。