第一章引言
在过去的四十几年里，图论已经被证明是解决几何、数论、运筹学和优化等领域中各种组合问题非常有用的工具。而匹配是图论中的一个重要内容，也是图论的一个活跃的研究领域．匹配与独立集。横贯等概念有着密切的关系．三四十年代Ｈａｌｌ，Ｔｕｔｔｅ［１】【２】得出了二分图上完美匹配存在性的充要条件；五十年代末Ｂｅｒｇｅ［３１等得出了最大匹配的判定条件；Ｋｕｈｎ，Ｍｕｎｋｒｅｓ［４］［５１给出了二分图上的最大权匹配的一个有效算法；六十年代Ｅｄｍｏｎｄ［Ｓ］｛７］到了一般图上最大匹配以及最大加权匹配的第一个多项式算法；Ｇａｂｏｗ［ｓ］将Ｅｄｍｏｎｄｓ算法的复杂度从ｏ（［ｖ１４）提高到了ｏ（Ｉｖｌ３），还提出一种嵌入合并和查技术的算法其复杂度为ｏ（ＩＶｌｌＥＩ）１９】；Ｍｉｅａｌｉ，Ｖａｚｉｒａｎｉ［１０】提出了一个最优渐进运行时间为ｏ（￣／丽例）的算法，不过这个算法难于理解和实现，以至从发表到证明其正确性花了近十年的时间． 最大匹配、最大权匹配的启发式算法也有不少研究，ＤｏｒａｔｈａＥ．Ｄｒａｋｅ［ｎ］等人针对加权匹配问题提出了一种效率为；复杂度为ｏ（㈣）的算法；ＪｏｎａｔｈａｎＡｒｏｎｓｏｎ，ＭａｒｔｉｎＤｙｅｒ，Ａｌａｎ刚ｅ＝ｅ【１目等人发展了随机贪婪算法并对其中的一些性质做了深入的探讨．本文针对三分图上的最大匹配也提出了一个启发式算法，算法能够为随后的基于拉格朗日松弛的分支定界提供一个好的初始下界．管理决策中，匹配在所谓人员分配问题和最优分配阿题中有重要应用，
永远的谭嗣同．还有很多问题可以化归到匹配问题．
通常意义上的匹配都假定图中节点在匹配中只出现１次。如果放宽在节点上的容量约束，允许每个节点可以在匹配中重复出现多次，就变成了６一Ｍｏｔｃｈｉｎｇ问题．ＰｕｌｌｅｙＢｌａｎｋ（１９８０，１９８１）［１３】ｆ１４Ｊ对ｂ—Ｍａｃｔｈｉｎ９作了研究；ＭａｔｔｈｉａｓＭｕｌｌｅｒ．Ｈａｎｎｅｍａｎｎ，ＡｌｅｘａｎｄｅｒＳｃｈｗａｒｔｚ御咧【１５】从实现的角度进行了研究．以上的这些研究往往局限在二分图上，在管理决策中也的确出现了不少的问题可以归结到三分图上的匹配问题，笔者最近所作的项目中就出现了此类问题。在本文的第三章还会有详细的论述．一些仃公司中往往要委派一名技术人员和一名销售人员负责某一个客户的销售以及售后服务，这里面涉及到销售人员，技术人员以及客户三方的匹配，针对不同的控制目标我们可以建立不同的模型．如果规定同一个销售人员，技术人员只能负责不超过某个数目的客户，相应的问题就变成了一个三分图上的ｂ—Ｍａｔｃｈｉｎｇ问题．三分图上的匹配问题，加权匹配问
４
题，ｂ—Ｍａｔｃｈｉｎｇ问题在管理决策中也有相当广泛的应用．
三分图上的匹配问题是一种ⅣＰ难的问题【１６ｌ，就我们掌握的资料来看目前三分图上的匹配问题除了证明其为ＮＰ—ｈａｒｄ外，从算法的角度没有更为深入的研究．
从超图【－ｑ的角度看本文研究的问题，第二章所定义的基本概念“三元组”正是超图中的３一一致超边． 拉格朗日松弛方法是一种能够综合用于求解数学规划问题的方法．它往往可以将规划问题分解为若干具有特殊结构的子问题来进行有效的求解．拉格朗日松弛方法的实质就是给出原问题最优值的一个下界的方法．这与求解一个线性整数规划是用线性松弛产生问题的一个下界是一样的，但是拉格朗日松弛方法提供的下界比线性松弛方法提供的下界要好一些．我们所建立的数学模型的拉格朗日乘子问题是一个分段的线性凹函数，可以采用次梯度优化方法进行求解．本文就是针对三分图上的匹配问题提出了一种拉格朗日松弛方法，并将将拉格朗日松弛融入到分支定界结构．本文的第二章主要介绍一些基本概念，并给出了最大匹配的判断准则；第三章介绍三分图上匹配的基于拉格朗日松弛的分支定界方法；第四章介绍三分图上ｂ一匹配的基于拉格朗日松弛的分支定界方法；第五章给出了三分图上匹配的两个应用． ５
第二章基本概念
本章所涉及的图除特别声明均为无环非空图。
本章讨论的匹配问题基于三分图Ｇ＝（ＵＥ），其中ｙ可以划分为ｘ，ｙｌｚ，Ｘ＝｛２：ｉｌｉ＝ｌ，２，…，ｎ），Ｙ＝锄ｂ＝１，２，…，ｎ），Ｚ＝｛ｚｋｌｋ＝１，２，¨．，ｎ），Ｅ为边集，满足Ｘ内部的点均不相邻，此性质对ｙ＇Ｚ亦成立．记取ｙ为Ｇ由ＸＵＹ导出子图的边集，Ｅ－２为Ｇ由ＹＵＺ导出子图的边集Ｅｚｘ为Ｇ由ｚｕｘ导出子图的边集．
定义１．如果（ｚ，Ⅳ），（Ｙ，。），（Ｚ，。）∈Ｅ，ｚ∈Ｘ，Ｙ∈Ｆｚ∈Ｚ则称（。，Ｙ，ｚ）为三元组（３－ｃｌｕｓｔｅｒ）．记ｏ（ａ）为Ｇ的所有三元组组成的集合．
定义２．三元组的运算．三元组的交（ｎ）、并（Ｕ）和差（＼）等运算等同于视三元组为子图所对应的运算，运算结果为—子图．例如，在图２，１．ｏ中（２；２，Ｙ２，Ｚ２）ｎ（。２，Ｙ３，幻）＝（｛ｚ２，ｚ２）；“￡２，幻）））．
定义３．不与任何三元组关联的边称为冗余边（ｒｅｄｕｎｄａｎｔｅｄｇｅ），例如，图２．１．ｇ中（２：３Ａ）即为Ｇ的冗余边．
硫酸铝钾
由于这里考虑的是匹配，跟三元组相关，删除冗余边对我们的问题没有实质性的改变，删除冗余边的算法如下；
步骤１：Ｒ＋一圣
步骤２：ｄｅｚ＋＿ｌ，如果Ｅ≠圣，任取ｅ∈Ｅ，否则转步骤４。
情形ｌ：ｅ∈ＥＸｙ，设为（。，Ⅳ），开始遍历ｚ，如果存在ｚ∈Ｚ满足（Ｙ，ｚ），（ｚ，ｚ）∈Ｅ，则令ｄｅｆ＋＿０，遍历结束后如果ｄｅｌ＝１，Ｒ÷＿引Ｊ｛ｅ）．
情形２：ｇ∈Ｅｙｚ，设为（玑＝），开始遍历ｘ，如果存在。∈Ｘ满足（ｚ，２７），（ｚ，９）∈Ｅ，则令ｄｅｊ÷＿０，遍历结束后如果ｄｅｌ＝ｌ，Ｒ＋－ＲＵＭ。
情形３ｔｅ∈Ｅｚｘ，设为（≈￡），开始遍历ｙ，如果存在９∈Ｙ满足（￥，Ⅳ），（Ⅳ，ｚ）∈日，则令ｄｅｆ＋＿０，遍历结束后如果ｄｅｌ＝１，Ｒ卜ＲＵ｛ｅ）．
步骤３；Ｅ＋．Ｅ一｛ｅ），转步骤２．
步骤４：Ｒ即为冗余边的集合．
上述删除冗余边的算法复杂度为Ｏ（ＩＥＩＩＶＩ），记Ｆ（ａ）为Ｇ删除冗余边所构成的图，以下除非特别说明，Ｇ均已经删除了冗余边．
定义４．Ⅳ∈ｄｒ（Ｇ），ａ∈ａ（Ｇ），记Ⅳ中与ｄ相邻的三元组的集合为ｎ（Ｏ，Ｎ）＝删口ｎＪ≠雪，ｄ∈Ⅳ｝，ｌｎ（ｏ，ｌｖ）ｌ称为ｄｒ在Ⅳ中的度（ｄｅｇｒｅｅ），记为ａ（ｏ，Ｎ），一
６
般地ｎ（％ａ（Ｇ））简记为ｎ（ａ）．ｏ在ｏ（ｃ）中的度也简称为一的度，记为△（∞．对于日∈ｏ（Ｇ）有△（日，Ｎ）＝ｍ—ａｘ△（以Ｎ）；上面定义了三元组的度，下面我们来定义顶点的度＂∈ＫＮ∈ｏ（Ｇ），记Ⅳ中与＂相关的三元组集合为ｒ（＂，Ｎ），ｌｒ（ｕ，Ⅳ）Ｉ称为ｕ在Ⅳ中的度（ｄｅｇｒｅｅ），记为ｄ（ｕ，Ｎ），一般地ｄ（”，ａ（Ｇ））简记为ｄ（ｕ）．ｕ在ｏ（ｅ）中的度也简称为＂的度，记为ｄ（＂）．对于ｓ￡Ｖ有ｄ（Ｓ，Ｎ）＝ｍ．ａ．ｘｄ（ｕ，Ⅳ）。
例如，图２．１．ｄ中（ｚ２，Ｙ２，Ｚ２）的度为２．
sf1995定义５．如果Ｍ≠垂，Ｍ∈ｏ（Ｇ），而且对Ｖ口，ｄ∈Ｍ均有口ｎｄ＝垂，则称Ｍ为Ｇ的匹配（ｍａｔｃｈｉｎｇ）．记ｍ（Ｇ）为Ｇ所有匹配组成的集合．
例如，在图２．１．ａ所示图中，加粗显示的三元组集｛（￥１，Ｙｌ，ｚ１），（Ｘ２，Ｙ３渤））为该图的一个匹配．
彳．＞附ｊ八ｊ＼越涤ｙ
Ｙ１．●
彳＞对。下＼烬涤ｒ
图２．１．ａ图２．１－ｂ
根据ａ（Ｇ）和匹配的定义不难得出；
命题１．ａ（Ｇ）＝ＵＭ．
Ｍｅｒｅ（ｅ）
定义６．Ｇ中与Ｍ中三元组关联的顶点称为Ｍ饱和点（ｓａｔｕｒａｔｅｄｖｅｒｔｅｘ），反
中华奇石网之称为非Ｍ饱和点．设ｗＳｘＵｙＵＺ。若Ⅳ中每点都是Ｍ饱和点．则称Ｍ
饱和Ⅳ．Ｇ中与Ｍ中的三元组关联的边称为Ｍ饱和边（ｓａｔｕｒａｔｅｄｅｄｇｅ）．
定义７．若Ｍ饱和ｘＵｙＵｚ。则称Ｍ为Ｇ的完美匹配（ｐｅｒｆｅｃｔｍａｔｃｈｉｎｇ）．
定义８．Ｍ为Ｇ的匹配，若对Ｇ的任何匹配Ｍ’均有『Ｍ’ＩＳＪＭｌ，则称Ｍ为Ｇ
的最大匹配（ｍａｘｉｍｕｍｍａｔｃｈｉｎｇ）．
显然，每个完美匹配都是最大匹配，反之不一定．
由于这些概念均与边的方向无关，所以我们只须讨论无向图中的匹配问题．图２．１．口以及图２．１．ｂ中所示的匹配｛（。１，Ｙｌ，ｚ１），（。２，Ｙ３，砘））和｛（。ｌ，ｖｌ，ｚ１），（如，舶，幻），（。３，Ｙ２，Ｚ３））分别是该图的最大匹配和完美匹配．
７
下面定义交错三元组系列和增广三元组系列．
定义９．设Ｍ和Ｍ’是Ｇ的两个不相交的非空匹配，ｏ（Ｇ）的连通子集￡为Ｇ中（Ｍ，Ｍ７）交错三元组系列（ａｌｔｅｒｎａｔｉｎｇ３－ｃｌｕｓｔｅｒｓｅｒｉａｌｓ）是指Ｅ的元素在Ｍ和Ｍ’中交替出现（指如果三元组属于Ｍ，则与之相邻的三元组属于Ｍ’，如果三元组属于Ｍ’，则与之相邻的三元组属于Ｍ），Ｅ中每个点的度不超过２并且满足：对Ｖ口∈Ｅ若有口∈矾ｄＣｖ，Ｅ）＝１则不存在一∈ＭＵＭ’＼Ｅ使得＂∈一．（Ｍ，Ｍ’）交错三元组系列也简称为Ｍ交错三元组系列，其中Ｍ『＝ｏ（Ｇ）＼Ｍ．如果还满足ｌ｛ｏ．１０∈∑，口∈Ｍ）ｌ＜Ｉ｛口Ｉ口∈Ｅ，口∈口（Ｇ）一Ｍ）ｌ，则称Ｅ为Ｍ增广三元组系列（ａｕｇｍｅｎｔｉｎｇ３－ｃｌｕｓｔｅｒｓｅｒｉａｌｓ）．2012年中央1号文件
piv图３
图３中Ｍ＝（０＂２，口６），Ｍ’＝｛Ｏ＂１，Ｏ．５，Ｏ．７，Ｏ＂８），则｛０＂２，０＂６，口１，０＂５，口７，观）是（Ｍ，Ｍｒ）交错三元组系列，也是Ｍ交错三元组系列以及增广三元组系列．
引理１．设Ｍ和Ｍ’为Ｇ的两个不同的非空匹配。Ｈ＝ＭｏＭ’＝ＭＵＭ，一ＭｎＭ’，则Ｈ的每个连通分支必是下列两种类型之一：
Ｊ．孤立三元组．
２．（Ｍ，Ｍ７）交错三元组系列．
证明设尸是Ｈ的任意一个连通分支，若Ｐ为一孤立三元组，则１成立．否则Ｐ的每个顶点的度必然小于或等于２（否则，必然有一个顶点在Ｍ或者Ｍ’中出现两次，与匹配的定义矛盾），而且Ｐ中相邻的三元组必然分属于Ｍ和Ｍ７，由此可知２成立．
命题２．Ｍ为Ｇ的最大匹配的充分必要条件是Ｇ中不存在Ｍ增广三元组系列．
证明（辛）设Ｍ是Ｇ的最大匹配，并且设日为Ｍ增广三元组系列．则令Ｍ’＝Ｍｏ（ｏＩ口∈日），由增广三元组的定义可知Ｍ７为Ｇ的匹配而且ＩＭ，ｌ＞ＩＭＩ，
８
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议