数据结构证明：若一个具有N个结点K条边的非连通无向图是森林,则该森林中必有N-K棵树

Question

数据结构证明：若一个具有N个结点K条边的非连通无向图是森林,则该森林中必有N-K棵树

Answer 1

如果某棵树中有N0个结点,K0条边,则N0 = k0 + 1
设森林中有m棵树,其结点数分别为n1,n2,n3,.,nm
相应地,各棵树的边数分别为k1,k2,k3,...km
显然：n1 = k1 + 1,n2 = k2 + 1,.,nm = km + 1 (1)
按照题设：
n1 + n2 + n3 +.+ nm = N (2)
k1 + k2 + k3 +.+ km = K (3)
将(1) 代入(2) 得：
(k1 + 1) + (k2 + 1) + (k3 + 1) + .+ (km + 1) = N
即：
k1 + k2 + k3 + ...+ km + 1 + 1 +.+ 1 = N
按照(2)：
K+ m= N
于是m = N - K