六年级 · 图论 · 深度理解

🎯找核心概念

这是哪类问题：这一讲专门解决“一群对象，两两之间有没有某种关系”这类问题：六个人握手、几台电脑连网线、花园里的小径能不能一笔走完、传球次数最多多少……表面上五花八门，本质都是把“对象”画成点、把“关系”画成连点的线，于是问题就变成了在一张“点和线组成的图”上数线、找路、判断能不能一笔画。图论就是教你怎么把现实问题翻译成这种点线图，再在图上推理。

关键词（大白话）：

点（顶点）：代表一个对象，比如一个人、一台电脑、一个路口、一盆花。
线（边）：代表两个对象之间的一种关系，比如握过手、连了网线、有一条小径。
度数：从某个点连出去的线的条数，比如某人握了几次手，这个点的度数就是几。
奇点 / 偶点：度数是奇数的点叫奇点，是偶数的点叫偶点。判断一笔画就靠数奇点个数。
一笔画：笔不离纸、每条线只走一遍，能不能把整张图画完（或走完）。
连通图：从任意一点都能沿着线走到其它任意一点，整张图“连成一片”不散开。
完全图：n个点两两都连了线的图，边数是 $C_{n}^{2}=\frac{n(n-1)}{2}$。

🔍理解本质规律

一笔画判定：一个连通图，奇点个数是 $0$ 时可从任意点出发回到原点一笔画；奇点个数是 $2$ 时必须从一个奇点出发、到另一个奇点结束；奇点个数超过 $2$ 就画不成。
握手定理：把所有点的度数加起来，一定等于边数的 $2$ 倍，所以度数之和必是偶数，奇点的个数一定是偶数（不可能有奇数个奇点）。
去奇点/重复边：有 $2n$ 个奇点（$n>1$）画不成一笔画时，每“消掉”一对奇点就要去掉或重复一条线，要消掉 $n-1$ 对，所以至少去掉/重复 $n-1$ 条线；邮递员要回到原点则用重复边把奇点配成对。
完全图边数：$n$ 个点两两连线共 $C_{n}^{2}=\frac{n(n-1)}{2}$ 条线，是握手、传球、连线计数的基本公式。
连通最少边：$n$ 个点要连成一片，至少要 $n-1$ 条线（这种图叫树）。
最值靠“上界估计 + 具体构造”：求最少/最多多少条线，要先证明“不可能比这更省/更多”（上界或下界），再真正画出一个达到这个数的例子，两头一夹才算定下来。
重复计数法：同一批东西，换两种角度各数一遍，得到的两个式子相等或可联立，从而解出未知量。

看得见的规律把这一讲想象成“连连看的地图”。每个人、每台电脑、每个路口都是地图上的一个小圆点；只要两者有关系，就在它们之间画一根橡皮筋。画完后退一步看整张橡皮筋网：数一数每个点伸出几根筋（度数），数一数伸出奇数根的点有几个（奇点），看看整张网是不是连成一片（连通）。一笔画就好比“用一根线不抬笔把所有橡皮筋描一遍”，能不能描完，全看奇点是 $0$ 个、$2$ 个还是更多。

为什么这样解为什么数奇点就能判断一笔画？想象你正在一笔画的途中“路过”某个点：进来一条线、出去一条线，成双成对地用掉。所以除了起点和终点，中间每个点用掉的线都是偶数条——它必须是偶点。能当“落单”起点或终点的点最多两个。于是：全是偶点 → 起点终点重合，画成一圈；恰好两个奇点 → 它俩当起点和终点；奇点超过两个 → 不够分，画不成。要补救，就把多出的奇点两两配对，给每对之间添一条重复的线，让它们都变回偶点，自然又能一笔画了。握手定理则是因为每条线都连着两个端点，数度数时被两头各数一次，所以度数总和恰好是边数的两倍。

🗂️分类总结题型

