图论 = 在满足结构限制的所有方案中进行优化。
一、连通性
连通图
任意两点之间均存在路径的图。
连通分量
极大的连通子图。
强连通图（有向图）
任意两点互相可达的图。
强连通分量 (SCC)
极大的强连通子图。
割点（Articulation Point）
删除后使连通分量增加的点。
桥（Bridge）
删除后使连通分量增加的边。
二、生成树
生成树
包含所有顶点且边数为 $n-1$ 的连通无环子图。
最小生成树 (MST)
在所有生成树中，边权和最小的。
严格次小生成树
在所有 权值大于 MST 的生成树中最小的。
非严格次小生成树
在所有 不同于 MST 的生成树中权值最小的。
三、路径问题
路径
顶点不重复的边序列。
最短路
在所有 $s o t$ 路径中 长度最小 的。
最短路树
从源点出发的最短路径构成的树。
第 $k$ 短路
按路径长度排序的第 $k$ 小路径。
四、匹配
匹配
任意两条边不共享端点的边集。
最大匹配
在所有匹配中 边数最多 的。
完美匹配
每个点均被匹配的匹配。
二分图最大匹配
二分图中边数最多的匹配。
五、网络流
流
满足容量限制和流量守恒的边权分配。
最大流
在所有合法流中 总流量最大 的。
割
将 $s,t$ 分开的点集划分。
最小割
在所有 $s,t$ 割中 容量最小 的。
最小费用最大流
在 最大流 前提下 费用最小。
六、欧拉与哈密顿
欧拉路径
恰好经过每条边一次的路径。
欧拉回路
恰好经过每条边一次并回到起点。
哈密顿路径
恰好经过每个点一次的路径。
哈密顿回路
恰好经过每个点一次并回到起点。
七、拓扑结构
拓扑排序
对 DAG 的顶点进行线性排序，使所有边方向一致。
DAG（有向无环图）
没有有向环的有向图。
八、树结构
树
连通且无环的图。
森林
若干棵树组成的图。
直径（树）
树中 最长简单路径长度。
重心（树）
删除后最大子树最小的点。
九、意义
便于复习