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

《匹配理论及其应用-毕业论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、目录1引言12匹配理论12.1图的概念12.2匹配的相关定义22.3匹配定理33匹配理论的应用83.1相关算法介绍83.1.1匈牙利算法83.1.2算法103.2应用的两种常见类型113.2.1人员安排问题113.2.2最优安排问题134大学生就业现状分析164.1大学生就业一般过程模型164.2大学生就业过程的特点174.3关于大学生就业现状和成因的研究175匹配理论及其在大学生就业市场中的应用176结束语23参考文献24致谢2524匹配理论及其应用Xxxxxx系本xxxxx班xxxxxx指导教师：xx

2、xxxxx摘要：本文将从匹配理论的基础知识及其基本应用着手，通过对大学生就业现状进行分析，将大学生的应聘问题转化为图论中的最优匹配问题，从而根据匹配理论的相关知识来解决最优匹配问题。利用匹配理论的知识达到解决大学生就业问题的目的。关键词：图论，匹配理论，大学生。MatchingtheoryanditsapplicationLixxxxxxxClassxxxx，MathematicsDepartmentTutor：xxxxxxxxxxxxAbstract:Thispaperwilladoptthebasic

3、knowledgeandbasicapplicationofmatchingtheory,whichtranslatethejobrecruitmentofcollegestudentsintotheoptimalgraphmatchingproblemofgraphtheorythroughtheanalysisoftheemploymentstatus,sothattoresloveoptimalmatchingproblemaccordingtotherelevantknowledgeofmatch

4、ingtheory.Therefore,usethematchingtheorytoresolvetheemploymentproblemofcollegegraduates.Keywords:graphtheory,matchingtheory,collegestudents.241引言目前，大学生就业难已经成为中国一个十分突出的问题。中国经济增长保持了良好的态势，能够持续不断地提供就业岗位。大学生是就业群体中能力和素质较高的群体，应是中国就业群体中最具有竞争力的，应不会出现大面积的就业困难。然而现实并

5、非如此。“毕业即失业”已经成为普遍现象。匹配是图论的一个重要内容。匹配理论很好的描述了市场中双向选择的情形，解释了一个市场能稳定存在的根源，并为我们对各种市场进行设计建立合理的市场机制提供了可行的选择。因而利用匹配理论的知识对大学生就业市场的研究具有重大的意义。2匹配理论2.1图的概念我们所讨论的图与人们通常所熟悉的图，例如圆、椭圆，函数图形等是很不相同的。所谓图是指有序三元组，其中非空称为顶点集，称为边集，而是到中元素有序对或无序对簇的函数，称为关联函数。中元素称为顶点，中的元素称为边，刻画了边与顶点之

6、间的关联联系。若中元素全是有序对，则称为有向图，记为.若中的元素全是无序对，则称为无向图，记为.图论中大多数定义和概念是根据图的图形表示提出来的。例如边与它的两端点称为关联的；与同一条边相关联的两端点或者与同一个顶点相关联的两条边称为相邻的。两端点相同的边称为环。若无环图的顶点集可以划分为两个非空子集和使得中任何两顶点之间无边相连并且中任何两顶点之间也无边相连，则称该图为二分图，称为二部划分。从上面的讨论中可以看到，图的本质内容是顶点和边之间的关联联系，至于顶点和边是否用平面上的几何点和线段来表示，则完全

7、是不必要的，换句话说，图的概念可以抽象化。24定义设和是图的顶点子集，使,且的每一条边的每一个端点在中，另一个端点在中，则称为二分图（。记作：.如果中的顶点与中的每个顶点都相联，则成为完全二分图。若，（符号表示集合中元素的个数），则完全二分图记作.图的顶点集分成两个子集和的分划，称为的二分划。2.2匹配的相关定义定义1设是无环非空图，是的非空子集，若中任何两条边在中均不相邻，则称为的匹配。例如，在图2.2.1所示图中，粗边所示的边集是该图的一个匹配。中与中边关联的顶点称为饱和点。反之，称为非饱和点。设.若

8、中每点都是饱和点，则称饱和.若饱和，则称为的完备匹配。若对的任何匹配均有，则称为的最大匹配。显然，每个完备匹配都是最大匹配。如图2.2.1中粗边表示的匹配分别是该图的最大匹配和完备匹配。(图2.2.1）定义2可增广道路设是图的一个匹配，是的一条路，且在中，的边和的边交替出现，则称是的一条交错路。若交错路24的两个端点为非饱和点，则称为可增广路。例如，图2.2.2所示图中，虚线所示为匹配，则是一条交错路，而是一条可增广路。（图2