匹配理论及其应用㊣精品文档值得下载

生就业现状和成因的研究关于大学生就业现状的研究主要集中在三个方面对大学生就业的整体形势的分析关于大学生择业观的研究关于大学生就业过程中劳动力市场分隔性别歧视社会资本，以及其它歧视现象等的研究。

各种类型的歧视和不可竞争性因素对大学生就业的影响非常突出。

匹配理论及其在大学生就业市场中的应用例题年，忻州师范学院急需招聘位各科教师，有不同专业的名师范专业毕业的学生前来应聘。

将这五名毕业生记作五种学科分别记作这五位毕业生所能胜任的课程如图所示。

试问如何分配使得所有的应聘人员都找到心仪的工作，且空缺的职位均有人胜任图分析该题属于求最大匹配的情形，可以根据匈牙利算法求得此结果。

解构造个二分图，是的二分图的顶划分，其中，，，仅当可以胜任学科时，在顶与之间连条边，如此构成个应聘图，接下来利用匈牙利算法求得该二分图的最大匹配。

具体解法如下第步给初始匹配如图所示，属于匹配的边用实线，其余用虚线图第二步显然尚未饱和，找出其中未饱和点，从出发经过下列过程，，从而找到为非饱和点和可增广道路图中箭头所示作得新的匹配，如图所示。

图第三步未饱和，若为非饱和点，从点出发经过下列过程，从而得到非饱和点，以及从到的条可增广道路作得新的匹配，如图所示。

图第四步已全部饱和，故结束。

例题单位因业务扩大需要招聘五位各部门的经理。

已知有五位毕业生去应聘该单位，并且知道这五位毕业生做这五项工作的利润矩阵为求如何分配，可以使得该公司获利最大分析此题考虑了利润的信息，属于求最优匹配的情形，基本思想是按定的办法修改标号，使得和不断下降，直到给出问题的解为止。

标号的唯要求是，。

解给初始标号，如图所示。

图在标号下得，用匈牙利算法求图的最大匹配。

匹配的边用实线给出。

图未饱和，，，所以，，所以，，重新标号，，在新的标号下，增加了条边，减少条边，如图所示。

图在新的标号下，存在，已饱和，，，由于，存在，而且非饱和，故存在条可增广道路作得图图已饱和，是最优匹配。

从而即可得出所求结果。

上述研究成果为本课题的进步研究提供了创新思路，与西方国家相比，我国对大学生就业问题的研究主体之间还没有个明确的分工。

这些研究虽取得定的成果，但是在系统性和科学性方面尚有待进步地深入，并且需要更多的实证研究来支撑和检验理论研究的成果。

鉴于上述分析，本文对匹配理论及其应用问题的研究无论在现实方面还是理论方面都具有重要的意义。

结束语在计算机科学蓬勃发展的刺激下，图论也获得了个很大的空间。

其中，匹配理论是比较热门的内容。

数学知识与日常生活息息相关，针对大学生招聘问题，可以根据匹配理论的知识建立匹配模型，从而实现大学生与职业的最优匹配。

参考文献张成双边匹配理论及其在我国大学应届毕业生劳动力市场的应用华南理工大学石莹搜寻匹配理论与中国劳动力市场经济学动态梁清园双边匹配理论在我国自主招生择校机制中的应用华南理工大学应松宝我国大学生就业过程研究西南交通大学，朱宁洁劳动力市场与大学毕业生人力资本投资决策生产力研究窦艳芬我国高等教育大众化过程中毕业生就业问题研究天津大学曾湘泉变革中的就业环境与中国大学生就业经济研究刘辉，焦建国劳动力市场搜寻与匹配理论当代财经宋紫峰，石光稳定匹配理论的发展及在我国的应用前景中国经济时报致谢首先在本人的写作过程中，老师给予了大力的帮助和指导，在此深表感谢，在整个写作过程中她给了我很大的帮助，在论文题目制定时，她首先肯定了我的题目大方向，但是同时又帮我具体分析使我最后选择大学生就业这个具有研究意义的具体目标，让我在写作时有了具体方向。

在论文开题报告制定时，我的思路不是很清晰，经过老师的帮忙，让我具体写作时思路顿时清晰。

