SCP 模拟 · SCP 2021 第一轮（初赛）模拟 第 13 题

有 $4$ 个结点和 $4$ 条边的有标号简单无向图的数量是

别被'图'字骗了，这题考的是'图论'里最基础的'计数'——用容斥原理算'有边'的图，等于'所有图'减去'无边'的图。

最容易栽跟头的地方是：把'有标号'和'无标号'搞混，以为要除以4!；或者直接用C(4,2)去算边数，忘了图里边可以重复选（比如4条边可以是4条不同的边，也可以是同一条边出现多次）；还有人会把'简单图'的定义记错，以为不能有重边，其实'简单图'只是不能有自环，重边是允许的。

这道题考查的是组合计数里的'容斥原理'以及'图论'里'有标号简单无向图'的定义。命题人挖坑的地方很隐蔽：题目说'有4个结点4条边'，但没说边是否必须不同，也没说结点是否必须不同，所以学生很容易误以为要算'恰好4条不同边'的图，或者误以为要算'恰好4条边且结点互不相同'的图。

思考心法：拿到题先想'总共有多少种图'，再想'有多少种图是'没有边'的'，然后用'总数减去'无边的'就是'有边的'。具体怎么算：

1. 总图数：4个结点，每对结点之间最多有一条边（简单图定义），一共有C(4,2)=6对结点，每对结点要么有边要么没边，所以总图数是2^6=64。 2. 无边图数：4个结点，没有边，只有一种图（所有对都没有边），所以无边图数是1。 3. 有边图数：64-1=63。

等等，这不对啊，题目说'有4条边'，不是'有边'。我再仔细读题：'有4个结点和4条边的有标号简单无向图的数量'。哦，原来题目是说'有4条边'，不是'有边'。那我再算：

1. 总图数：4个结点，每对结点之间最多有一条边，一共有C(4,2)=6对结点，每对结点要么有边要么没边，所以总图数是2^6=64。 2. 有4条边的图数：6对结点中选4对，C(6,4)=15。

所以答案是15，选A。

避坑指南：这里的关键是'简单图'的定义——不能有自环，但可以有重边。如果题目说'多重图'，那就要考虑重边，但这里明确说'简单图'，所以每对结点最多一条边。另外，'有标号'意味着结点是不同的，所以C(4,2)=6对结点是固定的，不需要除以4!。

考频与趋势：从历年真题看，'容斥原理'和'组合计数'是高频考点，尤其是'有边'和'无边'的计数问题。这道题虽然简单，但考察了学生对'简单图'定义的理解和'容斥原理'的应用。未来可能会出更复杂的'有边'和'无边'的计数问题，比如'有至少k条边'或'有恰好k条边'的图的数量。

预测：基于历年真题和命题趋势，未来可能会出更复杂的'容斥原理'和'组合计数'问题，比如'有至少k条边'或'有恰好k条边'的图的数量。这道题虽然简单，但考察了学生对'简单图'定义的理解和'容斥原理'的应用，未来可能会出更复杂的'容斥原理'和'组合计数'问题。