Question

设无向图 G 有n 个顶点和e 条边，每个顶点Vi 的度为di（1<=i<=n〉，则e= ?

Answer 1

e=sum(di)/2。

一条边贡献2度；

所以是 e=2m。

无向图G=<V,E>,其中：

1.V是非空集合，称为顶点集。

2.E是V中元素构成的无序二元组的集合。

扩展资料

若一个图中每条边都是无方向的，则称为无向图。

（1）无向边的表示

无向图中的边均是顶点的无序对，无序对通常用圆括号表示。

【例】无序对(vi，vj)和(vj，vi)表示同一条边。

（2）若G是无向图，则0≤e≤n(n-1)/2

恰有n(n-1)/2条边的无向图称无向完全图(Undirected Complete Graph)

Answer 2

假设G中每个顶点的度数最大等于2
边数=2n/2=n<n+1
与题设矛盾
所以G中至少有一个顶点的度数大于或等于3

边数=2n/2=n<n+1
前面的2是度数。以条边2个顶点，用度数×顶点数/2=变数，好像书上有这公式的

Answer 3

e=sum(di)/2