在完成初稿后，老师认真查看了我的文章，指出了我存在的很多问题。

在此十分感谢的细心指导，才能让我顺利完成毕业论文。

最后要感谢在整个论文写作过程中帮助过我的每位人。

感谢他们陪我路走来，给我支持和信心。

谨向我的父母和家人表示诚挚的谢意。

他们是我生命中永远的依靠和支持，他们无微不至的关怀，是我前进的动力他们的殷殷希望，激发我不断前行。

没有他们就没有我，我的点滴成就都来自他们。

本论文的完成远非终点，文中的不足和浅显之处则是我新的征程上个个新的起点。

奇数个顶的连通片的个数。

证明设任意，，而中无完备匹配，令是有如下性质的图ⅰ是的生成子图ⅱ是无完备匹配而边数最多的单图，于是是的生成子图，因而令，则，即，从而的顶数是偶数。

令是中次顶的集合。

由之定义，，若，则中有完备匹配，这不可能。

所以是的真子集。

下面证明是不相交的完全图之并。

反证之，若的个连通片不是完全图，则在该连通片中，存在顶，使得，，而又，所以存在，使得，由于是没有完备匹配的个顶的边数最多的图，故任意，中有完备匹配。

令与分别是与中的完备匹配。

又令为，在中的导出图，则的每顶皆两次，是些无公共边的偶图之并。

这是由于其上与的边交替出现。

如下图所示，其中粗实线是的边，虚线是的边。

与在的不同连通片内，若在的圈上，如图所示，那么在上的边与不在上的边构成的完备匹配，与之定义矛盾。

图与在的同个圈上，如图所示这时在上部分上的与以及不在部分的边构成的个完备匹配，矛盾。

图由与知是不相交的完全图之并。

由于，中奇数个顶的连通片至多个，但中有了完备匹配。

这个匹配把的每个奇数项的连通片的个顶许配给的个顶，与的连通片的其余的顶与中或本连通片中其余的顶相配，注意的每个连通片皆完全图，如图所示。

而这与中无完备匹配矛盾，证毕。

的奇片的偶片图匹配理论的应用相关算法介绍匈牙利算法在匹配的应用问题中，常常需要给出定图的最大匹配。

本节给出个有效算法，它是由匈牙利数学家埃德蒙兹年首先提出来的，故通常称为匈牙利算法。

匈牙利算法的基本思想较简单。

设是具有二部划分，的二分图，从图的任意匹配开始。

若饱和，则是的最大匹配。

若不能饱和，则在中选择个非饱和点。

若中存在以为起点的可增广路，则就是比更大的匹配，利用代替，并重复这个过程，若中不存在以为起点的可增广路，则令是根在的交错子图的顶点集，并令，再由定理可知，且中不存在以为起点的可增广路，此时称为检验过的非饱和点，对中其它未检验过的非饱和点重复这个过程，直到中的所有的非饱和点全部检验过为止。

当整个过程结束时，由于中不存在可增广路，从而为的最大匹配。

匈牙利算法设是具有二部划分，的二分图。

连通的二分图，在中任取初始匹配若把中顶皆许配，止，即的最大匹配否则取中未被许配的顶，令，若，止，中无完备匹配否则取若被许配，设，，，转否则可取增广轨令，转。

显然算法是根据定理设计出来的，通过可增广轨把个小匹配逐次增广而得最大匹配乃至完备匹配如果存在的话。

如图中初始匹配为，取未被许配的顶，取，未被许配的顶，，未被许配。

得可增广轨令，搜索可增广轨的具体过程如图所示，它显示了图中为根的外向交错树树上从出发的轨皆的交错轨，即个非匹配边个匹配边交替出现的生长过程，最后得到了可增广轨，即图右侧最高那条轨。

图图算法求加权完全二分图中最大权完备匹配方法。

定理设是的可行标点符号。

若等子图有完备匹配是的最大权完备匹配。

从任意可行顶点标号例如平凡标号开始，确定等子图，并且在中选取匹配，并由定理知是最优匹配，算法停止，否则转入第步。

匈牙利算法终止于属于，，使计算，确定的可行标点符号，并以替代，以替代转入第步。

注算法是有效算法。