图的匹配问题与最大流问题（一） 基本的概念2015-09-02从今天开始，准备写个系列，关于图的匹配，最大流，线性规划等这些图论中的重要而且有着千丝万缕连续的问题，顺便介绍求图的最大匹配问题的著名的匈牙利算法。算是对前段时间学习的一个小结吧。Ps：本人自认很水，多多见谅。（对内容进行了部分修改，原来使用Word编辑的公式这里无法显示，只能截图了）首先这次就先从基本的概念介绍起，顺便说说这之间的一些联系，接下来再开始一一上算法。一、图的匹配问题我们日常中听过最多的图的匹配问题可能就是著名的结婚问题: 在一个集合中，有m个女生，s个男生，其中1<=r<=s，设集合S1, S2, …,Si,.. ,Sm 分别代表第i个女生喜欢的男生的集合（当然一个女生可以喜欢多个男生），问有没有可能最终令这m个女生都能够和自己心仪的男生结婚？这个问题我们最直观的想法是，首先必须保证，任意r（<=m）个女生喜欢的男生数量必须大于等于r。这是很直观的，比如3个女生如果同时只喜欢上2个男生，则无论如何也无法分配。而正是这一直观的想法，解决了这一问题。从上面可知，最终能够令m个女生都能和自己心仪的男生结婚的必要条件就是任意r个女生喜欢的男生的数量必须大于等于r。而通过证明，我们知道这一条件也是充分的。这一证明并不是本文的重点，所以这里略过，有兴趣，可以继续讨论。这一问题就是图的最大匹配问题。不过更一般的我们常说的图的最大匹配问题是这样描述的：对于一个二部图，其最大匹配是多少？如图，所示，最大匹配为4.
二、最大流问题最大流问题是一个很经典的问题，很多人对此也很熟悉，它能够等同于一个线性规划问题。下面给出最大流问题的一个基本描述：如下图所示，s是源点，t为汇点，每条边上数字的含义是边能够允许流过的最大流量。可以将边看成管道，0/3代表该管道每秒最多能通过3个单位的流量，0代表当前流量。最大流问题即是说，从s点到t点，最大允许流量是多少？
易网时代-编程资源站