若一个具有n个顶点，e条边的无向图是一个森林，则该森林中必有[$##$]棵树。
如果某棵树中有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
发表于 2022-04-28 10:53:50
回复(0)
问题信息
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
