NOIP 提高组初赛 · NOIP 2010 提高组初赛试题 第 22 题

无向图 $G$ 有 $7$ 个顶点，若不存在由奇数条边构成的简单回路，则它至多有____条边。

这题核心就是识别'无奇环'等价于'二分图'，然后直接套用 Turán 定理的结论公式，算出完全二分图的最大边数即可。

很多学生看到'无奇数条边构成的简单回路'容易愣住，不知道这和'二分图'是一回事，或者误以为只要没有奇数条边的回路就行，忽略了二分图的本质是顶点能分成两个集合，所有边都在集合之间。还有人会下意识想构造一个接近完全图的图，比如 K7 去掉几条边，结果发现只要有一个奇环就违规了。最容易错的是把公式记成 n(n-1)/2 或者随便凑个数，忘了 Turán 定理里那个除以 4 取整的魔法，导致算出 14 或 15 这种明显不对的答案。

考点与概念

题目给出的条件是：无向图 $G$ 有 $7$ 个顶点，且不存在由奇数条边构成的简单回路。这个条件在图论里有一个非常经典的等价表述——这样的图一定是二分图。

什么是二分图？简单来说，就是把图中的所有顶点分成两个不相交的集合 $V_1$ 和 $V_2$，使得图中所有的边都连接 $V_1$ 中的一个点和 $V_2$ 中的一个点，而同一集合内的点之间没有边相连。这种结构天然地保证了图中不可能存在奇数长度的环。因为如果你沿着环走，每跨一条边就从一个集合跳到另一个集合，要走一圈回到起点，必须跳偶数次，所以环的长度必然是偶数。

反之，如果一个图里没有奇环，那它一定可以划分为两个这样的集合。所以，题目的条件其实就是告诉我们要找的是：在 7 个顶点的二分图中，最多能有多少条边？

命题视角：为什么考这个？

命题人特别喜欢用这种'等价转化'来挖坑。表面上看是在限制边的数量，实际上是在考察你对图结构本质的理解。如果只盯着'边数'，学生可能会去尝试构造各种复杂的图，比如 K7 去掉几条边，结果发现只要有一个奇环就违规了。而一旦意识到'无奇环=二分图'，问题瞬间就简化成了：怎么把 7 个点分成两部分，让两部分之间的边数最多？

这其实是一个经典的极值图论问题，结论由 Turán 定理给出：对于 $n$ 个顶点的图，若不含 $k+1$ 个顶点的完全子图，则边数最多为 $rac{k-1}{k} imes rac{n^2}{2}$。在二分图的情况下，$k=2$（不含 3 个顶点的完全子图，也就是不含奇环），公式就简化成了 $rac{n^2}{4}$。

思考心法：拿到题先想什么？

1. 翻译条件：'无奇数条边的简单回路' $ ightarrow$ '二分图'。 2. 明确目标：7 个顶点的二分图，边数最多是多少？ 3. 构造思路：为了让边数最多，应该让两个集合的大小尽可能接近。因为边都在两个集合之间，集合越大，能连的边就越多。所以要把 7 个点分成 $3$ 和 $4$ 两部分（$3+4=7$，且差值最小）。 4. 计算：完全二分图 $K_{3,4}$ 的边数就是 $3 imes 4 = 12$。 5. 验证：有没有可能更多？假设分成 $2$ 和 $5$，边数是 $10$；分成 $1$ 和 $6$，边数是 $6$。显然 $3$ 和 $4$ 是最优的。

避坑提醒

• 别记错公式：很多人会误记成 $rac{n(n-1)}{2}$（这是完全图的边数），或者 $rac{n^2}{2}$，这些都是错的。二分图的最大边数是 $rac{n^2}{4}$。
• 别忽略整数部分：如果 $n$ 是奇数，$rac{n^2}{4}$ 不是整数，这时候要向下取整。比如 $n=7$，$rac{49}{4}=12.25$，取整就是 $12$。
• 别被'简单回路'这个词绕晕：其实这里的'简单回路'就是指'环'，题目只是用更正式的术语来描述。关键是抓住'奇数条边'这个特征。

考频与趋势

图的基本概念是信息学竞赛的基石，题库共考过 281 题，覆盖 11 个考试级别（2007-2026）。从逐年分布看，2023 年考了 36 题，2024 年考了 61 题，2025 年考了 58 题，2026 年考了 71 题，呈现出明显的上升趋势，说明这类基础概念题在近年越来越受重视。

在分赛事维度，GESP 八级考了 85 题，GESP 七级考了 85 题，CSP 提高级考了 13 题，NOIP 提高组初赛考了 10 题。这道题属于 NOIP 提高组初赛的典型题型，难度适中，但要求对概念有深刻理解。

预测

基于近年考频持续攀升的趋势，尤其是 2024-2026 年每年都在 50-70 题之间，这类基础概念题在未来几年仍将是高频考点。命题人可能会继续用'等价转化'的方式出题，比如'无奇环'、'无偶环'、'连通分量'等，考察学生对图结构本质的把握。因此，熟练掌握 Turán 定理、二分图性质、欧拉图等基础理论，将是应对这类题目的关键。