最大流问题图和收发点

一个图是由点集V={v_i}和V中元素的无序对的一个集合E={e_k}所构成的二元组，记为G=(V,E)，V中的元素v_i叫做顶点，E中的元素e_k，叫做边。

仅有一个入次为0的点v_s称为发点(源)，一个出次为0的点v_t称为收点(汇)，其余点为中间点，这样的网络G称为容量网络，常记做G=(V,E,C)。

最大流问题容量和流量

设有向连通图G=(V,E)，G的每条边(v_i,v_j)上的非负数c_ij称为边的容量。对任一G中的边(v_i,v_j)有流量f_ij，称集合f={f_ij}为网络G上的一个流。图1即为一个有向连通图，括号中第一个数字代表容量，第二个数字代表流量。

最大流问题可行流

称满足下列两个条件的流为可行流：

1.容量限制条件：对G中的每条边(v_i,v_j)，有0≤f_ij≤c_ij；即每条边上的流量非负而且最大也只能达到容量的限制。

2.平衡条件：对中间点v_i，有

对发、收点v_s,v_t,，有

一个流f={f_ij}，当f_ij=c_ij，则称流f对边(vi,vj)是饱和的，否则称f对(v_i,v_j)不饱和。

最大流问题割（截）集

容量网路G=(V,E,C),v_s,v_t为发、收点，若有边集E‘为E的子集，将G为两个子图G₁,G₂，即点集V被剖分其为两个顶点集合分别记

1.若把整个截集的弧从网络G=(V,E,C)中丢去，则不存在从v_s和vt的有向路，即图(V,E-E')不连通。

2.只要没把整个截集删去，就存在从v_s和vt的有向路，即当E’‘为E的真子集，图G(V,E-E'')仍连通。

由此可知，截集是从起点v_s到终点v_t的必经之路。

割集