结构推理
设无向图G是由k(k≥2)棵树组成的森林，已知G中有n个结点，m条边．试证明．m=n-k．
【正确答案】
证明 设G的k个连通分枝为G
1
，G
2
，…，G
k
，每个G
i
有n
i
个结点m
i
，条边，i=1，2，…，k．由于G，都是树，有m
i
=n
i
-1，i=1，2，…，k．
故 m=∑
i=1
k
m
i
-∑
i=1
k
(n
1
-1)=n-k
【答案解析】
提交答案
关闭