首页 > 试题广场 > 若一个具有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)
假设最初的图只有N个结点,即有N棵树,每增加一条边,则少一棵树,若有M条边,则剩N-M棵树
发表于 2020-05-02 22:12:05 回复(0)
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棵树。
发表于 2020-07-01 09:35:59 回复(0)
根据一棵树的边数+1=结点数。
可以知道,每多一棵树,结点数就少一个。
即,
一棵树时,边数 = 结点数-1
两棵树时,边数 = 结点数-2
….
n棵树时,边数 = 结点数-n
发表于 2020-03-07 21:35:34 回复(0)