主题
《君药：组合构造 | L0-L7题根生长式闭环教案 · 图论初步与组合论证》
L0-L7 生长脉络表
| 层次 | 核心知识 | 思维跃迁 |
|---|---|---|
| L0 | 图的基本概念：顶点、边、度数、简单图、完全图 | 感性认识 → 建立“点线关系”的本源认知 |
| L1 | 握手定理、子图、补图、同构 | 规律发现 → 从具体图到图的定量性质 |
| L2 | 树的基本性质：无圈连通图、生成树、树叶数 | 结构分析 → 认识最简连通图的特征 |
| L3 | 欧拉图与欧拉回路、一笔画问题 | 遍历思想 → 沿着边不重复走遍所有边 |
| L4 | 哈密顿图与哈密顿回路、必要与充分条件（狄拉克定理） | 遍历升级 → 遍历所有顶点 |
| L5 | 极值图论：图兰定理（不含完全子图的最大边数） | 极值思想 → 给定约束下的最值结构 |
| L6 | 拉姆齐数 R(s,t) 的定义与基本性质（R(3,3)=6 的推广） | 必然性 → 染色中必然出现单色结构 |
| L7 | IMO 级图论综合：图论与组合、数论、几何的融合压轴 | 命题人视角 → 回归本源，跨模块创新 |
L0 题根本源层
- 层级定位：小学高年级～初一，通过生活中的关系网络引入图的概念。
- 核心生长点：用点和线表示对象及它们之间的关系，建立图论的第一印象。
- 核心知识点：
- 图的基本要素：顶点（点）、边（线）。
- 简单图：没有自环，没有重边。
- 完全图：每两个顶点之间都有边。
- 顶点的度数：与它相连的边的条数。
【备课专属】
- 考察本质：图是描述离散结构的语言，L0 就是认识这个语言的基本符号。
- 难度分析：零计算，重在理解点、边、度数的概念。
- 命题意图：从生活实例（朋友关系、交通网络）平滑进入图的世界。
- 葛军风格点拨：图就是一堆点，有些点之间有线连着。L0 就是先认识这些点和线，就像认识新朋友。
【锚定例题 L0-1】
下图中有几个顶点？几条边？每个顶点的度数是多少？（画一个简单的三角形加一个点与一边相连）
【锚定例题 L0-2】
画出 4 个顶点的完全图，并计算每个顶点的度数。
【锚定例题 L0-3】
一个图有 5 个顶点，其中两个顶点度数为 3，两个顶点度数为 2，一个顶点度数为 1。问这个图共有多少条边？（握手定理初步）
L1 入门特例层
- 层级定位：初一～初二，学习握手定理及基本运算，认识子图、补图、同构的概念。
- 核心生长点：从单个图的性质到图之间的关系。
- 核心知识点：
- 握手定理：所有顶点度数之和等于边数的 2 倍。
- 子图：从原图中取一部分顶点和边。
- 补图：顶点不变，补上所有缺失的边。
- 图的同构：顶点可以重新编号使得边的关系对应。
【备课专属】
- 考察本质：握手定理是图论中第一个定量结果，同构是分类的基础。
- 难度分析：简单计算，但需理解“对应”的概念。
- 命题意图：让学生掌握基本的图论运算，并能判断两个图是否相同。
- 葛军风格点拨：握手定理说：所有人握手次数之和是握手次数的两倍。L1 就是算这个总次数。
【锚定例题 L1-1】
一个图有 10 个顶点，每个顶点度数都是 3，问这个图有多少条边？
【锚定例题 L1-2】
画出 4 个顶点的一条路径的补图。
【锚定例题 L1-3】
判断下图（两个 4 个顶点的图）是否同构：一个是一个正方形，另一个是一个三角形加一个孤立点？显然不是。应该给两个同构的例子，比如两个不同画法的六边形。
L2 基础框架层
- 层级定位：初二～初三，学习树的基本性质（无圈连通图），以及生成树的概念。
- 核心生长点：树是最简单的连通图，它的边数等于顶点数减 1。
- 核心知识点：
- 树的定义：无圈连通图。
- 树的性质：边数 = 顶点数 − 1；任意两点有唯一路径；叶子（度数为1的顶点）至少两个。
- 生成树：包含所有顶点的连通子图且为树。
- 最小生成树问题（思想介绍）。
【备课专属】
- 考察本质：树是图论的基石结构，许多问题最终归结为树。
- 难度分析：需要理解无圈和连通的含义。
- 命题意图：为后续遍历问题（欧拉、哈密顿）打基础。
- 葛军风格点拨：树就是没有环的连通图，像树枝一样分叉，不会绕圈。L2 就是认识这种最简单的结构。
【锚定例题 L2-1】
证明：一棵树至少有 2 个叶子（度数为 1 的顶点）。
【锚定例题 L2-2】
已知一棵树有 8 个顶点，其中 3 个顶点度数为 3，其余顶点度数为 1，问度数为 1 的顶点有几个？
【锚定例题 L2-3】
一个连通图有 10 个顶点，15 条边，它的一个生成树至少要去掉多少条边？
L3 核心工具层
- 层级定位：初三～高联一试，学习欧拉图与欧拉回路（一笔画问题），理解欧拉定理。
- 核心生长点：从实际问题“一笔画”抽象出欧拉回路存在的条件。
- 核心知识点：
- 欧拉回路：经过每条边恰好一次并回到起点；欧拉路径：经过每条边一次（不一定回到起点）。
- 欧拉定理：一个连通图有欧拉回路当且仅当所有顶点度数都是偶数；有欧拉路径当且仅当恰有两个奇度数顶点。
- 应用：哥尼斯堡七桥问题。
- 有向图的欧拉回路（简单介绍）。
【备课专属】
- 考察本质：欧拉定理给出了存在性条件的简洁刻画，是图论史上第一个定理。
- 难度分析：定理易记，证明可用归纳法。
- 命题意图：让学生掌握判定一笔画的方法，体会数学建模的威力。
- 葛军风格点拨：能不能一笔画成，就看奇点个数。0 个奇点能回来，2 个奇点能画但不回来。L3 就是学会这个判据。
【锚定例题 L3-1】
判断下列图形哪些可以一笔画成：一个五角星，一个日字格（两个正方形共边），一个十字架。
【锚定例题 L3-2】
一个连通图有 8 个顶点，其中 4 个顶点度数为奇数，问这个图是否存在欧拉路径？为什么？
【锚定例题 L3-3】
在哥尼斯堡七桥问题中，如果要使该图有欧拉回路，至少需要添加或删除多少座桥？
L4 高阶方法层
- 层级定位：高联一试～二试，学习哈密顿图与哈密顿回路，以及狄拉克定理等充分条件。
- 核心生长点：与欧拉图不同，哈密顿回路要求经过每个顶点恰好一次，条件更复杂。
- 核心知识点：
- 哈密顿回路：经过每个顶点恰好一次并回到起点；哈密顿路径：经过每个顶点一次（不一定是回路）。
- 狄拉克定理：若简单图 G 有 n ≥ 3 个顶点，且每个顶点度数 ≥ n/2，则 G 是哈密顿图。
- 其他充分条件（奥雷定理）。
- 旅行商问题简介（NP-hard）。
【备课专属】
- 考察本质：哈密顿问题是图论中的经典难题，狄拉克给出了一个简单的充分条件。
- 难度分析：理解条件，不要求证明。
- 命题意图：让学生了解图论中的另一类遍历问题，拓展视野。
- 葛军风格点拨：哈密顿回路是环游世界，每个城市只去一次。狄拉克说：如果每个城市都至少有半数以上的邻居，就一定能找到这样的环游。L4 就是学会这个判据。
【锚定例题 L4-1】
一个完全图 K₅ 是否存在哈密顿回路？有多少条不同的哈密顿回路（不计方向）？
【锚定例题 L4-2】
判断一个 6 个顶点的图，每个顶点度数至少为 3，是否一定有哈密顿回路？（狄拉克定理，n=6，n/2=3，度数 ≥3，所以是）
【锚定例题 L4-3】
构造一个 5 个顶点的图，每个顶点度数至少为 2，但没有哈密顿回路。
L5 体系基石层
- 层级定位：高联二试～CMO，学习极值图论中的图兰定理：不含完全子图 Kᵣ 的最大边数。
- 核心生长点：给定禁止子图，问最多能有多少条边。
- 核心知识点：
- 图兰定理：若一个简单图 G 有 n 个顶点且不含 Kᵣ 作为子图，则它的边数不超过 T(n,r)，其中 T(n,r) 是 r−1 部分完全图的边数。
- 完全 r−1 部图：将顶点分成 r−1 部分，每部分内无边，不同部分之间全连边。
- 等分时边数最大。
- 应用：证明某些极值问题。
【备课专属】
- 考察本质：图兰定理是极值图论的开端，揭示了无完全子图条件下的最大结构。
- 难度分析：需要理解极值构造，证明可用归纳法或双计数。
- 命题意图：让学生接触极值图论的经典结果。
- 葛军风格点拨：不让出现 K₃，边最多怎么连？就是把点分成两堆，堆内不连，堆间全连——这就是二分完全图。L5 就是学会这种“分而连之”的策略。
【锚定例题 L5-1】
一个 5 个顶点的图，不含三角形（K₃），最多有多少条边？画出这样的图。
【锚定例题 L5-2】
一个 6 个顶点的图，不含 K₄，最多有多少条边？写出最大边数的构造。
【锚定例题 L5-3】
用图兰定理证明：若一个图有 n 个顶点，边数大于 n²/4，则它必含三角形。
L6 CMO 高阶层
- 层级定位：CMO，学习拉姆齐数 R(s,t) 的定义及基本性质，证明 R(3,3)=6 并推广。
- 核心生长点：任意染色，必然出现单色完全子图。
- 核心知识点：
- 拉姆齐数 R(s,t) 的定义：最小的正整数 n 使得完全图 Kₙ 的边任意染红蓝两色，必然出现红色 K_s 或蓝色 K_t。
- R(3,3)=6 的证明。
- 拉姆齐数的基本下界（概率方法），上界（递推关系）。
- 拉姆齐定理（广义）的思想。
【备课专属】
- 考察本质：拉姆齐理论揭示了完全的随机必然导致有序结构。
- 难度分析：需要构造染色和归纳论证。
- 命题意图：让学生掌握拉姆齐数的基础，为更深入的组合论证奠基。
- 葛军风格点拨：6 个人中，必有 3 人两两认识或两两不认识——这就是 R(3,3)=6。L6 就是证明这个必然。
【锚定例题 L6-1】
证明 R(3,3) > 5，即构造一个 5 个点的图，用红蓝染色不出现单色三角形。
【锚定例题 L6-2】
证明 R(3,4) ≤ 9。（提示：用递推 R(s,t) ≤ R(s-1,t) + R(s,t-1)）
【锚定例题 L6-3】
已知 R(3,3)=6，求 R(3,4) 的一个下界。
L7 IMO 顶峰层
- 层级定位：IMO 难度，图论与组合、数论、几何的融合压轴题。
- 核心生长点：回归 L0 点线关系，将图论思想用于跨模块问题。
- 核心知识点：
- 图论与数论：用图表示同余关系，研究整数图的色数。
- 图论与几何：用图表示点集的邻接关系（如单位距离图）。
- 图论与组合设计：如正则图的存在性与构造。
- IMO 经典图论题剖析（如 2007 年第 3 题、1999 年第 2 题等）。
【备课专属】
- 考察本质：图论的语言可以描述各种离散结构，是解决复杂问题的万能工具。
- 难度分析：IMO 级，需要创造性地将问题转化为图论模型。
- 命题意图：检验学生能否用图论思想解决陌生问题。
- 葛军风格点拨：当你在 IMO 题里看到“关系”“连接”“认识”这些词，就应该想到图论。L7 就是学会把这个“关系网”画出来。
【锚定例题 L7-1】
（IMO 1999 第2题）设 n 为正整数，考虑集合 {1,2,…,n} 的一个排列 a₁,a₂,…,aₙ，定义 b_k = |{i | 1 ≤ i ≤ k, a_i ≥ k}|。证明：存在一个排列使得 b₁,b₂,…,bₙ 两两不同。（可转化为图论问题）
【锚定例题 L7-2】
（IMO 2007 第3题）在一个数学竞赛中，有些参赛者是朋友。已知若 A 是 B 的朋友，B 是 C 的朋友，则 A 也是 C 的朋友。问最多可以有多少对朋友？（这是图论中的传递关系，实际上等价于若干个团，答案易得）
【锚定例题 L7-3】
（IMO 2001 第3题改编）有 n 个点，某些点之间连了边，已知每个点的度数相同，且没有孤立点。证明：可以给每个点标上 0 或 1，使得每条边的两端数字不同（即图是二部图）的必要条件是什么？并说明。
【教师专属·命题人视角】真题反向拆解
题目（IMO 2007 第3题）在一个数学竞赛中，有些参赛者是朋友。已知若 A 是 B 的朋友，B 是 C 的朋友，则 A 也是 C 的朋友。问最多可以有多少对朋友？
反向拆解生长路径：
- L7（原题）：朋友关系是等价关系？因为已知传递性，加上通常朋友是相互的（对称），再加上自反？但题目没说自反，通常朋友关系是对称且传递，则它是等价关系（需要自反？但“是朋友”通常不自反，但可以加自反）。实际上，由对称和传递，可推出在同一个连通分支内，所有点之间都有边？因为若 A 与 B 朋友，B 与 C 朋友，则 A 与 C 朋友，所以同一连通分支内任意两点经两步可达即为朋友，而由于对称，可推出任意两点都是朋友。所以每个连通分支是一个完全图。因此朋友关系就是若干个完全图的并集。设有 k 个完全图，大小分别为 n₁,…,nₖ，总人数 n = ∑nᵢ，总朋友对数 = ∑ C(nᵢ,2)。要使这个数最大，当 k=1 时即 n 个点完全图，对数为 C(n,2)。所以最多有 C(n,2) 对朋友。
- L6：这个结论很简单，但需要理解传递性带来的结构。
- L5-L2：用图论语言，条件意味着图是若干个团的并集。
- L1-L0：从朋友关系抽象出图，利用对称和传递推出团结构。
生长逻辑提炼： 这道题将社会关系抽象为图，利用传递性推出每个连通分支都是完全图，从而转化为简单的组合优化。命题人用生活语言包装，考察学生的抽象能力。
【全体系闭环总结】
本体系实现 L0-L7 图论初步与组合论证无跳跃生长，全程唯一题根：点和线的关系是离散结构的核心，图论就是研究这种关系。
生长路径： L0 基本概念 → L1 握手定理与子图补图 → L2 树 → L3 欧拉图 → L4 哈密顿图 → L5 图兰定理 → L6 拉姆齐数 → L7 IMO 级综合
与后续体系衔接：
- 为「网络流」「匹配理论」「代数图论」等高级内容奠基
- 与「组合计数」「极值组合」「概率方法」深度融合
无遗漏、无冗余、完全闭环。