1、i目 录1 引言 .12 匹配理论 .12.1 图的概念 .12.2 匹配的相关定义 .22.3 匹配定理 .33 匹配理论的应用 .83.1 相关算法介绍 .83.1.1 匈牙利算法 .83.1.2 算法 .10KuhnMkres3.2 应用的两种常见类型 .113.2.1 人员安排问题 .113.2.2 最优安排问题 .134 大学生就业现状分析 .164.1 大学生就业一般过程模型 .164.2 大学生就业过程的特点 .174.3 关于大学生就业现状和成因的研究 .175 匹配理论及其在大学生就业市场中的应用 .176 结束语 .23参考文献 .24致谢 .25ii匹配理论及其应用Xxx
2、xxx 系本 xxxxx 班 xxxxxx指导教师： xxxxxxx摘 要：本文将从匹配理论的基础知识及其基本应用着手，通过对大学生就业现状进行分析，将大学生的应聘问题转化为图论中的最优匹配问题，从而根据匹配理论的相关知识来解决最优匹配问题。利用匹配理论的知识达到解决大学生就业问题的目的。关键词：图论，匹配理论，大学生。Matching theory and its applicationLi xxxxxxxClass xxxx，Mathematics DepartmentTutor：xxxxxxxxxxxxAbstract: This paper will adopt the basic k
3、nowledge 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 matchin
4、g theory. Therefore, use the matching theory to resolve the employment problem of college graduates.Key words: graph theory ,matching theory ,college students.01 引言目前，大学生就业难已经成为中国一个十分突出的问题。中国经济增长保持了良好的态势，能够持续不断地提供就业岗位。大学生是就业群体中能力和素质较高的群体，应是中国就业群体中最具有竞争力的，应不会出现大面积的就业困难。然而现实并非如此。 “毕业即失业”已经成为普遍现象。匹配是图论
5、的一个重要内容。匹配理论很好的描述了市场中双向选择的情形，解释了一个市场能稳定存在的根源，并为我们对各种市场进行设计建立合理的市场机制提供了可行的选择。因而利用匹配理论的知识对大学生就业市场的研究具有重大的意义。2 匹配理论2.1 图的概念我们所讨论的图 与人们通常所熟悉的图，例如圆、椭圆，函数图形()graph等是很不相同的。所谓图是指有序三元组 ，其中 非空称为顶点集，,VE称为边集，而 是 到 中元素有序对或无序对簇的函数，称 为关联函EEVV数。 中元素称为顶点， 中的元素称为边， 刻画了边与顶点之间的关联联V系。若 中元素全是 有序对，则 称为有向图，记为,.若 中的元素全是无序对，
6、则 称为无向图，,DDEV,VE记为 .GGV图论中大多数定义和概念是根据图的图形表示提出来的。例如边与它的两端点称为关联的；与同一条边相关联的两端点或者与同一个顶点相关联的两条边称为相邻的。两端点相同的边称为环。若无环图的顶点集可以划分为两个非空子集 和 使得 中任何两顶点之间无边相连并且 中任何两顶点之间也无XY Y边相连，则称该图为二分图， 称为二部划分。YX,从上面的讨论中可以看到，图的本质内容是顶点和边之间的关联联系，至于顶点和边是否用平面上的几何点和线段来表示，则完全是不必要的，换句话说，图的概念可以抽象化。定义 设 和 是图 的顶点子集，使 ,且 的每1V2G1212(),VGV
7、1一条边的每一个端点在 中，另一个端点在 中，则称 为二分图（1V2VG。记作： .()bipartegh2(,;)GE如果 中的顶点与 中的每个顶点都相联，则成为完全二分图。若12， （符号 表示集合 中元素的个数） ，则完全二分图记作 .12,VmnV ,mnK图 的顶点集 分成两个子集 和 的分划G()1V21212,VG，称为 的二分划 。12, biparton2.2 匹配的相关定义定义 1 设 是无环非空图， 是 的非空子集，若 中任何两条边在DM)(DEM中均不相邻，则称 为 的匹配。例如，在图 2.2.1 所示图中，粗边所示的边集是该图的一个匹配。 中与 中边关联的顶点称为 饱
8、和点。反之，称为 非饱和点。设 .M)(VX若 中每点都是 饱和点，则称 饱和 .若 饱和 ，则称 为MX)(DVM的完备匹配。若对 的任何匹配 均有 ，则称 为 的最大匹配。DD显然，每个完备匹配都是最大匹配。如图 2.2.1 中粗边表示的匹配分别是该图的最大匹配和完备匹配。x1x2x3x4x5y1y2y3y4y5x1x2x3x4x5y1y2y3y4y5(图 2.2.1）定义 2 可增广道路M设 是图 的一个匹配， 是 的一条路，且在 中， 的边和GPGPM的边交替出现，则称 是 的一条 交错路。若 交错路 的两E P个端点为 非饱和点，则称 为 可增广路。M2例如，图 2.2.2 所示图中
9、，虚线所示为匹配 ，则 是一M2457910,V条 交错路，而 是一条 可增广路。 M124578,VV1V2V4 V7V5V3 V9V8 V10V6（图 2.2.2）定理 2.2.1 的一个匹配 是最大匹配的充要条件是 不包含 增广道GMGM路。证明 设 是 的一个匹配，并设 包含一条 增广道路 ，G012mV设 ,M1,23,421, 2,32,1mmVVV 显然， ,且 是 的一个匹配，因为 ，所以 不是最EG M大匹配。反之，假设 不是最大匹配，且令 是 的一个最大匹配，那么.(2.2.1)设 是由 导出的 的子图，那么 的每个顶点在 中具有的度数HMH不是 1 就是 2.因为它最多只
10、能和一条 的边以及 的边关联。因此， 的每 H个分支或是一条边在 和 中交错的偶回路，或是一条边在 和 中交错 M的道路。由式(2.2.1)， 包含的 的边多于 的边，因而必定有 的一条道路 开始于 的边且终止于 的边。故在 中被 所饱和的 的起点和终P HP点在图 中就是 不饱和的，于是 是 的一条 增广道路。GMPG2.3 匹配定理本节介绍 ， ， ， 关于匹配理论的四个基本定理。需BergHalKonigTute要用到符号 ，定义 = ，其中 与 是集合，称A - -BABAA为 与 的对称差，因为 = ，有时把 写成 . - - - - B3定理 1 （ ,1957） 是图 中的一个最
11、大匹配当且仅当 中无BergMGG的可增广轨。M证明 若 中无 的可增广轨，但 不是 的最大匹配，即 中另有一匹配 ， 的边数比 的边数多，考虑 的子图 .由于 M - 与 是匹配, 中的边两两无公共端点， 亦然，所以 中顶的次数不G是 1 就是 2.于是 的连通片必为其边在 与 中交替出现的圈，不然就是边G 在 与 中交替出现的轨；又 与 的边数不同， ，由 的定义，M M -中来自 的边比来自 的边多。于是 的某个连通片必为以 中的边为 G起止边的轨 ， 是 的可增广轨，与假设 中无 可增广轨矛盾，,puv, M至此证得 是 的最大匹配。 G反之，若 是 的最大匹配，显然 中无 可增广轨，
12、不然 还可以改造成边数更多的匹配，与 是最大匹配相违。证毕。M定理 2 ( ,1935) 设 是二分图，顶集的二分图划分为 与 ，即HalGXY, 中无邻顶对， 中亦然；存在把 中顶皆许配的,VGXYXY充要条件是任意 ，皆有 ，其中 是 中每个顶的邻顶组成的sNsNsS所谓 的邻集。S证明 若任意的 ，皆有 ，但 中无把 中顶皆许配的匹配，SXsGX如图 2.3.1 所示。设 是 的一个最大匹配，当然 也不能把 中的顶皆许MGM配。设 是一个未被 许配的 中顶，令 是被 的交错轨与 连通的集合。VAV由定理 1， 是 中的唯一的未被 许配的顶，不然 中有可增广轨，与A 是最大匹配相违。令 ，
13、于是 ,且 ，与假 SXNsY1Ns设任意 ，皆与 相违，至此证出充分性。SXNs4s个T=N(S)V(图 2.3.1)必要性的证明 设有把 中顶皆许配的匹配，任意的 ，则 的顶亦皆XSX被许配，与 中顶相配的顶的个数是 ，又与 中顶相配的顶皆在 的邻集中，Ss故 ，证毕。Ns定理 2 就是图论中著名的 婚配定理。Hal1935 年，有人向 提出如下问题：城中每位小伙子都结识 位姑娘，每l k位姑娘都结识 位小伙子， 。问这些未婚青年是否皆可与自己的意中人结k1k婚？把上述问题化成下面的图论模型：令小伙子集合为 ，姑娘集合为 ，Hal XY仅当甲小伙子与乙姑娘结识时，在甲与乙两顶之间连一边，构
14、成一个 次正则k二分图， 次 正则二分图中存在完备匹配吗？k1由定理 2 推导出下面推论，从而肯定地回答了上述 “与意中人结婚”al的问题。推论 次正则二分图有完备匹配， 。k 0k证明 设 与 是 次正则二分图 的顶划分, 中无邻顶对， 中亦然，XYkGXY则 ， .从而 . ，显然G0Y,S.因为与 中的顶无关联的每条边有一个端点在 中，于是得kSNS NS；由定理 2 知 中有把 中顶皆许配的的匹配，又 ，所以XXY中有完备匹配。证毕。定理 3 ( ,1931) 若 是二分图，则其最大的匹配的边数为 .KonigGG5证明 设 是二分图 的最大匹配， 与 是二分图的顶划分。若 把MGXY
15、M中的一切顶皆许配，则 ，这时 显然是 的一个最小覆盖,因为覆XG盖住 中的边至少用 个顶。故这种情况下，成立 .若 未M把 中顶皆许配，设 是 中未被 许配的顶组成的集合，见图 2.3.2.令X是有 的交错轨与 中顶连通的顶之集合，即 ，则ZM,SZXTY.取 . 由图 2.3.2 中“黑顶 ” 们组成，则 是 的一NsTBSTBBG个覆盖集。事实上，如果 不是 的覆盖集，则至少存在一条边 ，GeE的一端在 中，另一端在 中，即 的每两个端点皆“白顶” ，此与eYe矛盾。又 ，而 中任一匹配 ，皆有 ，NsTMBM，即 ，故 是 的最小覆盖，至此证明出最大匹配中边G的条数等于 .证毕。 x-
16、ssx（图 2.3.2）定理 4 ( ,1947)图 有完备匹配当且仅当任意的：TuteG， ，其中 是 中奇数个顶的连通片的个数。SVGOSOSG证明 设任意 ， ，而 中无完备匹配，令 是有如()VG下性质的图：() 是 的生成子图；() 是无完备匹配而边数最多的单图， 于是 是 的生成子图，因而： .令 ，则GS OGSS6，即 ，从而 的顶数是偶数。0OG0G令 是 中 次顶的集合。由 之定义， ，若 ，U1VUVG则 中有完备匹配，这不可能。所以 是 的真子集。下面证明 是 VU不相交的完全图之并。反证之，若 的某个连通片不是完全图，则在该连通片中，存在顶 ，使得 ，而 .又 ，所以
17、存在,xyz,()xyzEG()xzEy，使得 ，由于 是没有完备匹配的 个顶的边数wVGUw VG最多的图，故任意 ， 中有完备匹配。令 与 分别是ee1M2与 中的完备匹配。又令 为 ，在 中的导出xzy H12xzyw图，则 的每顶皆两次， 是一些无公共边的偶图之并。这是由于其上 与H 1的边交替出现。如下图所示，其中粗实线是 的边，虚线是 的边。2M12(1) 与 在 的不同连通片内，若 在 的圈 上，如图(a) 所示，那xzywywH1C么 在 上的边与 不在 上的边构成 的完备匹配，与 之定义矛盾。1C21CGGxzyw图(a)(2) 与 在 的同一个圈 上，如图(b)所示这时在
18、上 部分上xzywH2C2Cywz的与 以及 不在 部分的边构成 的一个完备匹配，矛盾。1M2z GC2yzw图(b)7由(1)与(2)知 是不相交的完全图之并。由于 ，GUOGU中奇数个顶的连通片至多 个，但 中有了完备匹配 。GUM这个匹配 把 的每个奇数项的连通片的一个顶许配给 的一个顶，M与 的连通片的其余的顶与 中或本连通片中其余的顶相配，注意的每个连通片皆完全图，如图 c 所示。而这与 中无完备匹配矛盾，证 G毕。G-U个个个UG-U个个个(图 c)3 匹配理论的应用 3.1 相关算法介绍3.1.1 匈牙利算法在匹配的应用问题中，常常需要给出定图的最大匹配。本节给出一个有效算法，它是由匈牙利数学家埃德蒙兹(1931 年)首先提出来的，故通常称为“匈牙利算法” 。匈牙利算法的基本思想较简单。设 是具有二部划分 的二分图，从G12,V
