离散数学&数据结构 - 图论常匹配问题与算法概括

2025年5月12日笔记学习 / 离散数学 zh-CN

离散数学&数据结构-图论常匹配问题与算法概括

关键词：从某点到某点路径最短、有向/无向图、有权图
典型题干

求 A 城市到其他城市的最短路径。
常用算法：
- Dijkstra：正权图单源最短路径（常用于地图/网路延迟）
- SPFA：负边权也能跑，适用于稀疏图
- Floyd：所有点对最短路径，三重循环（适用于稠密图）
适用问题类型：
- 地图导航、路线规划、网络延迟最小化

关键词：走遍所有边一次、不重复、回到起点或不回起点
典型题干：

邮递员需要经过每条街道一次，如何规划路线？
常用算法：
- Hierholzer 算法：找欧拉回路或路径
- 判断条件：
  - 欧拉回路：所有点度数为偶数
  - 欧拉路径：最多两个点为奇数度
适用问题类型：
- 邮递、清扫机器人、巡检线路问题

最大流问题就是：

想象你是个调水的管道工：
有个源点（source）：水从这儿开始流。
有个汇点（sink）：水最终要流到这。
图里的每条边是水管，有个最大能流多少水的限制（容量）。
你要解决的核心问题就是
“从源点最多能往汇点送多少水？”

EK算法最大流是：

用广度优先去找：从源点到汇点还有没有“能通的水路”。
找到就“倒水”：找出这条路上最细的那根管子（瓶颈），推这么多流量。
更新管道：把用掉的流量减去，剩下的再来。
直到你怎么找都找不到新路了：那就是最大流了。

Edmonds-Karp 是一种 基于广度优先搜索（BFS） 的最大流算法，属于 Ford-Fulkerson 方法的实现之一。
注意：离散数学考试给予简化版本，不维护反向边。

它的核心思想是：
每次用 BFS 在残量网络中找一条从源点 S 到汇点 T 的最短增广路径，然后将该路径上的可增广流量加入到总流中，并更新残量网络。

残量网络：对于每条边 (u,v)，我们维护：
正向边容量 c(u,v)
当前流量 f(u,v)
残余容量 r(u,v) = c(u,v) - f(u,v)
并添加反向边 (v,u)，其残余容量为 f(u,v)，表示可以“退回”流量。

假设你有如下图的网络：

S --(10)--> A --(5)--> T
 \                      /
  \----(15)------------/

你用 BFS 找到 S->A->T，可增广流为 5，再找 S->T，可增广流为 15。
总流量 5 + 15 = 20，路径更新后不能再增广，算法结束。

最大流 = 能从水库 S 送到城市 T 的最多水量
最小割 = 一刀下去能阻断的最小总水流（把某些管道切掉）
换句话说：
最大你能送的 = 最少别人能拦的

S --(3)--> A --(2)--> T
 \                  /
  \----(4)--------/

最大流是 5（S→A→T 走 2，S→T 走 3）
最小割是割断 S→T 和 A→T（容量是 3+2=5）
他们相等，定理成立。

术语	定义（通俗解释）
网络流图	一个带有容量限制的有向图，每条边表示“能容纳多少流量”。
源点（S）	流量的起点，像是“水库”或“工厂”。
汇点（T）	流量的终点，像是“城市”或“消费者”。
流量（Flow）	实际通过边的流量，不能超过边的容量。
容量（Capacity）	边所能承受的最大流量，相当于“管道粗细”。
残量网络	当前流量状态下，图中还可以继续“走”的路径与容量。
增广路	在残量网络中，从源点到汇点还可以“加流”的路径。
最大流	从源点到汇点能“加”上的最大总流量。
割（Cut）	把图的点分成两个集合，源点在一边，汇点在另一边。
割的容量	从源点集合通向汇点集合的边的容量总和。
最小割	所有可能割中，容量最小的一个，表示“最小阻断能力”。
最大流最小割定理	最大能通过的流量 = 最小能拦下的割。
EK算法（Edmonds-Karp）	使用 BFS 查找增广路，逐步累加流量，直到没有增广路。时间复杂度 O(VE²)。
Dinic算法	更快的最大流算法，基于分层图+DFS增广。时间复杂度 O(V²E)（稀疏图较优）。