二分图匹配

给定一个二分图G，在G的一个子图M中，M的边集{E湖针晚济关}中的任意两深助条边都不依附于同一个顶点，则称M是一个匹配。

• 中文名称 二分图匹配
• 外文名称 Bipartite Matching

定义

　　极大匹配(Maximal Matching)是指在当前已完成的匹配下,无法再通过增加未完波岩值班并思气气盐钱成匹配的边的方式来增加匹配的边数。最大匹配(maximum matchi东杀片成量写台仅ng)是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。

　　如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。

　　求二分图最大匹配可以用最大流(Maximal Fl来自ow)或者匈牙利算法(Hungarian Algorithm)

图

　　设G=(V360百科，E)是一个图，M是E的一个子集，如果M不含环且任意两边都不相邻，则称M为G的一个匹配打。G中边数最多的匹配称为G的最大匹配。 对于图G=燃杂木英第钟们正手(V，E)，在每条边e上赋一个实数权w(e)。设M是G的一个匹配。定义 M中所有边权值之和称之为匹配M的权。G中权最大的匹配称为G的最大权匹配。如果对一切，e∈E，w(e)=1,则G的最大权匹配就是G的最大匹配。

匹配

　　设M是图G=(V,E)的一个匹配，vi∈V型刘上研。若vi与M中的边相关联，则称vi是M饱和点，否则称vi为M非饱和点。 如果G中每个顶点来自都是M饱和点，则称M为G的完美匹配。 设M是G的一个匹配，跳许即言见P是G的一条链。如果P的边交替地一条是M中的边，一条不是M中的边，则称P为M交错链。类似地，我们可以定义G的交错圈。易知，G的交错圈一定是偶圈。 一条连接两个不同的M非饱和点的M交错链称为M增广链。 两个集合S1与S2的"异或"操作S1⊕S2是指集合S1⊕S容环小宽专应毫曾的苦微2=(S1∩S2)-(S1∪S2) 容易看出，设M是G的匹配，P是G中的M增广链、则M⊕P也是G的匹配，而且 可以证明，G中匹配M是最大匹配当且仅当G中没有M增广链。

例题

　　中、日、韩三个足球队进行比赛，已知A不是第一名，B不是韩国队，也不是第二名，第一名不是日本队，中国队第二.问A、B、C各代表哪国队?各是第几名?

　　我们先来降低难度.先只要求你判断出中、日、韩各是第几名(不必判断A、B船、C).可以把中、积日、韩各用一个点代表，列于上一行.第更果久律觉华随苗一、二、三名各用一个点代表，列于下一行，记为:

　　V1={中，日，韩}，V2={第1名，第2名，第3名}.

　　V1中的点与V2中某一个点有肯定关系的，就画一条实线，如和②.右完杀图红磁容否定关系的两点之间画一条虚线，如不是②;不是①.把已知条件不加任何推理地表现于图上.虚线2条，实线1条，共3条线.

　　现在，有两个明显的事实;第一，V1中每点有且只有一条实线与V2中相应点配对，V2中每点有较生革聚且只有一条实线与V1中相应点配对.V1内部点之间不会有线相联结，V2内部点之间也不会有360百科线相联结.第二，从V1(或V2)中某一个点，例如说a点如发出了一条实线向着V2(或V1)中某一个点，例如说x点，那有面心角概皮审毫犯汽拿么a点与V2(或V且景推做小1)中其他点之间必然只能用虚线联结.(这是逻辑推理中的排它性)

　　由此，我各因色受手罗祖们很容易将中、日、韩的名次判出.

　　这样的问题，抽象起来可归属于白大统南群图论中称之为"二分图的匹配"问战声失题.

　　图论的名词术语太多，这里不作详细定义，只是描述性介绍一下，大家以前在"一笔画"等讲中已初步接触.所谓二分图，就是顶点集合可以划分成两个部分，V=V1+V2，如V1有p个点，记为V1={v1，v2…，vp}，V2告且哪死有q个点，记为V2={vp+1，vp+2…，vp+q}，而V1中任意一点，不会与V1中其他声材北概良斯木点联结，而只能与V2中某些扩右点联结;V2也如此.大家看几个例.

　　一般的图记为G=(V，E)，V当是顶点集合，E是边(也可称为线)的集合.大家在哥尼斯堡七桥问题中已领略过这种抽象.现在的二分图是一类特殊的图，只不过顶点集V划分为两部分，而这只能"跨越"于然牛抗培止章剧V1中某个点和V2中另一个点.二分图的匹配问题，就是找一个边的集合，这些边之间都没有公共的端点.

　　关于二分图的匹配，要研究的是"最大匹配"，即找一个边最多的匹配.

　　就本讲开始引入的问题看，我们还没有解完，因为还有A、B、C三个代号到底如何归于中、日、韩三队的问题.一种解题办法，是把已判出的国籍和名次捆绑在一个顶点内，如(中2)、(韩1)、(日3)，再和A、B、C构造一个新的二分图:

　　显然，推知B是(日3)，因为B有2条虚线，而必然有1条实线，只能推出B与(日3)之间为实线.同理，(韩1)只能为C;剩下的唯一的情况留给了A为(中2).全部问题解决了.

　　再看最初的题目，如果你选择先判断中、日、韩和A、B、C三个代号之间的匹配关系，将会怎样呢?画一个图看，利用已知条件画出实、虚线.

　　只能利用B不是韩国队及中国队第二，B不是第二(因此B不是中国队)这样一些条件，题目中另二句话:A不是第一名，第一名不是日本队，这种否定关系之间，没有传递性，你不能判定A是不是日本队.因此根据已知条件所画的图中只有两条虚线，之后最多只能确定日、B之间为实线.所以对这样的二分图，无法找出合理的最大匹配.这方法使问题求解走进了死胡同.

　　那么你选择先判A、B、C和第一、第二、第三名之间的匹配关系，又会怎样呢?画一个图看.

　　现在也只有二条虚线，仍然无法找出最大匹配，或说解不唯一，对求解问题无助.

　　现在回过头来看，先找国别与名次之间的匹配，似乎有些"碰运气"，因为完全可以把题目改动，使先找国别与名次的匹配无法解决，例如叙述改为:

　　中、日、韩三足球队比赛，已知结果为:第1名不是A，第2名不是韩国队也不是B，A不是日本队，中国队为B，问A、B、C，和1、2、3名与各国队如何匹配?

　　细心读者发现，这只是把原题中A、B、C的地位与1、2、3名的地位互换而已.所以现在改动后的题目，再先抓"国别"和"名次"的匹配，就无法求解.

　　但是数学要求找出一种解一般问题的方法而不是"碰运气"，而且完全可以找一个例子，使得无论取国别与名次;或国别与代号(A，B，C);或代号与名次这三类二分图的匹配都无法求解，而必须找更广泛意义下的匹配才能解决，为此先介绍一般的三个因素一起考虑的"匹配"方法.

　　先结合前例，将国别用三个不同点表示于上方，三个名次点表示于左下方，三个代号点表示于右下方.用实线的肯定关系和虚线的否定关系把已知条件"翻译"于图上.