标题: 图论简介 (二)
作者: gauge
定向图的要素，顶点集V={x,y,z…},定向边E={xy,yz,…},其中xy表示由x指向y的一条变，所以xy不一定等于yx. 图上的流是一个函数，对每一条变指定一个非负实数，即流量，记作f(xy).因而图上的流也可以看作一个函数：f: E[0,\infty).
对于图上的顶点x来说，将通过x的流分作两类。其一是由x流出，即形如xy的边。另一类是流入，即形如zx的边。
图上给定一个流f, 则可将图上的顶点分作3类。
流出的量等于流入的量。
流出的量大于流入的量，这样的顶点称作源，source. 用记号s来表示。
流出的量小于流入的量，这样的顶点称作汇，sink. 用记号t来表示。
因而，除掉源和汇，其他的顶点没有产生额外的流量，也没有流消失。为简单起见，本文总是假设源和汇各自都只有一个。实际上，有多个source或者sink的流很容易归结为只有一个的情形。
容易证明，流出source的流量等于流入sink的流量，这个数称为流f的流量。
例子：电路。其中的源就是电源，包括发电机。其中的汇就是消耗电能的设备。当然，这里假定电路本身没有电力的损耗。
通常，线路上的流有容量限制。确切的说，定向图上的每一条定向边xy, 都对应到一个非负实数C(xy)，即容量，capacity.
在一个定向图中，给定每条边的容量，我们能否找到满足某些条件的流f, 使得对每一条边xy, 都有f(xy)=<C(xy).
比如，在所有的满足限制条件f(xy)=<C(xy)的流中，是否存在一个具有最大流量的流。当然这是一个初等而简单的问题。其证明类似于数学分析中所有与紧性有关的定理。首先，满足上述限制条件的流，其流量有一个绝对的一致上界，因而存在一个最小上界。因而就可以找到流的一个序列f_n, 使得f_n的流量趋向于这个最小上界。序列f_n一定有一个子序列收敛到某个流，这个流就具有最大流量。
所以，具有容量限制的定向图上，一定存在最大流。
最大流最小割定理。max-flow min-cut theorem.
定向图(V,E), V为顶点集，E为定向边的集合。对V的不相交的子集X,Y, 令E(X,Y)={定向边xy| 其中x在X中，y在Y中}.对取值为实数的函数g: ER(实数)，令g(X,Y)=\sum g(x,y), 亦即所有由X指向Y的定向边对应的函数值之和。
设S为V的子集，若source在S中，同时sink不在S中，则称S为一个割，cut. 也可以简单的说，割就是可以分离source和sink的顶点集。
设定向图上有容量函数C, 对于一个割S, 定义S的容量为C(S,V-S)= \sum C(xy), 其中x在S中，y不在S中。
设(V,E,C)为有容量限制的定向图，f为其上的一个流，满足容量限制。
简单事实：f的流量 =< 任意一个割的容量。
最大流最小割定理(Ford-Fulkerson, 1962): 存在一个割，其容量 = 最大流的流量。
亦即，具有容量限制的最大流的流量 = 最小割的容量。
证明纲要。
由于具有最大流量的流存扎，所以我们可以取一个最大流f.
递归的定义一个顶点集S如下，
首先，source在 S中。
其次，若x在S中，且f(xy)<C(xy), 则y也在S中。
最后，若x在S中，且f(yx)>0, 则y也在S中。
反复使用上述过程，最后可以得到一个由顶点构成的集合，即S. 由于图中只有有限多个顶点，所以上述过程也一定会在有限多个步骤之后终止。还需证明sink不在S中。如下。
假如sink在S中，则有一列顶点，x_1=source, x_2, …, x_n=sink.使得
r_i = \max{c(x_ix_{i+1})-f(x_ix_{i+1}), f(x_{i+1}x_i)}>0
这个式子不大容易看清，我们重新叙述如下，对于该序列中的任意两个相邻顶点x,y,其中x=x_i在y=x_{i+1}前面，都有 C(xy)-f(xy)>0 或者 f(yx)>0, 取二者当中较大的一个，这个数就是r_i. 然后取所有r_i中最小的一个，有限多个正数的最小值还是一个正数(严格大于0)。记这个正数为r. 由此对f作一些修改可以构造一个新的流，若边xy在上述序列中，则将流量f(xy)修改为f(xy)+r. 否则就不作改变。这样得到的函数确实是一个流，满足容量限制，而且其流量比f的流量要大r>0. 这就和f是最大流矛盾。这就证明了S确实为一个割。
下面说明割S的容量 = 流f的流量。首先有等式，
f的流量 = f(S,V-S) – f(V-S,S).
由S的构造，容易看出第一项 f(S,V-S) = C(S,V-S) = 割S的容量。第二项f(V-S,S) = 0. 证毕。
记号V-S表示不在S中的顶点全体，亦即表示集合S在V中的余集。
最大流最小割的整性定理：若容量C(xy)都是整数，则最大流f的流量f(xy)也都是整数。
实际上，当每条边的容量都是整数时，max-flow min-cut定理的证明也给出了一个很好的算法。如下，构造流的序列f_0, f_1, f_2, … 使得对每一条边，其流量都是递增的。
流f_0, 对每条边赋予流量f_0(xy)=0. 这是一个平凡的流。对于流f_i, 如max-flow min-cut定理的证明，构造相应的集合S. 则有两种情形。若sink在S中，如此，我们将终止这个构造过程。另一种情形是sink不在S中，这样可找到一条由source到sink的链，亦即一些首尾依次相连的边，这些边连接着source和sink, 将这条边的每一个的流量增加1, 这样得到一个新的流f_{i+1}. 这个程序将在有限多个步骤之后终止，最后所得即为一个在每条边上的流量都是整数的流。
最大流最小割的对偶定理
前面，我们对于流量进行的限制是要求每一条边的流量有一个上限，即容量C(xy). 我们也可以对每一个顶点的容量进行限制，即要求流入每一个顶点的流量有一个上限。注意到对每一个顶点，我们对于流入和流出进行了区分的，在一个不是 source或sink的顶点，流入的流量等于流出的流量。因而二者都是有限的。对于这样的图，我们可以类似的定义割、割得容量这两个概念。此时的割称为 Vertex-cut, 定义为V-{source,sink}的一个子集S使得，在V-S不可能存在一个具有正流量的流。
通常我们不限制source和sink的流量，或者说，这两个顶点的容量是无穷大。
对顶点限制流量的定向图，可以用一个小的技巧转化为我们已经证明过的对边的容量进行限制的定向图。于是我们有下述的定理。
定理：设定向图(V,E)的顶点有容量限制，但在source和sink处没有容量限制，则关于顶点的最小割的容量 = 最大流的流量。
Source 和sink多于1个的情形。
设s_1, s_2, … ,s_n为全部的source, 我们将之转化为只有一个sourece的情形。在原来的定向图中添加一个顶点s, 以及定向边ss_i, 在这些边上的容量限制取作无穷大。由此即可转换为只有一个source的情形。
对于sink完全类似的处理即可。
注意到，max-flow min-cut定理中，如果某些边的容量为无穷大，定理的结论仍然成立，只不过此时的最大流的流量可能是无穷大。证明的方法也没有多大变化，无非就是稍稍改变一下其中的某些叙述。
图的连通性 - connectivity
基本定理(Menger, 1927)
(1)[vertex form] 设s, t为图G中两个不相邻的顶点，则分离s, t的最少顶点数 = 连接s, t的独立道路的最大数目。
(2)[edge form] 设s, t为图G中两个不同的顶点，则分离s, t的最少边数 = 连接s, t的不相交道路的最大数目。
定理中术语的解释。
s, t为不相邻的顶点是指没有直接连接s, t的边。
所谓分离s, t的顶点集合S, 是指s, t都不在S中，且在原图中去掉S中的顶点，则s, t在剩下的图中不能相互连接。亦即，任意连接s, t的道路至少通过S中的一个顶点。
连接s, t的道路是指，一些首尾相接的边sa, ab, bc, …, xy, yt, 并且所有的顶点互不相同。例如sa, ab, bc, cd, da, at不是一条道路。
两条连接s, t的道路称为独立的，若这两条道路的公共点只有s, t.
不相交的道路，是指这些道路没有相同的边，但是可以有共同的顶点。
证明。
(1) 由图G构造一个相应的定向图，将图G中的每一条边xy都换作两条定向边xy及yx, 在 除开s,t 以外的每个顶点上赋予容量1. 由此限定的流在每条边上的流量只能为０或者１. 将顶点s, t看作source和sink. 于是由整性最大流最小割定理，可知存在一个具有最大流量的整数流。容易看出：连接s, t的独立道路的最大数目 = 最大流量 = 分离s, t需要的最少顶点数。
(2) 类似(1). 只需将其中对于顶点的容量限制改换为对于边的容量限制即可。
证毕。
若图中任意两个顶点都可以用一些边连接起来，则称这个图为连通的。
G为连通图，则G称为k-连通的，k-connected, 若
当Gz中顶点个数为(k+1)时，G为完全图，亦即任意两个顶点之间都有边相连接。
当G中的顶点个数至少为(k+2)时，去掉其中的任意(k-1)个顶点，所得到的图仍然连通。
注意，连通图可以看作1-连通的。
一个图称为k-edge-connected, 若去掉其中的任意(k-1)条边，剩下部分仍然连通。
使得图G为k-连通的最大数字k称为图G的连通度，connectivity.
使得图G为k-edge-connected的最大数字k称为图G的edge-connectivity.
约定，不连通的图，其两种连通度都规定为0.
Menger定理的推论：
(1) 图G是k-connected的 iff 对于图G中任意两个顶点，至少有k条独立的道路连接这两个顶点。
(2) 图G是k-edge-connected的 iff 对于图G中任意两个顶点，至少有k条不相交的道路连接这两个顶点。
Menger定理是在1927年证明的，而max-flow min-cut定理则是在1962年证明的。我们是由max-flow min-cut定理证明Menger定理。反过来，也可以用Menger定理证明max-flow min-cut定理。因而人们通常这样叙述：Menger定理与max-flow min-cut定理是等价的。两个数学定理等价，这个说法多少有点古怪：两个都正确的命题之间是等价的。这两个定理也都可以单独证明。
iff = if and only if, 这个简洁的用语充分的反映出来英语的某些优势。
另外Menger定理的结论“分离s, t的最少顶点数 = 连接s, t的独立道路的最大数目”用英文可以叙述为：The minimal number of vertices separate s from t = the maximal number of independent s-t paths. 似乎英文要简明一些。当然二者包含的信息还是相同的，用哪种语言并不能从本质上简化定理。