匹配理论及其应用-毕业论文

i 目目 录录 1 1 引言引言.1 2 2 匹配理论匹配理论.1 2.1 图的概念图的概念.1 2.2 匹配的相关定义匹配的相关定义.2 2.3 匹配定理匹配定理.3 3 3 匹配理论的应用匹配理论的应用.8 3.1 相关算法介绍相关算法介绍.8 3.1.1 匈牙利算法匈牙利算法.8 3.1.2 算法算法.10KuhnMunkres 3.2 应用的两种常见类型应用的两种常见类型.11 3.2.1 人员安排问题人员安排问题.11 3.2.2 最优安排问题最优安排问题.13 4 4 大学生就业现状分析大学生就业现状分析.16 4.1 大学生就业一般过程模型大学生就业一般过程模型.16 4.2 大学生就业过程的特点大学生就业过程的特点.17 4.3 关于大学生就业现状和成因的研究关于大学生就业现状和成因的研究.17 5 5 匹配理论及其在大学生就业市场中的应用匹配理论及其在大学生就业市场中的应用.17 6 6 结束语结束语.23 参考文献参考文献.24 致谢致谢.25 ii 匹配理论及其应用 XxxxxxXxxxxx 系本系本 xxxxxxxxxx 班班 xxxxxxxxxxxx 指导教师：指导教师： xxxxxxxxxxxxxx 摘 要：本文将从匹配理论的基础知识及其基本应用着手，通过对大学生 就业现状进行分析，将大学生的应聘问题转化为图论中的最优匹配问题，从而 根据匹配理论的相关知识来解决最优匹配问题。利用匹配理论的知识达到解决 大学生就业问题的目的。 关键词：图论，匹配理论，大学生。 Matching theory and its application Li xxxxxxx Class xxxx，Mathematics Department Tutor：xxxxxxxxxxxx Abstract: This paper will adopt the basic knowledge and basic application of matching theory, which translate the job recruitment of college students into the optimal graph matching problem of graph theory through the analysis of the employment status, so that to reslove optimal matching problem according to the relevant knowledge of matching theory. Therefore, use the matching theory to resolve the employment problem of college graduates. Key words: graph theory ,matching theory ,college students. 0 1 引言 目前，大学生就业难已经成为中国一个十分突出的问题。中国经济增长保 持了良好的态势，能够持续不断地提供就业岗位。大学生是就业群体中能力和 素质较高的群体，应是中国就业群体中最具有竞争力的，应不会出现大面积的 就业困难。然而现实并非如此。 “毕业即失业”已经成为普遍现象。 匹配是图论的一个重要内容。匹配理论很好的描述了市场中双向选择的情 形，解释了一个市场能稳定存在的根源，并为我们对各种市场进行设计建立合 理的市场机制提供了可行的选择。因而利用匹配理论的知识对大学生就业市场 的研究具有重大的意义。 2 匹配理论 2.1 图的概念图的概念 我们所讨论的图与人们通常所熟悉的图，例如圆、椭圆，函数图形()graph 等是很不相同的。所谓图是指有序三元组，其中非空称为顶点集，,V EV 称为边集，而是到中元素有序对或无序对簇的函数，称为关联函EEVVV 数。中元素称为顶点，中的元素称为边，刻画了边与顶点之间的关联联VE 系。若中元素全是有序对，则称为有向图，记为VV,V E,V E .若中的元素全是无序对，则称为无向图， , D DV DE DVV,V E 记为. , G GV GE G 图论中大多数定义和概念是根据图的图形表示提出来的。例如边与它的两 端点称为关联的；与同一条边相关联的两端点或者与同一个顶点相关联的两条 边称为相邻的。两端点相同的边称为环。若无环图的顶点集可以划分为两个非 空子集和使得中任何两顶点之间无边相连并且中任何两顶点之间也无XYXY 边相连，则称该图为二分图，称为二部划分。YX, 从上面的讨论中可以看到，图的本质内容是顶点和边之间的关联联系，至 于顶点和边是否用平面上的几何点和线段来表示，则完全是不必要的，换句话 说，图的概念可以抽象化。 定义 设和是图的顶点子集，使,且的每 1 V 2 VG 1212 ( ),VVV G VV G 1 一条边的每一个端点在中，另一个端点在中，则称为二分图（ 1 V 2 VG 。记作：.()bipartitegrph 12 ( ,;)GV V E 如果中的顶点与中的每个顶点都相联，则成为完全二分图。若 1 V 2 V ， （符号表示集合中元素的个数） ，则完全二分图记作. 12 ,Vm VnVV ,m n K 图的顶点集分成两个子集和的分划G( )V G 1 V 2 V 1212 ,VVV GVV ，称为的二分划。 12 ,V VGbipartition 2.2 匹配的相关定义匹配的相关定义 定义 1 设是无环非空图，是的非空子集，若中任何两条边在DM)(DEM 中均不相邻，则称为的匹配。例如，在图 2.2.1 所示图中，粗边所示的DMD 边集是该图的一个匹配。中与中边关联的顶点称为饱和点。反之，称DMM 为非饱和点。设.M)(DVX 若中每点都是饱和点，则称饱和.若饱和，则称为XMMXM)(DVM 的完备匹配。若对的任何匹配均有，则称为的最大匹配。DD M MM MD 显然，每个完备匹配都是最大匹配。 如图 2.2.1 中粗边表示的匹配分别是该图的最大匹配和完备匹配。 x1x2x3x4x5 y1y2y3y4y5 x1x2x3x4x5 y1y2y3y4y5 (图 2.2.1） 定义 2 可增广道路M 设是图的一个匹配，是的一条路，且在中，的边和MGPGPM 的边交替出现，则称是的一条交错路。若交错路的两 E GMPGMMP 个端点为非饱和点，则称为可增广路。MPM 2 例如，图 2.2.2 所示图中，虚线所示为匹配，则是一M 2457910 ,V V V V V V 条交错路，而是一条可增广路。 M 124578 ,V V V V V VM V1 V2 V4 V7 V5 V3 V9 V8 V10 V6 （图 2.2.2） 定理 2.2.1 的一个匹配是最大匹配的充要条件是不包含增广道GMGM 路。 证明 设是的一个匹配，并设包含一条增广道路，MGGM 0121m V VV 设,MM 1,23,421,22,32,21 , mmmm V VV VVVV VVV 显然，,且是的一个匹配，因为，所以不是最 ME G M G1MM M 大匹配。反之，假设不是最大匹配，且令是的一个最大匹配，那么M M G .(2.2.1)MM 设是由导出的的子图，那么的每个顶点在中具有的度数HMMGHH 不是 1 就是 2.因为它最多只能和一条的边以及的边关联。因此，的每M M H 个分支或是一条边在和中交错的偶回路，或是一条边在和中交错M M M M 的道路。由式(2.2.1)，包含的的边多于的边，因而必定有的一条道H M MH 路开始于的边且终止于的边。故在中被所饱和的的起点和终P M M H M P 点在图中就是不饱和的，于是是的一条增广道路。GMPGM 2.3 匹配定理匹配定理 本节介绍，关于匹配理论的四个基本定理。需BergeHallKonigTutte 要用到符号，定义=，其中与是集合，称A - BA - B ABABABA 为与的对称差，因为=，有时把写成. - BABA - BB - AA - BAB 3 定理 1 （,1957） 是图中的一个最大匹配当且仅当中无BergeMGG 的可增广轨。M 证明 若中无的可增广轨，但不是的最大匹配，即中另有一MMMGG 匹配，的边数比的边数多，考虑的子图.由于 M M MGGG M - M 与是匹配, 中的边两两无公共端点，亦然，所以中顶的次数不M M M M G 是 1 就是 2.于是的连通片必为其边在与中交替出现的圈，不然就是边 G M M 在与中交替出现的轨；又与的边数不同，由的定义，M M M M MM - 中来自的边比来自的边多。于是的某个连通片必为以中的边为 G M MG M 起止边的轨，是的可增广轨，与假设中无可增广轨矛盾，,p u v,p u vMGM 至此证得是的最大匹配。 MG 反之，若是的最大匹配，显然中无可增广轨，不然还可以改MGGMM 造成边数更多的匹配，与是最大匹配相违。证毕。M 定理 2 (,1935) 设是二分图，顶集的二分图划分为与，即HallGXY , 中无邻顶对，中亦然；存在把中顶皆许配的 ,V GXY XY XYX 充要条件是任意，皆有，其中是中每个顶的邻顶组成的sX N ss N sS 所谓的邻集。S 证明 若任意的，皆有，但中无把中顶皆许配的匹配，SX N ssGX 如图 2.3.1 所示。设是的一个最大匹配，当然也不能把中的顶皆许 M G M X 配。设是一个未被许配的中顶，令是被的交错轨与连通的集合。V M XA M V 由定理 1，是中的唯一的未被许配的顶，不然中有可增广轨，与VA M M 是最大匹配相违。令，于是,且，与假 M SAX N sAY 1N ss 设任意，皆与相违，至此证出充分性。SX N ss 4 s个 个 T=N(S) V (图 2.3.1) 必要性的证明 设有把中顶皆许配的匹配，任意的，则的顶亦皆XSXS 被许配，与中顶相配的顶的个数是，又与中顶相配的顶皆在的邻集中，SsSS 故，证毕。 N ss 定理 2 就是图论中著名的婚配定理。Hall 1935 年，有人向提出如下问题：城中每位小伙子都结识位姑娘，每Hallk 位姑娘都结识位小伙子，。问这些未婚青年是否皆可与自己的意中人结k1k 婚？ 把上述问题化成下面的图论模型：令小伙子集合为，姑娘集合为，HallXY 仅当甲小伙子与乙姑娘结识时，在甲与乙两顶之间连一边，构成一个次正则k 二分图，次正则二分图中存在完备匹配吗？k1k 由定理 2 推导出下面推论，从而肯定地回答了上述“与意中人结婚”Hall 的问题。 推论 次正则二分图有完备匹配，。k0k 证明 设与是次正则二分图的顶划分,中无邻顶对，中亦然，XYkGXY 则 ，.从而. ，显然 Gk Xk Y0k XY,SX S .因为与中的顶无关联的每条边有一个端点在中，于是得 k Sk N SS N S ；由定理 2 知中有把中顶皆许配的的匹配，又 ，所以 SN SGXXY 中有完备匹配。证毕。G 定理 3 (,1931) 若是二分图，则其最大的匹配的边数为.KonigG G 5 证明 设是二分图的最大匹配，与是二分图的顶划分。若把MGXYM 中的一切顶皆许配，则，这时显然是的一个最小覆盖,因为覆XMXXG 盖住中的边至少用个顶。故这种情况下，成立.若未MM MXGM 把中顶皆许配，设是中未被许配的顶组成的集合，见图 2.3.2.令X X XM 是有的交错轨与中顶连通的顶之集合，即，则ZM X ,SZX TZY .取.由图 2.3.2 中“黑顶” 们组成，则是的一 N sTBXSTBBG 个覆盖集。事实上，如果不是的覆盖集，则至少存在一条边，BG eE G 的一端在中，另一端在中，即 的每两个端点皆“白顶” ，此与eSYTe 矛盾。又，而中任一匹配，皆有， N sTMBG M MG ，即，故是的最小覆盖，至此证明出最大匹配中边 MG BGBG 的条数等于.证毕。 G x-s s x （图 2.3.2） 定理 4 (,1947)图有完备匹配当且仅当任意的：TutteG ，其中是中奇数个顶的连通片的个数。 SV GO GSSO GSGS 证明 设任意，而中无完备匹配，令是有如( )SV GO GSSG G 下性质的图：()是的生成子图；()是无完备匹配而边数最多的单图，G G G 于是是的生成子图，因而：.令，则GSGS O GSO GSS S 6 ，即，从而的顶数是偶数。 0O G 0O G G 令是中次顶的集合。由之定义，若，U G 1V G G U UV G 则中有完备匹配，这不可能。所以是的真子集。下面证明是 G U V GGU 不相交的完全图之并。反证之，若的某个连通片不是完全图，则在该连GU 通片中，存在顶，使得，而.又，所以存在, ,x y z,()xy yzE G()xzE GyU ，使得，由于是没有完备匹配的个顶的边数wV GU ywE G G V G 最多的图，故任意，中有完备匹配。令与分别是 eE GGe 1 M 2 M 与中的完备匹配。又令为，在中的导出Gxz Gyw H 12 MMGxzyw 图，则的每顶皆两次，是一些无公共边的偶图之并。这是由于其上与HH 1 M 的边交替出现。如下图所示，其中粗实线是的边，虚线是的边。 2 M 1 M 2 M (1)与在的不同连通片内，若在的圈上，如图(a)所示，那xzywHywH 1 C 么在上的边与不在上的边构成的完备匹配，与之定义矛盾。 1 M 1 C 2 M 1 C G G x z y w 图(a) (2)与在的同一个圈上，如图(b)所示这时在上部分上xzywH 2 C 2 Cywz 的与以及不在部分的边构成的一个完备匹配，矛盾。 1 Myz 2 Mywz G C2 y z w 图(b) 7 由(1)与(2)知是不相交的完全图之并。由于，GU O GUU 中奇数个顶的连通片至多个，但中有了完备匹配。GU U G M 这个匹配把的每个奇数项的连通片的一个顶许配给的一个顶，MGU U 与的连通片的其余的顶与中或本连通片中其余的顶相配，注意UGU U 的每个连通片皆完全图，如图 c 所示。而这与中无完备匹配矛盾，证GU G 毕。 G-U个 个 个 U G-U个 个 个 (图 c) 3 匹配理论的应用 3.1 相关算法介绍相关算法介绍 3.1.1 匈牙利算法匈牙利算法 在匹配的应用问题中，常常需要给出定图的最大匹配。本节给出一个有效 算法，它是由匈牙利数学家埃德蒙兹(1931 年)首先提出来的，故通常称为“匈 牙利算法” 。 匈牙利算法的基本思想较简单。设是具有二部划分的二分图，从G 12 ,V V 8 图的任意匹配开始。若饱和 ，则是的最大匹配。若不能饱和GMMMGM ，则在中选择一个非饱和点 。若中存在以为起点的可增广路， 1 V 1 VMGxMP 则就是比更大的匹配，利用代替，并重复这个过程，若MMP M M M 中不存在以为起点的可增广路，则令是根在的交错子图的顶点集，GxMHxM 并令.再由定理 1 可知，且中不存在以为起 12 ,SHV THV G NSTGx 点的可增广路，此时称为检验过的非饱和点，对中其它未检验过的非MxM 1 V 饱和点重复这个过程，直到中的所有的非饱和点全部检验过为止。当M 1 VM 整个过程结束时，由于中不存在可增广路，从而为的最大匹配。GMMG 匈牙利算法： 设是具有二部划分的二分图。连通的二分图，在中任取初始匹G 12 ,V VG 配；M (1)若把中顶皆许配，止，即的最大匹配；否则取中未被MXMGX 许配的顶，令；Mu ,SuT (2)若，止，中无完备匹配；否则取； N STG yN ST (3)若被许配，设，转(3)；否则yMyzM SSz TTy 可取增广轨，令，转(2)。,P u y MME P 显然算法是根据定理 2.3.1 设计出来的，通过可增广轨把一个Hungarian 小匹配逐次增广而得最大匹配乃至完备匹配（如果存在的话） 。如图 3.1.1 中初 始匹配为，取未被许配的顶，取，未被 223355 ,Mx yx y x yM 1 xX 1 yY 1 y 许配的顶,未被许配。得可增广轨.令M 11 ,xX yY 1 yM 1221 x y x y . 1122112213355 ,MME x y x yx yx y x y x y 搜索可增广轨的具体过程如图 3.1.2 所示，它显示了图 3.1.1 中为根的外向交 1 x 错树（树上从出发的轨皆的交错轨） ，即一个非匹配边一个匹配边交替出 1 xM 现的生长过程，最后得到了可增广轨，即图 3.1.2 右侧最高那一条轨。 1221 x y x y 9 x1x2x3x4x5 y1y2y3y4y5 （图 3.1.1） y2 x1 y2 x1 x2 y2 x1 x2 y3 x1 y2 x2 y3 x3 y2 x1 y3 x2x3 (图 3.1.2) 3.1.2 算法算法KuhnMunkres 求加权完全二分图中最大权完备匹配方法。 , , n n Kw 定理 设 是的可行标点符号。若 等子图有完备匹配是的最大权lGl l GM G 完备匹配。 (1)从任意可行顶点标号(例如平凡标号) 开始，确定 等子图，并且在ll l G 中选取匹配，并由定理 3.1.1 知是最优匹配，算法停止，否则转入第 2 步。 l GM (2)匈牙利算法终止于属于，使.SXTY l G NST 10 计算，确定的可行标点符号 ，并以 替代 ，以替代转入第 1 步。 l Gl l lG l G 注(1) 算法是有效算法。KuhnMunkres 注(2) 最大权完备匹配不是唯一的。 注(3) 可以用来求中最小权完备匹配。KuhnMunkres , , n n Kw 3.2 应用的两种常见类型应用的两种常见类型 匹配问题是运筹学的重要问题之一，也是图论的重要内容，它在所谓的 “人员分配问题”和“最优分配问题”中有重要应用。 3.2.1 人员安排问题人员安排问题 某公司准备安排个职员从事.假设每个职员能胜任其中n 12n x xx 12n y yy 一项或几项工作。试问：能否把所有职员都安排一项他所能胜任的工作？这个 问题称为人员安排问题。 对于此类问题，接下来构造二部划分为的简单二分图，其中, x yG ，并且职员胜任工作，于是 1212 , nn Xx xxYy yy ij x yE G i x j y 问题转化为判定给定的二分图中是否具有完备匹配问题。G 设和是的两个不相交的非空真子集。中交错路是指M M E GG,M M 其边在和中交错出现的路。交错路简称为交错路，其中M M ,M M M .设是的匹配，两端点不同且都是非饱和的交错路称 ME GM MGMM 为增广路。M 引理 3.2.1 设和是的两个不同的非空匹配，则MM GHG M M 的每个连通分支必是下列三种类型之一：（）孤立点；（）交H,M M 错偶圈；（）交错路。,M M 证明 由于中每个顶点至多与和中一条边关联，所以HMM 而且对中顶点，若既与中一条关联，又与 02H Hx 2 H dx xM 一条边关联。M 设是中任意一个连通分支。设是一个孤立点，则（）成立。下PHP 11 设.若中顶点全是 2 度点，则由上述说明知中每个顶点既与 12P PP 中一条边关联，又要与中一条边关联，所以是一条交错偶圈，MM P,M M 故（）成立。 若中含 1 度点，设为，则由推论知中必含另一个 1 度点，设为.由PxPy 于，所以是一条以和为端点的路，中内部点（若存在的话） 2PPxyP 都是 2 度点，因而是交错路，()成立。P,M M 定理 3.2.1 设是二部划分为的二分图的匹配，是非M,X YGxXM 饱和点，是中由起点为的交错路所能连接的顶点集：ZGxM ，,SZX TZY 则(a)；(b)下述三条等价：()中不存在以为短点的增广 G TNSGxM 路；()是中唯一的非饱和点；()且.xZM G TNS1TS 证明 (a)任取，则中存在以和为端点的交错路.令yTGxyMP ，由于是二分图且，所以，即， P zNyGyTYzZXS G yNS 因而有. G TNS (b)()()（反证法）设是中异于的非饱和点，则中存在yZxMG 以和为端点的交错路，是中以为端点的增广路，并设的xyMPPGxMPP 另一端点为，则是非饱和点，由的定义知，矛盾于()yxyMZyZ 的假定，所以()成立。 (）()任取。于是存在，和使 G yNSYusZX eE G ，若，则显然有，下设，于是中存在以和为端 G euyuxyTuxGxu 点的交错路。由于是非饱和点，所以为饱和点。若不含，则MPxMuMPy .由的定义知，。因而有，再由(a)，eMZyZYT G NST .由于是中唯一的非饱和点，所以中点全是饱和点。又 G TNSxZMTM 由于中通过与中点配对的点全在中，且，所以中点XMTS G TNS Sx 12 与中点由配对。故有.TM1TS ()()任意，设是中以和为端点的交错路。由于 zSxPGxzM 是二分图，并且，所以的长为偶数。又由于是非饱和点，所以G, x zXPxM 是饱和点。由的任意性知，中的点全是饱和点，它们zM zSx SxM 与中点由配成对。由于且，所以中点全是 G NSM G NST1TST 饱和点，即知是中唯一的非饱和点，()成立。MxZ 推论 3.2.1 非空二分图有饱和所有最大度点的最大匹配。 证明 设是二部划分为的二分图，并设是中做大匹配并尽可G,X YMG 能多地饱和最大度点。 （反证法）设存在最大度点是非饱和的。令是中以为起点的xMZGx 交错路所能连通的顶点集。不妨设，并令.由于MxX,SZX TZY 是的最大匹配，所以由定理知中不存在以为起点的增广路。MGBergeGxM 再由定理 3.2.1 知，且.若中的点全是最大度点，则1TS G NSTS ， , GG u su T SduS TduT 即有，矛盾。于是，中存在非最大度点，设为，则，令1STSSzzx 是中交错路，由于，所以为偶数。又因 1 1 211mmm Pxe x eexe z GM, x zZm 为是非饱和点，所以，而，因而可以看出xM 131 , m e eeM 24 , m e eeM 是的饱和点。于是令:zM ， 2 41 31 mm MM E PMe eeeee 则,即是中最大匹配，但饱和最大度点的数目比的饱和最MM M G M M 大度点的数目至少多一个（即） ，矛盾于的选取。xM 3.2.2 最优安排问题最优安排问题 在上一节中，我们利用匈牙利算法解决了人员安排问题，针对那个问题， 已知每个职员能胜任其中一项或几项工作，试问怎样安排，才能使尽量多的人 13 有工作可做同时使尽量多的工作有人胜任？ 构造具有二部划分的简单二分图，其中： 12 ,V VG ， 112212 , nn Vx xxVy yy 并且边职员胜任工作，于是问题转化为求给定二分图 , ij x yE G i x j y 的最大匹配。G 我们知道，这种分配方案可能不止一种，或者说职员做各项工作，熟练程 度、工作效率等未必一致。因此要制定一个分工方案，使得人尽其才，且公司 的总效益最大。这样就要考察具有二部划分的加权二分图，其中 12 ,V V , , n n Kw ，边上的权表示职员做工 112 , n Vx xx 212 , n Vy yy, ij x y, ij w x y i x 作的效率。于是，问题等价于在这个加权图中求一个总权最大的完 j y , , n n Kw 备匹配，我们称这种安排为最优安排问题。 当然，若枚举所有的个完备匹配，然后比较它们的权，这种方法无疑是n! 可以的。但是当很大时，这种方法显然是无效的。这就要用到前面的n 这种有效的算法。KuhnMunkres 定义 已知是具有二部划分的完全加权二分图，映射，G 12 ,V V : l V GR 满足对的每条边，均有，其中表示边G,ex y ,l xl yw x y,w x y 的权，则 称为的可行顶标。令, x ylG ，为以为边集的的生成子 , l Ex yx yE Gl xl yw x y l G l EG 图，则称为 等子图。 l Gl 可行顶标是存在的，例如 2 1 2 max, 0 y V l xw x yV l yyV 这种可行顶标称为平凡标号。 定理 3.2.2 设 是的可行顶标。若 等子图有完备匹配，那么是lGl l GM M 的最大权完备匹配。 （即最优匹配）G 证明 由于是的生成子图，是的完备匹配。又由于对每个 e 属于 l GGM l G 14 都属于这个 等子图，而且中每条边覆盖每个顶点正好一次。所以M l l GM 。 x V e M w Mw el x 另一方面，对的任何完备匹配，有，于是GM x V e M w Mw el x 有，即是的最大权完备匹配。 w Mw M M G 例 已知完全二分图，其中， 5,5 K 112345 ,Vx x x x x ，且的权矩阵为，求的最优匹配。 212345 ,Vy yyyy 5,5 KA 5,5 K 35541 22022 24410 01100 12133 A 解 (1)取可行顶标 如下：l 12345 1 2 3 4 5 max 3,5,5,4,15 max 2,2,0,2,22 max 2,4,4,1,04 max 0,1,1,0,01 max 1,2,1,3,33 l yl yl yl yl y l x l x l x l x l x （2）取及的匹配如图 3.2.2(a)所示。由于，故中无完 l G l G 2 3O Gx l G 备匹配，则需修改顶标。 x1x2 x3x4x5 y1y2y3y4y5 图 3.2.2(a) (3)，得,于是： 4 xx 41323 , l G Sx x xTyyNST 15 . 2 min,1 l l xl yw x y xS yVT 因而的顶标分别为 4，2，3，0，3；的顶标分别为 12345 ,x x xx x 12345 ,y yyyy 0，1，1，0，0. (4)用修改后的顶标得及的一个匹配（虚线） ，如图 3.2.2(b)所示。此 l l G l G 匹配即为的最优匹配，其总权为 2+4+1+4+3=14。 5,5 K 当然，图的最优匹配未必唯一。例如上例中，完备匹配：G 1421334255 ,Mx yx y x y x yx y 的权也为 14，显然也是上例中的的最优匹配。 5,5 K x1x2x3x4x5 y1y2y3y4y5 图3.2.2（b） 4 大学生就业现状分析 从经济学的角度讲，毕业生就业问题是毕业生劳动力市场供给和需求在具 有一定特征的劳动力市场上相互作用的结果。大学生就业具有一定的特殊性， 并且任何一个国家在高等教育逐步推广和普及的过程中都会面临大学毕业生就 业问题的考验。因此，近年来对大学生就业问题的研究得到了各界的重视。 4.1 大学生就业一般过程模型大学生就业一般过程模型 个体完成前期的学习后，将决定是接受高等教育，还是进入其他就业过程 （不同于大学生的就业过程） 。如果决定接受高等教育，则需要参加高考，拟定 报考志愿，随后面临多次筛选(例如是否达到高考录取分数线，是否被大学录取， 是否接受调剂，是否入学等)。结果是个体要么进入大学学习，继续本章的就业 过程，要么退出这个就业过程。大学学习阶段也将有人退出这个就业过程.(例 如退学，出国，参军，毕业后考研等)，余下的选择就业的个体则成了我们通常 16 所关注的大学生求职群体。有些个体会在一段时间内坚持求职与考研两手抓， 一面求职一面考研，以增加自己选择的余地。如果考取研究生，我们就认为这 个个体已经退出了本章所谓的就业过程。但是，通常的做法是学校会把考取研 究生或以其他方式不参加求职过程的学生视为已经就业，而在初次就业率中有 所体现。大部分学生在毕业以前就已经开始搜寻企业（或用人单位）发出的招 聘信息；获得了用人信息后，对这些信息进行比较，选择出符合自身要求的用 人单位，并对其发出求职申请；在获得用人单位肯定回复后，双方进入面试和 求职谈判阶段，当双方达成一致后，由学生、用人单位和学校三方签订大学 生就业协议 ；然后是学生毕业参加工作，与用人单位签订正式劳动合同 。 在这个过程中，如果在任一阶段双方未能达成一致，学生都有可能重新开始求 职过程或双方退回到更前面的阶段进行协商。例如，学生和用人单位在讨价还 价阶段未能达成一致，双方将继续协调或结束该过程，从而学生需要重新搜索 用人单位，开始新的求职过程。 4.2 大学生就业过程的特点大学生就业过程的特点 由于大学生就业过程包括的元素多，时间跨度比较长（一般为 3-5 年） ，因 此可以从多个角度总结这个过程的特点。以下是对大学生就业有重要影响的几 个特点。 4.3 关于大学生就业现状和成因的研究关于大学生就业现状和成因的研究 关于大学生就业现状的研究主要集中在三个方面：对大学生就业的整体 形势的分析；关于大学生择业观的研究；关于大学生就业过程中劳动力市 场分隔、性别歧视、社会资本，以及其它歧视现象等的研究。各种类型的歧视 和不可竞争性因素对大学生就业的影响非常突出。 5 匹配理论及其在大学生就业市场中的应用 例题 1 2014 年，忻州师范学院急需招聘 5 位各科教师，有不同专业的 5 名 师范专业毕业的学生前来应聘。将这五名毕业生记作；五种学科 12345 ,x x x x x 分别记作；这五位毕业生所能胜任的课程如(图 5.1.1)所示。试问 12345 ,y yyyy 如何分配使得所有的应聘人员都找到心仪的工作，且空缺的职位均有人胜任？ 17 x1 x2 x3 x4 x5 y1 y2 y3 y4 y5 (图 5.1.1) 分析 该题属于求最大匹配的情形，可以根据匈牙利算法求得此结果。 解 构造一个二分图，,是的二分图的顶划分，其中，G V EXY,X YG ，仅当可以胜任学科时，在顶与 1234512345 ,Xx x x x xYy yyyy i x j y i x 之间连一条边，如此构成一个应聘图，接下来利用匈牙利算法求得该二分 j yG 图的最大匹配。 具体解法如下： 第一步：给初始匹配.如图(5.1.2)所示，属于匹配 113553 ,Mx y x y x yM 的边用实线，其余用虚线； x1y1 x2y2 x3y3 x4y4 x5y5 （图 5.1.2） 第二步：显然尚未饱和，找出其中一未饱和点，从出发经过下列过X 2 x 2 x 程： . 1225253 :,Vxx xx x x . 2335352 :,Vyyyyyy 18 从而找到为非饱和点和可增广道路（图 5.1.2 中箭头所示）： . 235532 Px y x y x y 作得新的匹配，如图(5.1.3)所示。( )MME p x1y1 x2y2 x3y3 x4y4 x5y5 (图 5.1.3) 第三步：未饱和，若为非饱和点，从点出发经过下列过程：X 4 x 4 x ，:,Vxx xx x xx x x x . 23323253254 :,Vyyyyyyyyyy 从而得到非饱和点，以及从到的一条可增广道路： 4 y 4 x 4 y . 43223554 Px y x y x y x y 作：得新的匹配，如（图 5.1.4）所示。( )MME P M x1 y1 x2y2 x3y3 x4y4 x5 y5 （图 5.1.4） 第四步：已全部饱和，故结束。X 例题 2 某单位因业务扩大需要招聘五位各部门的经理。已知有五位毕业生 19 去应聘该单位，并且知道这五位毕业生做这五项工作的利润矩阵为： 57763 44044 46630 03300 34355 C 求如何分配，可以使得该公司获利最大？ 分析 此题考虑了利润的信息，属于求最优匹配的情形，基本思想是按一定 的办法修改标号，使得和：l 1 n ij i l xl y 不断下降，直到给出问题的解为止。标号 的唯一要求是：l ，2，。 ijij l xl yc,1i j n 解 (1)给初始标号： 11 22 33 44 55 12345 maxmax 5,7,7,6,37, maxmax(4,4,0,4,4)4, maxmax 4,6,6,3,06, maxmax 0,3,3,0,03, maxmax 3,4,3,5,55, 0 j j j j j j j j j j l xc l xc l xc l xc l xc l yl yl yl yl y 如图（5.2.1）所示。 l x l y (7) x1y1 (0) (4) x2y2 (0) (6) x3y3 (0) (3) x4 y4 (0) (5) x5 y5 (0) (图 5.2.1) 20 (2) 在标号 下得：l . 121321222425323342435455 , l Ex yx y x y x yx yx y x yx y x yx y x yx y (3)用匈牙利算法求(图 5.2.2)的最大匹配。匹配的边用实线给出。 l x l y (7) x1y1 (0) (4) x2y2 (0) (6) x3 y3 (0) (3) x4 y4 (0) (5) x5 y5 (0) (图 5.2.2) (4)未饱和，. 4 x 142 ,VxV . 1231233 , ll VVyVVy xM 所以，. 14323 ,Vx xVy 1221221 , ll VVyP VVyxM 所以. 143123212 , l Vx x xVyyVV （5） 12145 ,VVy yy . 1 1,4,5 12 1,3,4 minmin1 i j y P VV j ijijijij xVi l xl ycl xl yc （6）重新标号： ， 134 7 16,6 15,1 10l xl xl x . 23 0 11,0 11l yl y (7)在新的标号 下，