题型	怎么一眼认出	用什么方法
点线建模与构造设计g6-c23-p01	题目让你“摆放/设计”，要求每个对象、每条线满足某种关联条件（如每行过几个点、每点在几行上），看到“画图、构造一种方案”就属于这类。	把对象设为点、关系设为线，按关联要求（每点度数、每线点数）一点点凑出一张符合条件的图。
一笔画判定与重复/去边g6-c23-p03	出现“不重复走遍所有小径/街道”“一笔画出”“至少重复几段”“去掉哪些线段能一笔画”这类字眼。	先数奇点个数：$0$ 或 $2$ 可一笔画；超过则按“奇点配对”原则，每对奇点重复或去掉一条线，需要 $n-1$ 条，并挑长度之和最小的去/重复。
邮递员回到原点（中国邮递员问题）g6-c23-p05	要从某点出发“经过每条街道再回到原点”，街道可重复走，求最短总长度。	先算所有街道总长；图有奇点则用重复边把奇点两两配对（选重复长度最小的配法），总路程=全部边长+重复边长。
握手与度数推理g6-c23-p06	题目给出每人握手次数/每点连线条数，问某个人/点的次数。	把握手次数当度数，从次数最多的点入手（它和所有人都连），逐层确定每对到底连没连，推出未知点的度数。
完全图边数计数g6-c23-p07	“两两之间最多一次”“传球/握手最多多少次”这类两两计数。	用完全图边数 $C_{n}^{2}=\frac{n(n-1)}{2}$，若还附带一笔画等限制，再在此基础上加减相应条数。
连通图与最少边数g6-c23-p09	“联网/连通，使任意两点能互通”，要求最少多少条线，或由最少线数反推点数。	用“$n$ 个点连通至少 $n-1$ 条线”，逐步去掉度数为 $1$ 的点与线来证明，并用一点连其余各点的“星形”构造达到这个最少值。
图论最值与构造（上界＋构造）g6-c23-p10	在某种连接条件下求线段“最多/最少”条数，且要写证明的题。	先用反证或度数分类、均值不等式定出界限，再具体画出一张达到这个界的图（如二部图、特定连法），上下夹逼得最值。
重复计数建方程g6-c23-p11	两两关系分两类（朋友/敌人、连/不连），问“同类三元组（好委员会）”等组合计数。	对同一类对象换两个角度各数一遍，列出两个等式联立求解（如 $x+y$ 与 $3x+y$）。

✏️举例验证

例 1 g6-c23-p03

题：花园小径围成一张图，共 $12$ 个交点，问能否从第 $1$ 点出发不重复走遍所有小径；不能则至少要重复几段。

按规律解：把交点当点、小径当线，数每个点伸出几条线。统计后发现有 $8$ 个奇点（$1$ 到 $8$ 号点），奇点个数 $8>2$，所以不可能一笔走完。$8$ 个奇点要两两配成 $4$ 对，但一笔画允许留下 $1$ 对当起点终点，所以需要消掉 $4-1=3$ 对，也就是至少重复 $3$ 段小径（例如 $3\to4$、$5\to6$、$7\to8$，或别的等价配法）。补上这 $3$ 段后图只剩 $2$ 个奇点，就能一笔走完了。

为什么对：因为一笔画途中每个中间点都要“进一条出一条”成对用线，奇点最多容两个当起终点。$8$ 个奇点要靠重复边两两配对消掉，每对消一段，留一对当起终点，所以 $\frac{8}{2}-1=3$ 段，正好对上答案 $3$。

例 2 g6-c23-p06

题：六人两两握手，明明握 $5$、冬冬 $4$、兰兰 $3$、静静 $2$、思思 $1$ 次，问毛毛握几次。

按规律解：把六人当六个点，握过手就连线，握手次数就是该点度数。明明握了 $5$ 次=和其余五人都握了，所以每个人至少都有“和明明握的这一次”。思思只握 $1$ 次，那一次只能是和明明，所以思思和其他人都没握。再看冬冬握 $4$ 次：除明明外，他不会和思思握，于是和兰兰、静静、毛毛都握了。静静握 $2$ 次：明明、冬冬各一次，正好用完，不再和别人握。兰兰握 $3$ 次：明明、冬冬各一次，再和毛毛一次。于是数毛毛：明明、冬冬、兰兰各和他握了一次，静静思思没有，毛毛共握 $3$ 次。

为什么对：整个推理就是用“度数”一层层锁定每条线连没连，符合握手定理——六人度数之和 $5+4+3+2+1+3=18$，恰好是边数 $9$ 的 $2$ 倍，验证无误。

例 3 g6-c23-p07

题：六人传球，每两人之间至多传一次，最多共传几次。

按规律解：六人两两之间都传一次，对应完全图，边数 $C_{6}^{2}=\frac{6\times5}{2}=15$ 条。但“一次传球过程”要求像一笔画那样一条接一条连下去，而完全图里 $6$ 个点全是奇点（每点连 $5$ 条），$6$ 个奇点画不成一笔画，要消掉 $\frac{6}{2}-1=2$ 对中的对应边才能一笔连成。所以最多 $15-2=13$ 次。

