图论与组合数学一、前置概念树与森林1.1 树n nn个顶点、n − 1 n-1n−1条边的连通无环图。每个结点及其后代都可以看作一棵子树。1.2 森林多个互不相连的树放在一起构成森林。森林的每个连通分量都是一棵树。森林与生成森林的区别见第五节。二、图的基本概念2.1 无向图定义A — BA 与 B 之间只有一条无箭头的线无向边连接可双向通行。度一条边连接 A、B 时A、B 各获得 1 个度无向图不分入度 / 出度。A / \ B C无向图总度数总度数 边数 × 2 总度数 边数 \times 2总度数边数×2即边数 总度数 ÷ 2 边数 总度数 \div 2边数总度数÷22.2 有向图定义A → BA 与 B 之间有一条带箭头的线有向边连接只能单向通行。入度A ← BA 有一个入度出度A → BA 有一个出度A ↙ ↖ B → C一条边 1 个出度 1 个入度所以总入度 总出度 边数三、连通图与强连通图3.1 连通图无向图定义任意两个顶点之间存在路径则为连通图否则为非连通图。n nn个顶点的连通图最少有n − 1 n-1n−1条边树形最多有C n 2 C_n^2Cn2​条边完全图n nn个顶点的非连通图最少有0 00条边最多有C n 2 − 1 C_n^2 - 1Cn2​−1条边完全图去掉一条边即一个孤立点 其余n − 1 n-1n−1个顶点组成完全图。C n m C_n^mCnm​、A n m A_n^mAnm​的计算公式见第八节。3.2 强连通图有向图定义任意两个顶点之间都有路径。n nn个顶点的强连通有向图最少有n nn条边首尾相连的有向环最多有2 × C n 2 n ( n − 1 ) 2 \times C_n^2 n(n-1)2×Cn2​n(n−1)条边任意两点之间都有双向边。四、母图与子图4.1 母图定义作为来源的图子图从它这里取点取边。4.2 子图定义点和边都来源于母图时此图称为母图的子图。4.3 生成子图定义必须包含母图所有顶点边数任意但每条边都必须来自母图。五、生成树与生成森林5.1 生成树定义连通图的生成树是包含原图中全部顶点的一个极小连通子图理解在保证原图点与点之间保持连通的前提下让边尽可能少删去所有环使其构成一棵树特征用完全部点包含原图的所有顶点边来自原图所有的边都属于原图保持连通是一个连通无环的树形结构5.2 生成森林适用对象非连通图定义非连通图中各个连通分量的生成树共同构成了该图的生成森林即多个生成树组成对应第一节的「森林」概念森林 多个互不相连的树。六、图的存储原图6.1 邻接矩阵存储形式伪代码实现for(1-n){cinuv;G[u][v]1;G[v][u]1;// 无向写有向不写}G [ u ] [ v ] 1 G[u][v] 1G[u][v]1表示存在边u → v u \to vu→v无向图需对称地双向置 1有向图只写一条。6.2 邻接表数组 链表存储形式伪代码实现vectorintG(n);for(1-n){cinuv;G[u].push_back(v);G[v].push_back(u);// 无向写有向不写}每条G[u]相当于一条链表用vector模拟相邻顶点挂在链上。6.3 两种存储方式对比对比项邻接矩阵邻接表存储空间O ( n 2 ) O(n^2)O(n2)O ( n m ) O(n m)O(nm)判断u uu、v vv是否相邻O ( 1 ) O(1)O(1)O ( 度 ) O(\text{度})O(度)遍历一个点的相邻点O ( n ) O(n)O(n)O ( 度 ) O(\text{度})O(度)七、拓扑排序7.1 概念拓扑排序针对有向无环图DAG反复删除入度为 0 的顶点并输出删除顺序即拓扑序结果可能不唯一。7.2 过程演示原图方便演示步骤操作输出11 入度为 0弹出122 入度为 0弹出233 入度为 0弹出344 入度为 0弹出4结果1 2 3 4拓扑排序只能用于有向无环图DAG有环图不存在拓扑序。八、数学组合与排列8.1 概念与区别组合C n m C_n^mCnm​无序定义从n nn个中选择m mm个作为一个组不考虑顺序求解问「有多少组」排列A n m A_n^mAnm​有序定义对从n nn个中选出的m mm个人 / 物进行排队考虑顺序求解问「有多少种排法」8.2 公式计算A n m n × ( n − 1 ) × ( n − 2 ) × ⋯ × ( n − m 1 ) ⏟ m 个因数 A_n^m \underbrace{n \times (n-1) \times (n-2) \times \dots \times (n-m1)}_{m\ \text{个因数}}Anm​m个因数n×(n−1)×(n−2)×⋯×(n−m1)​​C n m A n m A m m n ! m ! ( n − m ) ! C_n^m \frac{A_n^m}{A_m^m} \frac{n!}{m!\ (n-m)!}Cnm​Amm​Anm​​m!(n−m)!n!​常用特例C n 2 n ( n − 1 ) 2 C_n^2 \dfrac{n(n-1)}{2}Cn2​2n(n−1)​回看第三节的连通图边数结论8.3 解题原则特殊位置 / 特殊元素优先处理。分类 → 用加法原理将问题按不同情况分为互斥的几类最终将各类的方法数相加分步 → 用乘法原理将完成一件事分为连续的几个步骤最终将各步骤的方法数相乘总结图论章节的核心是度与边数的关系无向图总度数 2 × 边数 总度数 2 \times 边数总度数2×边数有向图总入度 总出度 边数 总入度 总出度 边数总入度总出度边数以及生成树 / 生成森林的构造理解组合排列部分以分类加法、分步乘法为解题主线。