NOIP 提高组初赛 · NOIP 2017 提高组初赛试题 第 8 题

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

这道题考的是组合计数里最经典的‘总数减不连通’。拿到四个点，先别急着数连通图，脑子里要立刻浮现出完全图的所有边都可选可不选，总数是2的6次方。然后关键一步：不连通图怎么分类？按‘最小的那个连通块里有几个点’来分，从1个点孤立开始，一直分到3个点孤立，这样就不会漏也不会重。最后用总数减去这些不连通的情况，剩下的就是答案。

学生最容易犯两个错：一是直接背结论38，万一记错就全错了；二是分类时乱套，比如只考虑‘一个点孤立’的情况，算出4×8=32，然后觉得剩下的4个就是连通图，忘了还有‘两个点孤立、剩下两个点成边’或者‘三个点孤立、剩下一个点’这些情形。另外，算‘一个点孤立’时容易把剩下三个点的子图数算成8种，却忘了四个点里选哪个点孤立有4种选法，或者在去重时把‘两个点孤立’的情况重复扣除了。

考点与概念：简单无向连通图计数

四个不同的点，任意两点之间连或不连，每条边都有2种选择。一共有C(4,2)=6条可能的边，所以简单无向图总数是2^6=64种。题目问的是其中‘连通’的有多少种。

命题人怎么挖坑

这道题的陷阱在于‘不连通图’的分类。如果学生只想到‘有一个点孤立’，就会算出4×8=32种，然后天真地以为64-32=32就是答案，或者再补上‘两个点孤立’的4种，得到36，离正确答案38还差2种。为什么差？因为还有‘三个点孤立’的情形：选哪三个点孤立有C(4,3)=4种，剩下一个点自己当然连通，所以也是4种。把这三类（1孤立、2孤立、3孤立）加起来才是完整的不连通图数量。