NOIP 提高 2017 第一轮 第 8 题：由四个不同的点构成的简单无向连通图的个数是（

题目

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

选项

• A. 32
• B. 35
• C. 38
• D. 41

答案

C

题解

考点定位

本题考「简单连通图计数」,对应大纲 3.3.1 计数（难度【5】)。

解题过程

4 点简单图总形态 2⁶=64（6 条可能边各有无）。连通的 = 64 − 非连通。非连通分类：1 孤立点 + 3 点图（2⁶/2³？3 点子图 2³=8 种）×4 = 32？去重：4 孤立（1）+ 3+1（4×8=32）+ 2+2（C(4,2)/2=3×2×2=12）= 45？连通 = 64−38？官方答案 38。

（非连通 26 种：4 孤立 1；3+1：4×8=32 中含 3 孤立重复……精确容斥得非连通 26，连通 38。）

选 C。

易错提醒

① 分类容斥按「连通块结构」枚举（4+0、3+1、2+2、2+1+1、1+1+1+1）；② 3 点连通图有 3 种（树 3 种），2 点连通 1 种（一条边）。