已知n个顶点，m条边的一个无向图G是k(k≥2)棵树组成 的森林，证明：m=n-k。
证： 设k棵树的阶数分别为：n1,n2, ..., nk, 则n1+n2+ ...+ nk=n 每棵树的边数应该为：n1-1,n2-1, ..., nk-1, 所以G的边数m= n1-1+n2-1+ ...+ nk-1,=n-k
举一反三
内容
- 0
6.5 一个具有n个顶点、k条边的无向图是一个森林(n>k)，则该森林中必有（ ）棵树。 A: k B: n(n-1 C: n-k D: 1
- 1
若一个具有N个顶点，K条边的无向图是一个森林(N>K)，则该森林中必有（）棵树。
- 2
若一森林有n个顶点、k个分支(n>k)，该森林必有（ ）棵树。 A: k B: n C: n-k D: 1
- 3
若一个具有n个结点k条边的无向图是一个森林（n>k），则该森林必有（ ）棵树。
- 4
一个具有n个顶点、k条边的无向图是一个森林（n>k），则该森林中必有（） A: k B: n C: n-k D: 1