图论：连通性与匹配
高三奥数·组合数学·难度 5/5·约 30 分钟
图论在竞赛中的常见主题。 基本概念：度、路径、连通分支、树、二分图。 握手定理： 推论：度为奇数的顶点必有偶数个。 树的性质： 个顶点的树恰有 条边，任意两点间有唯一路径，去掉任一条边即不连通。 二分图判定：一个图是二分图当且仅当它不含奇圈。 霍尔定理（完美匹配存在条件）：二分图存在饱和 的匹配，当且仅当对 的任意子集 ，其邻域 。
学完你应该能
- 掌握握手定理及其奇度点推论
- 理解树的等价刻画
- 了解二分图判定与霍尔定理
常见易错点
握手定理中忘记乘2 把「无奇圈」误记为「无奇数个顶点」
看完整讲解
这个知识点有 4 个由教师实名选定的讲解视频和 30 道配套练习题。注册后可以观看视频、做题自测，系统会记录你的掌握度，做错的题自动进错题本并按遗忘曲线提醒复习。