若一个具有n个顶点,k条边的无向图是一个森林,则森林中必有多少棵树
2个回答
展开全部
如果某棵树中有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
按照(3):
K+ m= N
于是m = N - K
设森林中有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
按照(3):
K+ m= N
于是m = N - K
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询