1:流网络
c(u, v)c(u, v) = 0。我们区别两个顶点:
函数::满足下面两条性质:
这个网络的流量就是:
此外当然多源点和多汇点的流网络可以转换为只有一个源点和汇点的普通网络。
如图:
概念:
(1)残存网络
(2)增广路径
例子:
(3)切割
(4)最大流最小切割定理
3:二分图
,使得每一条边都分别连接L、R中的顶点。如果存在这样的划分,则此图为一个二分图。二分图的一个等价定义是:不含有「含奇数条边的环」的图。
图1 是一个二分图。为了清晰,我们以后都把它画成图2 的形式.
4
饱和与非饱和:
我们定义匹配点、匹配边、未匹配点、非匹配边,它们的含义非常显然。
例如图
最大匹配:一个图所有匹配中,所含匹配边数最多的匹配,称为这个图的最大匹配。
完美匹配:如果一个图的某个匹配中,所有的顶点都是匹配点,那么它就是一个完美匹配。
完美匹配一定是最大匹配(完美匹配的任何一个点都已经匹配,
添加一条新的匹配边一定会与已有的匹配边冲突)。但并非每个图都存在完美匹配。
举例来说:如下图所示,如果在某一对男孩和女孩之间存在相连的边,就意味着他们彼此喜欢。
是否可能让所有男孩和女孩两两配对,
使得每对儿都互相喜欢呢?图论中,这就是完美匹配问题。如果换一个说法:
最多有多少互相喜欢的男孩/女孩可以配对儿?这就是最大匹配问题。
基本概念讲完了。求解最大匹配问题的一个算法是匈牙利算法,,下面讲的概念都为这个算法服务。
增广路:从一个未匹配点出发,走交替路,如果途径另一个未匹配点(出发的点不算),
因此,研究增广路的意义是改进匹配。只要把增广路中的匹配边和非匹配边的身份交换即可。
由于中间的匹配节点不存在其他相连的匹配边,所以这样做不会破坏匹配的性质。
交换后,图中的匹配边数目比原来多了
找不到增广路时,达到最大匹配(这是增广路定理)。匈牙利算法正是这么做的。
匈牙利算法伪代码:
bool 寻找从k出发的对应项出的可增广路{while (从邻接表中列举k能关联到顶点j){if (j不在增广路上){把j加入增广路;if (j是未盖点 或者 从j的对应项出发有可增广路){修改j的对应项为k;则从k的对应项出有可增广路,返回true;}}}则从k的对应项出没有可增广路,返回false;} void 匈牙利hungary(){for i->1 to n{if (则从i的对应项出有可增广路)匹配数++;}输出 匹配数;}生活是一段奇妙的旅行,就在那一去无返的火车上。