图上的流动 flow

定向图的要素，顶点集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: ER(实数)，令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定理中，如果某些边的容量为无穷大，定理的结论仍然成立，只不过此时的最大流的流量可能是无穷大。证明的方法也没有多大变化，无非就是稍稍改变一下其中的某些叙述。

好文章，因为我已经看晕了：）

这些应该都是比较简单的图论吧,曾经被蒙骗参加那个垃圾竞赛:全国大学生数学建模竞赛时认真的学过图论,印象比较深的是polya的一个记数定理,用群的作用证明的,比较漂亮.不过后来看一个匈牙利人的写的一本图论,就看得吐血了,有些证明方法真的太巧妙了,那种漂亮让人感觉这方法不是人想出来的,后来才知道那是属于代数图论的内容.

>>不过后来看一个匈牙利人的写的一本图论,就看得吐血了,有些证明方法真的太巧妙了,那种漂亮让人感觉这方法不是人想出来的

I guess you are referring to one of the two books written by Prof. Bela Bollobas?

* Modern Graph Theory (First edition, 2002)

* Random Graphs (Second edition, 2001)

I'll see if I get a library copy of the first book, its Amazon comments are very positive.

曾经被蒙骗参加那个垃圾竞赛:全国大学生数学建模竞赛时认真的学过图论,
====================================
一直认为这个竞赛是垃圾，所以我大学时就拒绝参加这种竞赛。

印象比较深的是polya的一个记数定理,用群的作用证明的,比较漂亮.不过后来看一个匈牙利人的写的一本图论,就看得吐血了,有些证明方法真的太巧妙了,那种漂亮让人感觉这方法不是人想出来的,后来才知道那是属于代数图论的内容.
=================================
代数图论？用群论来解决图论之类的是吗？我以前看过一本图论的书，末尾就是这个

好文章，因为我已经看晕了：）
========================
看来这个简介很失败，呵呵。

>这些应该都是比较简单的图论吧,曾经被蒙骗参加那个垃圾竞赛:全国大学生数学建模竞赛时认真的学过图论,印象比较深的是polya的一个记数定理,用群的作用证明的,比较漂亮.不过后来看一个匈牙利人的写的一本图论,就看得吐血了,有些证明方法真的太巧妙了,那种漂亮让人感觉这方法不是人想出来的,后来才知道那是属于代数图论的内容.

有比Polya定理更漂亮的啊？能简单介绍一下吗？

看来这个简介很失败，呵呵。
===========================
图论这东西就算配合插图也很难掌握的，我很怕这东西。

gauge兄写这么长的文章必定得花很多时间，但回帖的人不多可能会让gauge兄失去热情。这次内容比较常见，很期待计划中的最后三项内容。支持gauge兄，加油！