首页 > 试题广场 >

由四个不同的点构成的简单无向连通图的个数是（ ）

[单选题]
由四个不同的点构成的简单无向连通图的个数是（ ） 
  • 32
  • 35
  • 38
  • 41
查看答案及解析
添加回答
寒冰永生头像 寒冰永生
对于三条边用$cayley$ 公式答案为$16$

由于$K_3$只有3条边，剩下的必然使整张图联通，答案为$C_6^4+C_6^5+C_6^6=15+6+1=22$

总共的答案为 $16+22=38$

懒得改latex了，自己复制进typora看吧（
编辑于 2020-10-09 17:50:17 回复(0)
钰lily头像 钰lily
4个不同点构成简单无向连通图，最多有4*（4-1）/2=6 条边（强联通图），最少有4-1=3 条边（树），但注意，不是所有的任选3条边都满足条件，有一种情况是三个点形成一个三角形而孤立一个点，这种情况共有4种
所以 ans=C（6，3）-4+C（6，4）+C（6，5）+C（6，6）=38
发表于 2018-11-11 15:20:14 回复(1)
提交观点

问题信息

提高 C++ Pascal 图论
来自：NOIP2017初赛提高组
上传者：牛客309901号
难度：
2条回答 15474浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号