网络流

最大流

 

汇点 s，源点 t ，每条边有容量限制，求从 s 到 t 的最大流量，即最大流。

 

对于图$G(V,E)$，设每条边的实际流量$f(e)$，最大流量（容量）$c(e)$ .

 Ford-Fulkerson算法

 

 分两步求得最大流：

1. 找到一条从 s 到 t 的且只经过$f(e)<c(e)$的边路径。沿着该路径尽可能增大$f(e)$，不断重复以上操作，直到不存在满足条件的路径。

2. 只利用满足f(e) < c(e)的边e或者f(e) > 0的边e的反向边rev(e)，寻找一条 s 到 t 的路径，沿着该路径尽可能增加流，不断重复，直到找不到满足条件的路径。

 

 称由满足f(e) < c(e)​的边以及满足f(e) > 0 的边的反向边rev(e)组成的图为残余网络，称残余网络上的s-t路径为增广路。

 

  代码

//用于表示边的结构体（终点，容量，反向边）
struct edge
{
	int to, cap, rev;
};

vector<edge>G[MAX_V];//图的邻接表表示
bool used[MAX_V];//DFS中用到的访问标记
//向图中增加一条从s到t容量为cap的边

void add_edge(int from, int to, int cap) {
	G[from].push_back((edge) { to, cap, G[to].size() });
	G[to].push_back((edge) { from, 0, G[from].size() - 1 });
}

//通过DFS寻找增广路
int dfs(int v, int t, int f) {
	if (v == t)return f;
	used[v] = true;
	for (int i = 0; i < G[v].size(); i++) {
		edge &e = G[v][i];
		if (!used[e.to] && e.cap > 0) {
			int d = dfs(e.to, t, min(f, e.cap));
			if (d > 0) {
				e.cap -= d;
				G[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}

//求解从s到t的最大流
int max_flow(int s, int t) {
	int flow = 0;
	for (;;) {
		memset(used, 0, sizeof(used));
		int f = dfs(s, t, INF);
		if (f == 0)return flow;
		flow += f;
	}
}
struct edge{int to,cap,rev;}

 

最小割

对于某个顶点集合$S\in V$，从S出发指向S外部的边的集合，记为割 (S,V\S).这些边的容量之和，被称为割的容量。

割相当于连接两个顶点集的桥梁的集合，割的容量即所有桥梁的容量之和。

• 如果$s\in S,t\in V$\S，那么此时的割又称为s-t割。

如果将s-t割中的边都删去，就不会有s到t的路径了。

割的最小容量就是最小割问题。

 

有**定理：最大流等于最小割**

 这也容易理解，要切断s到t的所有路径，就是切断所有流量流通，所以最小割就是要把所有s到t的流量都拦住，就是说割容量要>=最大流，同时又要做到最小，就只有刚好等于最大流。

 

匹配

 

有一边的集合，集合中所有边两两之间没有公共端点，这样的集合M称为匹配。

 二分图匹配

 

  设有图$G(U \cup V;E)$，为二分图。

  将匹配问题看成最大流问题的一种特殊情况。对原图作如下变形：

  将原图中的所有无向边改成有向边，方向从U到V，容量为1，增加源点s 和汇点t ，从s 向所有顶点u连一条容量为1的边，从所有顶点v向t 连一条容量为1的边。

  求新图最大流的结果就是原图最大匹配。

 

 一般图匹配

  对于无向图G=(V,E)的每一条边随意赋予方向得到有向图$G'=(V,E')$。并对每条边$e\in E'$都关联一个变量$x_e$。则Tutte矩阵是一个如下定义的V*V矩阵$T=(t_{u,v})$

$$t_{u,v}=\left\{ \begin{aligned} x_{(u，v)},((u,v)\in E') \\ -x_{(v,u)},(v,u\in E')\\0,(其他) \end{aligned} \right.$$

 

  T的秩等于最大匹配的顶点数

 

匹配，边覆盖，独立集和顶点覆盖

 

 匹配 · · · · · · · · · · · · · · · · · · · · · · 在G中两两没有公共端点的边集合M

 边覆盖 · · · · · · · · · · · · · · · · · · · · · G中的任意顶点都至少是F中某条边的端点的边集合F

 独立集 · · · · · · · · · · · · · · · · · · · · · 在G中两两不相连的顶点集合S

 顶点覆盖 · · · · · · · · · · · · · · · · · · · G中的任意边都至少有一个端点属于S的顶点集合S

 

1. 对于不存在孤立点的图，|最大匹配|+|最小边覆盖|=|V|
2. 有 |最大独立集|+|最小顶点覆盖|=|V|
3. 有|最大匹配|=|最小顶点覆盖|