目录
1引言 (1)
2 匹配理论 (1)
2.1图的概念 (1)
2.2匹配的相关定义 (2)
2.3匹配定理 (3)
3 匹配理论的应用 (8)
3.1相关算法介绍 (8)
3.1.1匈牙利算法 (8)
算法 (10)
3.1.2Kuhn Munkres
3.2应用的两种常见类型 (11)
3.2.1人员安排问题 (11)
3.2.2 最优安排问题 (13)
4 大学生就业现状分析 (16)
4.1大学生就业一般过程模型 (16)
4.2大学生就业过程的特点 (17)
4.3关于大学生就业现状和成因的研究 (17)
5 匹配理论及其在大学生就业市场中的应用 (17)
6 结束语 (23)
参考文献 (24)
致谢 (25)
i
匹配理论及其应用
Xxxxxx系本xxxxx班 xxxxxx
指导教师： xxxxxxx
摘要：本文将从匹配理论的基础知识及其基本应用着手，通过对大学生就业现状进行分析，将大学生的应聘问题转化为图论中的最优匹配问题，从而根据匹配理论的相关知识来解决最优匹配问题。利用匹配理论的知识达到解决大学生就业问题的目的。
关键词：图论，匹配理论，大学生。
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.
1
1引言
目前，大学生就业难已经成为中国一个十分突出的问题。中国经济增长保持了良好的态势，能够持续不断地提供就业岗位。大学生是就业群体中能力和素质较高的群体，应是中国就业群体中最具有竞争力的，应不会出现大面积的就业困难。然而现实并非如此。“毕业即失业”已经成为普遍现象。
匹配是图论的一个重要内容。匹配理论很好的描述了市场中双向选择的情形，解释了一个市场能稳定存在的根源，并为我们对各种市场进行设计建立合理的市场机制提供了可行的选择。因而利用匹配理论的知识对大学生就业市场的研究具有重大的意义。
2 匹配理论
2.1 图的概念
我们所讨论的图()graph 与人们通常所熟悉的图，例如圆、椭圆，函数图形等是很不相同的。所谓图是指有序三元组(),,V E ?，其中V 非空称为顶点集，E 称为边集，而?是E 到V 中元素有序对或无序对簇的函数，称V V ?为关联函数。V 中元素称为顶点，E 中的元素称为边，?刻画了边与顶点之间的关联联系。若V V ?中元素全是(),,V E ?有序对，则(),,V E ?称为有向图，记为()()(),,D D V D E D ?=.若V V ?中的元素全是无序对，则(),,V E ?称为无向图，记为()()(),,G G V G E G ?=.
图论中大多数定义和概念是根据图的图形表示提出来的。例如边与它的两端点称为关联的；与同一条边相关联的两端点或者与同一个顶点相关联的两条边称为相邻的。两端点相同的边称为环。若无环图的顶点集可以划分为两个非空子集X 和Y 使得X 中任何两顶点之间无边相连并且Y 中任何两顶点之间也无边相连，则称该图为二分图，{}Y X ,称为二部划分。
从上面的讨论中可以看到，图的本质内容是顶点和边之间的关联联系，至于顶点和边是否用平面上的几何点和线段来表示，则完全是不必要的，换句话说，图的概念可以抽象化。
定义 设1V 和2V 是图G 的顶点子集，使1212(),V V V G V V ==? ,且G 的每一条边的每一个端点在1V 中，另一个端点在2V 中，则称G 为二分图（()bipartitegrph 。记作：12(,;)G V V E =.
如果1V 中的顶点与2V 中的每个顶点都相联，则成为完全二分图。若
12,V m V n ==，（符号V 表示集合V 中元素的个数），则完全二分图记作,m n K . 图G 的顶点集()V G 分成两个子集1V 和2V ()()1212,V V V G V V ==? 的分划()12,V V ，称为G 的二分划()bipartition 。
2.2 匹配的相关定义
定义1 设D 是无环非空图，M 是)(D E 的非空子集，
若M 中任何两条边在D 中均不相邻，则称M 为D 的匹配。例如，在图2.2.1所示图中，粗边所示的边集是该图的一个匹配。D 中与M 中边关联的顶点称为M 饱和点。反之，称为M 非饱和点。设)(D V X ?.
若X 中每点都是M 饱和点，则称M 饱和X .若M 饱和)(D V ，则称M 为D 的完备匹配。若对D 的任何匹配M '均有M M ≤'，则称M 为D 的最大匹配。显然，每个完备匹配都是最大匹配。
如图2.2.1中粗边表示的匹配分别是该图的最大匹配和完备匹配。
x
1x 2x 3x 4x 5y 1y 2y 3y 4y 5
x
1x 2x 3x 4x 5
y 1y 2y 3y 4y 5
(图2.2.1）
定义2 M 可增广道路
设M 是图G 的一个匹配，P 是G 的一条路，且在P 中，M 的边和()E G M - 的边交替出现，则称P 是G 的一条M 交错路。若M 交错路P 的两个端点为M 非
饱和点，则称P 为M 可增广路。
例如，图2.2.2所示图中，虚线所示为匹配M ，则()2457910,,,,,V V V V V V 是一条M 交错路，而()124578,,,,,V V V V V V 是一条M 可增广路。
V 1V 2
V 4
V 7V 5V 3
V 9V 8V 10V 6
（图2.2.2）
定理 2.2.1 G 的一个匹配M 是最大匹配的充要条件是G 不包含M —增广道路。
证明 设M 是G 的一个匹配，并设G 包含一条M —增广道路0121m V V V + ，设M M '=()()(){}()()(){}1,23,421,22,32,21,,,m m m m V V V V V V V V V V -+ ,
显然，()M E G '∈,且M '是G 的一个匹配，因为1M M '>+，所以M 不是最大匹配。反之，假设M 不是最大匹配，且令M '是G 的一个最大匹配，那么M M '>.(2.2.1)
设H 是由M M ⊕导出的G 的子图，那么H 的每个顶点在H 中具有的度数不是1就是2.因为它最多只能和一条M 的边以及M '的边关联。因此，H 的每个分支或是一条边在M 和M '中交错的偶回路，或是一条边在M 和M '中交错的道路。由式(2.2.1)，H 包含的M '的边多于M 的边，因而必定有H 的一条道路P 开始于M '的边且终止于M '的边。故在H 中被M '所饱和的P 的起点和终点在图G 中就是M —不饱和的，于是P 是G 的一条M —增广道路。
2.3匹配定理
本节介绍Berge ，Hall ，Konig ，Tutte 关于匹配理论的四个基本定理。需要
用到符号A ○
-B ，定义A ○-B =()()A B A B - ，其中A 与B 是集合，称A ○-B
为A 与B 的对称差，因为A ○
-B =B ○-A ，有时把A ○-B 写成A ⊕B . 定理1 （Berge ,1957） M 是图G 中的一个最大匹配当且仅当G 中无M 的可增广轨。
证明 若M 中无M 的可增广轨，但M 不是G 的最大匹配，即G 中另有一匹
配M '，M '的边数比M 的边数多，考虑G 的子图G G '=[M ○
-M '].由于M 与M '是匹配, M 中的边两两无公共端点，M '亦然，所以G '中顶的次数不是1就是2.于是G '的连通片必为其边在M 与M '中交替出现的圈，不然就是边在M 与
M '中交替出现的轨；又M 与M '的边数不同，M M '>，由○
-的定义，G '中来自M '的边比来自M 的边多。于是G 的某个连通片必为以M '中的边为起止边的轨(),p u v ，(),p u v 是M 的可增广轨，与假设G 中无M 可增广轨矛盾，至此证得M 是G 的最大匹配。
反之，若M 是G 的最大匹配，显然G 中无M 可增广轨，不然M 还可以改造成边数更多的匹配，与M 是最大匹配相违。证毕。
定理 2 (Hall ,1935) 设G 是二分图，顶集的二分图划分为X 与Y ，即(),V G X Y X Y ==? , X 中无邻顶对，Y 中亦然；存在把X 中顶皆许配的充要条件是任意s X ∈，皆有()N s s ≥，其中()N s 是S 中每个顶的邻顶组成的所谓S 的邻集。
证明 若任意的S X ?，皆有()N s s ≥，但G 中无把X 中顶皆许配的匹配，如图2.3.1所示。设M '是G 的一个最大匹配，当然M '也不能把X 中的顶皆许配。设V 是一个未被M '许配的X 中顶，令A 是被M '的交错轨与V 连通的集合。由定理1，V 是A 中的唯一的未被M '许配的顶，不然M '中有可增广轨，与M '是最大匹配相违。令S A X = ，于是()N s A Y = ,且()1N s s =-，与假设任意S X ?，皆与()N s s ≥相违，至此证出充分性。
s 个顶
T =N (S
)V
(图2.3.1)
必要性的证明 设有把X 中顶皆许配的匹配，任意的S X ?，则S 的顶亦皆被许配，与S 中顶相配的顶的个数是s ，又与S 中顶相配的顶皆在S 的邻集中，故()N s s ≥，证毕。
定理2就是图论中著名的Hall 婚配定理。
1935年，有人向Hall 提出如下问题：城中每位小伙子都结识k 位姑娘，每位姑娘都结识k 位小伙子，1k ≥。问这些未婚青年是否皆可与自己的意中人结婚？
Hall 把上述问题化成下面的图论模型：令小伙子集合为X ，姑娘集合为Y ，仅当甲小伙子与乙姑娘结识时，在甲与乙两顶之间连一边，构成一个k 次正则二分图，k 次()1k ≥正则二分图中存在完备匹配吗？
Hall 由定理2推导出下面推论，从而肯定地回答了上述“与意中人结婚”的问题。 推论 k 次正则二分图有完备匹配，0k >。
证明 设X 与Y 是k 次正则二分图G 的顶划分,X 中无邻顶对，Y 中亦然， 则()G k X k Y ω== ，0k >.从而X Y =.,S X S ??≠? ，显然
()k S k N S ≤ .因为与S 中的顶无关联的每条边有一个端点在()N S 中，于是得()S N S ≤ ；由定理2知G 中有把X 中顶皆许配的的匹配，又X Y = ，所以G 中有完备匹配。证毕。
定理3 (Konig ,1931) 若G 是二分图，则其最大的匹配的边数为()G β.
证明 设M 是二分图G 的最大匹配，X 与Y 是二分图的顶划分。若M 把X 中的一切顶皆许配，则M X =，这时X 显然是G 的一个最小覆盖,因为覆盖住M 中的边至少用M 个顶。故这种情况下，成立()M X G β==.若M 未把X 中顶皆许配，设X '是X 中未被M 许配的顶组成的集合，见图2.3.2.令Z 是有M 的交错轨与X '中顶连通的顶之集合，即,S Z X T Z Y == ，则()N s T =.取()B X S T =- .B 由图2.3.2中“黑顶” 们组成，则B 是G 的一个覆盖集。事实上，如果B 不是G 的覆盖集，则至少存在一条边()e E G ∈，e 的一端在S 中，另一端在Y T -中，即e 的每两个端点皆“白顶” ，此与()N s T =矛盾。又M B =，而G 中任一匹配M '，皆有()M G β'≤，()M G β≤，即()B G β≤，故B 是G 的最小覆盖，至此证明出最大匹配中边的条数等于()G β.证毕。 x -s
s x'
（图2.3.2）
定理4 (Tutte ,1947)图G 有完备匹配当且仅当任意的：
()S V G ?，()O G S S -≤，其中()O G S -是G S -中奇数个顶的连通片的个数。
证明 设任意()S V G ?，()O G S S -≤，而G 中无完备匹配，令G '是有如下性质的图：(ⅰ)G 是G '的生成子图；(ⅱ)G '是无完备匹配而边数最多的单图，于是G S -是G S '-的生成子图，因而：()()O G S O G S S '-≤-≤.令S =?，则()0O G '≤，即()0O G '=，从而G '的顶数是偶数。
令U 是G '中()1V G '-次顶的集合。由G '之定义，U ≠?，若()U V G '=，则
G '中有完备匹配，这不可能。所以U 是()V G '的真子集。下面证明G U '-是不相交的完全图之并。反证之，若G U '-的某个连通片不是完全图，则在该连通片中，
存在顶,,x y z ，使得,()x y y z E G '∈，而()xz E G '?.又y U ?，所以存在
()w V G U '∈-，使得()yw E G '∈，由于G '是没有完备匹配的()V G 个顶的边数
最多的图，故任意()e E G '∈，G e '+中有完备匹配。令1M 与2M 分别是G xz '+与G yw '+中的完备匹配。又令H 为12M M ⊕，在G xz yw '++中的导出图，则H 的每顶皆两次，H 是一些无公共边的偶图之并。这是由于其上1M 与2M 的边交替
出现。如下图所示，其中粗实线是1M 的边，虚线是2M 的边。
(1)xz 与yw 在H 的不同连通片内，若yw 在H 的圈1C 上，如图(a)所示，那么1M 在1C 上的边与2M 不在1C 上的边构成G '的完备匹配，与G '之定义矛盾。 x
z y
w
图(a )
(2)xz 与yw 在H 的同一个圈2C 上，如图(b )所示这时在2C 上yw z 部分上1M 的与yz 以及2M 不在yw z 部分的边构成G '的一个完备匹配，矛盾。 C 2
y
z w 图(b )
由(1)与(2)知G U '-是不相交的完全图之并。由于()O G U U '-≤，
G U '-中奇数个顶的连通片至多U 个，但G '中有了完备匹配M 。
这个匹配M 把G U '-的每个奇数项的连通片的一个顶许配给U 的一个顶，
U 与G U '-的连通片的其余的顶与U 中或本连通片中其余的顶相配，
注意G U '-的每个连通片皆完全图，如图c 所示。而这与G '中无完备匹配矛盾，证毕。 G'-U 的奇片U
G'-U 的偶片
(图c)
3 匹配理论的应用
3.1相关算法介绍
3.1.1 匈牙利算法
在匹配的应用问题中，常常需要给出定图的最大匹配。本节给出一个有效算法，它是由匈牙利数学家埃德蒙兹(1931年)首先提出来的，故通常称为“匈牙利算法”。
匈牙利算法的基本思想较简单。设G 是具有二部划分()12,V V 的二分图，从图G 的任意匹配M 开始。若M 饱和 ，则M 是G 的最大匹配。若M 不能饱和1V ，则在1V 中选择一个非M 饱和点 。若G 中存在以x 为起点的M 可增广路P ，则M M P '=⊕就是比M 更大的匹配，利用M '代替M ，并重复这个过程，若G 中
不存在以x 为起点的M 可增广路，则令H 是根在x 的M 交错子图的顶点集，并令12,S H V T H V == .再由定理1可知()G N S T =，且G 中不存在以x 为起点的M 可增广路，此时称x 为检验过的非M 饱和点，对1V 中其它未检验过的非M 饱和点重复这个过程，直到1V 中的所有的非M 饱和点全部检验过为止。当整个过程结束时，由于G 中不存在M 可增广路，从而M 为G 的最大匹配。
匈牙利算法：
设G 是具有二部划分()12,V V 的二分图。连通的二分图，在G 中任取初始匹配M ；
(1)若M 把X 中顶皆许配，止，M 即G 的最大匹配；否则取X 中未被M 许配的顶u ，令{},S u T ==?；
(2)若()N S T =，止，G 中无完备匹配；否则取()y N S T ∈-；
(3)若y 被M 许配，设yz M ∈，{}S S z ← ，{}T T y ← ，转(3)；否则可取增广轨(),P u y ，令()M M E P ←⊕，转(2)。
显然Hungarian 算法是根据定理2.3.1设计出来的，通过可增广轨把一个小匹配逐次增广而得最大匹配乃至完备匹配（如果存在的话）。如图3.1.1中初始匹配为{}223355,,M x y x y x y =，取未被M 许配的顶1x X ∈，取1y Y ∈，1y 未被M 许配的顶11,x X y Y ∈∈,1y 未被M 许配。得可增广轨1221x y x y .令
(){}1122112213355,,,M M E x y x y x y x y x y x y =⊕=.
搜索可增广轨的具体过程如图3.1.2所示，它显示了图3.1.1中1x 为根的外向交错树（树上从1x 出发的轨皆M 的交错轨），即一个非匹配边一个匹配边交替出现的生长过程，最后得到了可增广轨1221x y x y ，即图3.1.2右侧最高那一条轨。
x 1x
2x 3x 4x 5
y 1y 2y 3y 4y 5
（图3.1.1） y 2x 1y 2x 1x 2y 2x 1x 2y 3x 1y 2
x 2y 3x 3y 2x 1y 3x 2
x 3
(图3.1.2)
3.1.2 Kuhn Munkres -算法
求加权完全二分图(),,n n K w 中最大权完备匹配方法。
定理 设l 是G 的可行标点符号。若l 等子图l G 有完备匹配M *是G 的最大权完备匹配。
(1)从任意可行顶点标号(例如平凡标号) l 开始，确定l 等子图l G ，并且在l G 中选取匹配，并由定理3.1.1知M 是最优匹配，算法停止，否则转入第2步。
(2)匈牙利算法终止于S 属于X ，T Y ?，使()l G N S T =.
计算l G ，确定的可行标点符号l ，并以l 替代l ，以G 替代l G 转入第1步。
注(1) Kuhn Munkres -算法是有效算法。
注(2) 最大权完备匹配不是唯一的。
注(3) Kuhn Munkres -可以用来求(),,n n K w 中最小权完备匹配。
3.2 应用的两种常见类型
匹配问题是运筹学的重要问题之一，也是图论的重要内容，它在所谓的“人员分配问题”和“最优分配问题”中有重要应用。
3.2.1 人员安排问题
某公司准备安排n 个职员12n x x x 从事12n y y y .假设每个职员能胜任其中
一项或几项工作。试问：能否把所有职员都安排一项他所能胜任的工作？这个问题称为人员安排问题。
对于此类问题，接下来构造二部划分为{},x y 的简单二分图G ，其中
{}{}1212,n n X x x x Y y y y == ，
并且()i j x y E G ∈?职员i x 胜任工作j y ，于是问题转化为判定给定的二分图G 中是否具有完备匹配问题。
设M 和M '是()E G 的两个不相交的非空真子集。G 中(),M M '交错路是指
其边在M 和M '中交错出现的路。(),M M 交错路简称为M 交错路，其中
()\M E G M = .设M 是G 的匹配，两端点不同且都是非M 饱和的M 交错路称为M -增广路。
引理3.2.1 设M 和M *是G 的两个不同的非空匹配，H G M M *??=???，则H
的每个连通分支必是下列三种类型之一：（ⅰ）孤立点；（ⅱ）(),M M *交错偶圈；（ⅲ）(),M M *交错路。
证明 由于H 中每个顶点至多与M 和M *中一条边关联，所以()02H ≤?≤。而且对H 中顶点x ，若()2H d x =?x 既与M 中一条关联，又与M *一条边关联。
设P 是H 中任意一个连通分支。设P 是一个孤立点，则（ⅰ）成立。下设()12P ≤?≤.若P 中顶点全是2度点，则由上述说明知中P 每个顶点既与M 中一条边关联，又要与M *中一条边关联，所以P 是一条(),M M *交错偶圈，故（ⅱ）成立。
若P 中含1度点，设为x ，则由推论知P 中必含另一个1度点，设为y .由于()2P ?≤，所以P 是一条以x 和y 为端点的路，P 中内部点（若存在的话）都是2度点，因而P 是(),M M *交错路，(ⅲ)成立。
定理3.2.1 设M 是二部划分为{},X Y 的二分图G 的匹配，x X ∈，是M 非饱和点，Z 是G 中由起点为x 的M 交错路所能连接的顶点集：
,S Z X T Z Y == ，
则(a )()G T N S ?；(b )下述三条等价：(ⅰ)G 中不存在以x 为短点的M -增广路；(ⅱ)x 是Z 中唯一的M 非饱和点；(ⅲ)()G T N S =且1T S =-.
证明 (a )任取y T ∈，则G 中存在以x 和y 为端点的M 交错路P .令()P z N y ∈，由于G 是二分图且y T Y ∈?，所以z Z X S ∈= ，即()G y N S ∈，因而有()G T N S ?.
(b )(ⅰ)?(ⅱ)（反证法）设y 是Z 中异于x 的M 非饱和点，则G 中存在以x 和y 为端点的M 交错路P ，P 是G 中以x 为端点的M 增广路P ，并设P 的另一端点为()y x ≠，则y 是M 非饱和点，由Z 的定义知，y Z ∈，矛盾于(ⅱ)的假定，所以(ⅰ)成立。
(ⅱ）?(ⅲ)任取()G y N S Y ∈?。于是存在u s Z X ∈= ，和()e E G ∈使()G e uy ?=，若u x =，则显然有y T ∈，下设u x ≠，于是G 中存在以x 和u 为端点的M 交错路P 。由于x 是M 非饱和点，所以u 为M 饱和点。若P 不含y ，则e M ?.由Z 的定义知，y Z Y T ∈= 。因而有()G N S T ?，再由(a )，()G T N S =.由于x 是Z 中唯一的M 非饱和点，所以T 中点全是M 饱和点。又由于X 中通过M 与T 中点配对的点全在S 中，且()G T N S =，所以{}\S x 中点与T 中点由M 配对。故有1T S =-.
(ⅲ)?(ⅱ)任意{}\z S x ∈，设P 是G 中以x 和z 为端点的M 交错路。由于G
是二分图，并且,x z X ∈，所以P 的长为偶数。又由于x 是M 非饱和点，所以z 是
M 饱和点。
由{}\z S x ∈的任意性知，{}\S x 中的点全是M 饱和点，它们与()G N S 中点由M 配成对。由于()G N S T =且1T S =-，所以T 中点全是M 饱和点，即知x 是Z 中唯一的非饱和点，(ⅱ)成立。
推论3.2.1 非空二分图有饱和所有最大度点的最大匹配。
证明 设G 是二部划分为{},X Y 的二分图，并设M 是G 中做大匹配并尽可能多地饱和最大度点。
（反证法）设存在最大度点x 是M 非饱和的。令Z 是G 中以为x 起点的M 交错路所能连通的顶点集。不妨设x X ∈，并令,S Z X T Z Y == .由于M 是G 的最大匹配，所以由Berge 定理知G 中不存在以x 为起点的M 增广路。再由定理
3.2.1知1T S =-，且()G N S T =.若S 中的点全是最大度点，则
()()(),G G u s u T
S d u S T d u T ∈∈?===≤?∑∑， 即有1S T S ≤=-，矛盾。于是，S 中存在非最大度点，设为z ，则z x ≠，令11211m m m P xe x e e x e z --= 是G 中M 交错路，由于,x z Z ∈，所以m 为偶数。又因为
x 是M 非饱和点，
所以131,,m e e e M -? ，而24,,m e e e M ∈ ，因而可以看出z 是M 的饱和点。于是令:
(){}(){}24131\m m M M E P M e e e e e e -'=?= ， 则M M '=,即M '是G 中最大匹配，但M '饱和最大度点的数目比M 的饱和最大度点的数目至少多一个（即x ），矛盾于M 的选取。
3.2.2 最优安排问题
在上一节中，我们利用匈牙利算法解决了人员安排问题，针对那个问题，已知每个职员能胜任其中一项或几项工作，试问怎样安排，才能使尽量多的人有工作可做同时使尽量多的工作有人胜任？
构造具有二部划分()12,V V 的简单二分图G ，其中：
{}{}112212,n n V x x x V y y y == ，
并且边()(),i j x y E G ∈?职员i x 胜任工作j y ，于是问题转化为求给定二分图G 的最大匹配。
我们知道，这种分配方案可能不止一种，或者说职员做各项工作，熟练程度、工作效率等未必一致。因此要制定一个分工方案，使得人尽其才，且公司的总效益最大。这样就要考察具有二部划分()12,V V 的加权二分图(),,n n K w ，其中{}112,,n V x x x = ，{}212,,n V y y y = ，边{},i j x y 上的权(),i j w x y 表示职员i x 做工作j y 的效率。于是，问题等价于在这个加权图(),,n n K w 中求一个总权最大的完备匹配，我们称这种安排为最优安排问题。
当然，若枚举所有的n !个完备匹配，然后比较它们的权，这种方法无疑是可以的。但是当n 很大时，这种方法显然是无效的。这就要用到前面的K u h n Mu n kr es -这种有效的算法。
定义 已知G 是具有二部划分()12,V V 的完全加权二分图，映射():l V G R →，满足对G 的每条边{},e x y =，均有()()(),l x l y w x y +≥，其中(),w x y 表示边{},x y 的权，则l 称为G 的可行顶标。令{}{}()()()(){},,,,l E x y x y E G l x l y w x y =∈+=，l G 为以l E 为边集的G 的生成子图，则称l G 为l 等子图。
可行顶标是存在的，例如()()()212
max ,0y V l x w x y V l y y V ∈?=∈??=∈??
这种可行顶标称为平凡标号。
定理3.2.2 设l 是G 的可行顶标。若l 等子图l G 有完备匹配M *，那么M *是G 的最大权完备匹配。（即最优匹配）
证明 由于l G 是G 的生成子图，M *是l G 的完备匹配。又由于对每个e 属于M *都属于这个l 等子图l G ，而且M *中每条边覆盖每个顶点正好一次。所以()()()x V
e M w M w e l x **∈∈=
=∑∑。 另一方面，对G 的任何完备匹配M ，有()()()x V
e M w M w e l x *∈∈=
≤∑∑，于是有()()w M w M *≥，即M *是G 的最大权完备匹配。
例 已知完全二分图5,5K ，其中{}112345,,,,V x x x x x =，{}212345,,,,V y y y y y =，且5,5K 的权矩阵为A ，求5,5K 的最优匹配。
3554122022244100
11001
2133A ????????=????????
解 (1)取可行顶标l 如下： ()()()()()
()()()()()()()()()()1234512345max 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 y l y l y l y l y l x l x l x l x l x ============== （2）取l G 及l G 的匹配如图3.2.2(a)所示。由于()23O G x -=，故l G 中无完备匹配，则需修改顶标。
x 1x 2x
3x 4x 5
y 1y 2y 3y 4y 5
图3.2.2(a)
(3)4x x =，得{}{}()41323,,,,,l
G S x x x T y y N S T ===,于是：
()()(){}2min ,,1l l x l y w x y x S y V T α=+-∈∈-=.
因而12345,,,,x x x x x 的顶标分别为4，2，3，0，3；12345,,,,y y y y y 的顶标分别为0，1，1，0，0.
(4)用修改后的顶标l '得l G '及l G '的一个匹配（虚线），如图3.2.2(b)所示。此匹配即为5,5K 的最优匹配，其总权为2+4+1+4+3=14。
当然，图G 的最优匹配未必唯一。例如上例中，完备匹配：
{}1421334255,,,,M x y x y x y x y x y '=
的权也为14，显然也是上例中的5,5K 的最优匹配。
x 1x 2x 3x 4x 5
y 1y 2y 3y 4y 5
图3.2.2（b ） 4 大学生就业现状分析
从经济学的角度讲，毕业生就业问题是毕业生劳动力市场供给和需求在具有一定特征的劳动力市场上相互作用的结果。大学生就业具有一定的特殊性，并且任何一个国家在高等教育逐步推广和普及的过程中都会面临大学毕业生就业问题的考验。因此，近年来对大学生就业问题的研究得到了各界的重视。
4.1 大学生就业一般过程模型
个体完成前期的学习后，将决定是接受高等教育，还是进入其他就业过程（不同于大学生的就业过程）。如果决定接受高等教育，则需要参加高考，拟定报考志愿，随后面临多次筛选(例如是否达到高考录取分数线，是否被大学录取，是否接受调剂，是否入学等)。结果是个体要么进入大学学习，继续本章的就业过程，要么退出这个就业过程。大学学习阶段也将有人退出这个就业过程.(例如退学，出国，参军，毕业后考研等)，余下的选择就业的个体则成了我们通常所关注的大学生求职群体。有些个体会在一段时间内坚持求职与考研两手抓，一面求职一面考研，以增加自己选择的余地。如果考取研究生，我们就认为这个个体已经退出了本章所谓的就业过程。但是，通常的做法是学校会把考取研究生或以其他方式不参加求职过程的学生视为已经就业，而在初次就业率中有所体现。大部分学生在毕业以前就已经开始搜寻企业（或用人单位）发出的招聘信息；获得了用人信息后，对这些信息进行比较，选择出符合自身要求的用人单位，并对其发
出求职申请；在获得用人单位肯定回复后，双方进入面试和求职谈判阶段，当双方达成一致后，由学生、用人单位和学校三方签订《大学生就业协议》；然后是学生毕业参加工作，与用人单位签订正式《劳动合同》。在这个过程中，如果在任一阶段双方未能达成一致，学生都有可能重新开始求职过程或双方退回到更前面的阶段进行协商。例如，学生和用人单位在讨价还价阶段未能达成一致，双方将继续协调或结束该过程，从而学生需要重新搜索用人单位，开始新的求职过程。
4.2 大学生就业过程的特点
由于大学生就业过程包括的元素多，时间跨度比较长（一般为3-5年），因此可以从多个角度总结这个过程的特点。以下是对大学生就业有重要影响的几个特点。
4.3 关于大学生就业现状和成因的研究
关于大学生就业现状的研究主要集中在三个方面：①对大学生就业的整体形势的分析；②关于大学生择业观的研究；③关于大学生就业过程中劳动力市场分隔、性别歧视、社会资本，以及其它歧视现象等的研究。各种类型的歧视和不可竞争性因素对大学生就业的影响非常突出。
5 匹配理论及其在大学生就业市场中的应用
例题1 2014年，忻州师范学院急需招聘5位各科教师，有不同专业的5名师范专业毕业的学生前来应聘。将这五名毕业生记作12345,,,,x x x x x ；五种学科分别记作12345,,,,y y y y y ；这五位毕业生所能胜任的课程如(图5.1.1)所示。试问如何分配使得所有的应聘人员都找到心仪的工作，且空缺的职位均有人胜任？
x 1
x 2
x 3
x 4
x 5y 1y 2y 3y
4y 5
(图5.1.1)
分析 该题属于求最大匹配的情形，可以根据匈牙利算法求得此结果。
解 构造一个二分图G ，()V E X Y = ,,X Y 是G 的二分图的顶划分，其中，{}{}1234512345,,,,,,,,,X x x x x x Y y y y y y ==，仅当i x 可以胜任学科j y 时，在顶i x 与j y 之间连一条边，如此构成一个应聘图G ，接下来利用匈牙利算法求得该二分图的最大匹配。
具体解法如下：
第一步：给初始匹配{}113553,,M x y x y x y =.如图(5.1.2)所示，属于匹配M 的边用实线，其余用虚线；
x 1
y
1x 2
y 2x 3
y 3x 4
y 4x 5y 5
（图5.1.2）
第二步：显然X 尚未饱和，找出其中一未饱和点2x ，从2x 出发经过下列过程：
{}{}{}1225253:,,,V x x x x x x →→.
{}{}{}2335352:,,,V y y y y y y ?→→→.
从而找到为非饱和点和可增广道路（图5.1.2中箭头所示）：
235532P x y x y x y =.
作()M M E p ←⊕得新的匹配，如图(5.1.3)所示。