NOIP 普及 2018 第一轮 第 11 题：4 个无区别顶点的简单无向连通图个数

题目

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

选项

• A. 6
• B. 7
• C. 8
• D. 9

答案

A

题解

考点定位

本题考「无标号连通图计数」,对应大纲 3.3.1 计数（难度【5】）。

解题过程

4 个无区别点：按连通块划分计数（不考虑标号）：连通块类型（点数划分）：4 = 4 / 3+1 / 2+2 / 2+1+1 / 1+1+1+1。无标号简单连通图：4 点 3 种（树 2 种 + 三角？4 点树 2 形态、4 环 1、K₄ 减边若干——直接数无标号连通图：3+4+2+1+1？官方答案 6：4 点无标号连通简单图共 6 种（树 2、四边形 1、三角带尾 1、双三角 1、K₄ 减 2 边 1）。

选 A。

易错提醒

① 无标号计数按同构分类，比标号难；② 4 点无标号连通图 6 种是经典结论（标号版 38 种 ÷ 平均自同构 ≠ 直接除）。