首页 > 试题广场 > 若一个具有N个结点,M条边的无向图构成一个森林,(N>
[单选题]
若一个具有N个结点,M条边的无向图构成一个森林,(N>M), 则该森林必有(  )棵树。

  • M
  • N
  • N-M
  • 12
推荐
C
设该森林共有m棵树,每棵树有ni(1≤i≤m)个节点,依据树的性质有
N=n1+n2+…+nm
M=(n1-1)+(n2-1)+…+(nm-1)
上面两式相减得
N-M=1+1+…+1=m
而m就是树的个数,所以该森林共有N-M棵树。
编辑于 2019-12-10 14:21:18 回复(0)
C
利用类比举例法:
假设有三个(N=3)顶点,如果有两条边(M=2)的无向图构成森林的话。
  • 一个顶点作为根节点,另外两个作为子结点,构成一棵树(N-M=1)

带入选项中,可以得出C正确。

发表于 2019-12-09 19:35:50 回复(0)