为什么对：完全图给出两两传球的上限 $15$，再用一笔画规律扣掉无法连续的 $2$ 条，得到既不违反“每两人至多一次”、又能连贯传下去的最大值 $13$，与答案一致。

例 4 g6-c23-p09

题：若干台电脑联网，满足任意两台间连通等条件，最少 $79$ 条电缆。求台数；并问最多能连多少条。

按规律解：条件③保证整张图连通。连通图的最少边数是“点数减一”：从一点出发不走回头路，总会走到一个尽头点，去掉它和它那条线后剩下的图仍连通，如此一直去到只剩一点，正好去掉 $n-1$ 条线。所以最少 $n-1=79$，得 $n=80$ 台。求最多时，设连线最多的点 $A_1$ 连出 $k$ 条，与它相连的 $k$ 个点之间（因条件②）互不连线；与 $A_1$ 不连的有 $m$ 个点，$m+k=80$，每点最多连 $k$ 条，全图最多 $m\times k$ 条。由 $4mk=(m+k)^2-(m-k)^2\le 80^2=6400$ 得 $mk\le1600$。再把 $80$ 点分成各 $40$ 的两组、组间两两相连（二部图），恰好 $40\times40=1600$ 条且满足条件，故最多 $1600$ 条。

为什么对：“最少”用连通图至少 $n-1$ 条线的去点法严格证明，构造星形达到；“最多”先用均值不等式把上界卡在 $1600$，再造出真正达到 $1600$ 的二部图，上下夹逼，所以答案 $80$ 与 $1600$ 都成立。

🌱拓展应用

🛒 生活里的同类问题：

地图导航与扫街：邮递员、垃圾清运车、扫雪车要把每条路都走一遍又省路，就是一笔画/邮递员问题。
社交网络：谁认识谁、谁是好友，画成点线图就能数三角关系、找共同好友，正是握手与重复计数的现实版。
电路与网络布线：用最少电缆把所有设备连通、或在限制下连最多线路，对应连通图最少边与最值构造。
比赛赛程：循环赛“每两队赛一场”共多少场，就是完全图边数 $C_{n}^{2}$。
信息/水流管道的最大通过量：从 A 到 B 一段时间最多送多少信息，是网络流的入门体验（本讲第 2 题）。

🔄 变形我还认得吗：

把“小径”换成“桥”就是著名的“七桥问题”，把“街道”换成“画线条”就是“信封能否一笔画”，本质都在数奇点。
握手题改成“每人握手次数各不相同，可能吗”，仍用握手定理（奇点偶数个）来判断。
传球/握手题把人数换成 $n$，最多次数就从具体数变成含 $C_{n}^{2}$ 的式子，认出完全图就不慌。
联网题把“最少”改问“最多”，或加“任意三台最多两条”等约束，套路仍是“上界估计＋构造”。
好委员会题把“朋友/敌人”换成“同色/异色”“同队/不同队”，依旧用重复计数列方程。

🚀 它是后面什么的前置基础：

本讲的奇偶分析、度数思想是中学及竞赛“奇偶性与不变量”的前置基础。
完全图边数 $C_{n}^{2}$ 直接衔接排列组合（组合数 $C_{n}^{m}$）的学习。
上界估计＋构造的最值方法，是后续竞赛极值问题、抽屉原理综合题的通用思路。
重复计数法是组合计数、容斥原理的入门台阶。
连通图、树、二部图等概念是高中信息学、离散数学中图论的最初模型。

⚠️常见易错点

只看“图复杂”就猜能不能一笔画，不去老老实实数奇点个数。
把奇点个数和需重复（去掉）的边数搞混：$2n$ 个奇点是重复 $n-1$ 条，不是 $n$ 条，也不是 $2n$ 条。
邮递员问题忘了要“回到原点”，按只有 $2$ 个奇点处理，漏算把奇点全配对的重复边。
去边/重复边时只顾数量、不挑“长度之和最小”的那种配法，导致结果偏大。
完全图题直接用 $C_{n}^{2}$ 当答案，忽视“能否连续传球”等附加限制要再扣边。
求最值只给出一个构造例子就当证完，忘了还要证明“不可能更优”的那一半。
握手定理被忽略，算出奇数个奇点或度数和是奇数却不察觉错误。
重复计数时弄错每个对象“被数了几次”（好委员会被数 $3$ 次、其它被数 $1$ 次），方程就列错。

图论