数学大学
暴力枚举和抽象转换
组合数学 · 漫谈组合数学
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
暴力枚举和抽象转换
组合数学 · 漫谈组合数学
世界杯引出的问题
从世界杯赛程数场次切入：数数也有方法论，会建模就能「秒算」。
淘汰赛场次
每场淘汰一队，n 队决出冠军只需 n−1 场
数数的两种路
直接枚举慢，找到结构规律快
一一对应
一一对应是计数的核心武器：数不动的 A，去数与它一一对应的 B。
双射
一一对应保证两边元素个数相等
典型应用
n 个元素子集 ↔ 长度 n 的 0-1 串
七桥问题
哥尼斯堡七桥问题：把陆地桥抽象成图，一次不重复走遍所有桥不可能。
抽象成图
陆地化点、桥化边，问题变成一笔画
奇点判据
奇度顶点多于 2 个则不存在欧拉路径
本节要点
- ✓淘汰赛 n 队 n−1 场：每场淘汰一队
- ✓一一对应：数 A 转为数 B
- ✓七桥问题：抽象成图后奇点判据定案
延伸主题：推一遍单循环赛场次公式画一画七桥问题的图
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1为什么淘汰赛场次是 n−1？这个论证妙在哪里？
参考答案每场比赛恰好淘汰一支队伍，冠军是唯一未被淘汰者；n 支队要淘汰 n−1 支，恰好 n−1 场。它不枚举对阵表，而是抓住「一场一淘汰」的对应关系——结构性计数思想的典范。
2七桥问题的突破点为什么是「抽象成图」？
参考答案陆地的大小形状、桥的长短都无关紧要，重要的只是连接关系。抽象成顶点与边后，几何问题变成一笔画问题，立刻能用奇度顶点个数这一图论判据给出「不可能」的严格证明。
3「抽象成图」这一步丢掉了什么、留下了什么？
参考答案丢掉了地理尺寸、桥的长短与位置形态等几何细节；留下了连接关系——哪些区域之间有奇数条通道。计数与存在性判断只依赖后者，所以丢弃反而是解题的关键。