NOIP 普及组初赛 · NOIP 2018 普及组初赛试题 第 11 题

由四个没有区别的点构成的简单无向连通图的个数是（ ）。

四个无标号点要连成连通简单图，先想‘最少几条边能连通？’树最少3条，再多就是4、5、6条。按边数一层层画，边数相同就比形状是否同构，同构的只算一种，这样就能把总数数清楚。

最容易把‘无区别的点’当成有编号的点去算，那样树就有16种，总数会跑到9种，直接选错D。其次会忽略‘简单图’允许有环，把四边形或三角形加尾巴漏掉，导致少算。还有人会重复画同构的图，比如把链形和星形画反了当成两种，或者把钻石形和完全图混在一起，这些都会让答案偏大。

这道题考的是图的基本概念和无标号图的计数，属于组合数学里‘同构类计数’的典型应用。命题人喜欢在这里挖坑：一是把‘无区别的点’误读成‘有编号的点’，二是把‘简单图’误解为‘不能有环’，三是画图时重复或遗漏同构的形态。

拿到题先想：四个点要连通，最少需要几条边？答案是3条，这就是树。树里没有环，形状只有两种——一条长链（○—○—○—○）和一个中心连着三个叶子的星形（⭐）。这是2种。

再多一条边，就是4条边。这时候必然出现一个环。四个点围成一个圈（四边形）是一种；还有一种是三个点连成三角形，第四个点挂在三角形的一个顶点上（像个带尾巴的三角）。这两种形状不同构，所以是2种。

5条边呢？四个点最多6条边（完全图K₄）。5条边就是K₄去掉一条边，形状唯一，就是两个三角形共用一条边，俗称‘钻石形’。这是1种。

6条边就是K₄本身，每个点都和其他三个点相连，也是唯一的一种。

把边数相同的图按形状分类：3边2种、4边2种、5边1种、6边1种，加起来正好6种。对应选项A。

为什么不能选D（9种）？那是把点当成有编号的，用凯莱公式算树有16种，再加上各种环的结构，总数会跑到9。题目强调‘没有区别的点’，所以同构的图必须合并。

为什么不是B或C？很多人会漏掉‘带尾巴的三角形’这种4边图，或者把钻石形和K₄当成两种不同的5边/6边图，导致多算。其实只要严格按边数分类、再比形状是否同构，就不会出错。

这类题在NOIP普及组初赛里考频不高，但概念清晰，属于‘会就能拿分’的题型。历年看，图的基本概念在2018年考了1题，近年GESP八级、七级也常出现类似计数题，说明命题人依然重视对‘无标号’‘同构’这些细节的考察。预测未来若再出图计数，大概率还是限定点数（3~5点）让考生枚举，防止用公式硬算，继续考‘读清条件、画图比对’的细心程度。