Question

无向图边数和顶点关系是什么？

Answer 1

无向图边数和顶点关系是：

1、如果有n个顶点，边数＜n-1，则此图非连通图。

2、 全部顶点的度的和 = 边数的2倍。

3、有n个顶点，并且有 ＞n-1条边，则图一定有环。

4、边数取值范围从0到n(n-1)/2。

5、边数为n(n-1)/2时，叫完全图。

6、顶点数为n，则它的生成树含有n-1条边。

7、连通无向图最少边数 = (n-1)(n-2)/2+1 n为顶点数。

8、非连通无向图的边数 = n(n-1)/2+1。

9、 无向连通图边数至少为 = n-1。

10、边数的取值范围为 0~n(n-1)，强连通：v->w有双向路径，强连通图：任何一对顶点都是强连通的。

11、强连通最少边数。