匹配理论及其应用.doc

目 录 1引言 1 2 匹配理论 1 2.1 图的概念 1 2.2 匹配的相关定义 2 2.3匹配定理 3 3 匹配理论的应用 8 3.1相关算法介绍 8 3.1.1匈牙利算法 8 3.1.2 算法 10 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 匹配理论及其应用 Xxxxxx系本xxxxx班 xxxxxx 指导教师： xxxxxxx 摘 要：本文将从匹配理论识关键词图论学Matching theory and its application Li xxxxxxx Class xxxx，Mathematics Department Tutor：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引言 目前，大学业难经为国个问题国经济长态势够续断业岗学业质较应国业竞争应会现积业难现实并非毕业业”经为现图论个内理论场双向选择解释个场稳为我们对场进设计场选择理论识对学业场的研义2.1 图的概念 我们所讨论的图与人们通常所熟悉的图，例如圆、椭圆，函数图形等是很不相同的。所谓图组非空称为顶点集，称为边集，而是到中元素有序对或无序对簇的函数，称为关联函数。中元素称为顶点，中的元素称为边，刻画了边与顶点之间的关联联系。若中元素全是有序对，则称为有向图，记为.若中的元素全是无序对，则称为无向图，记为. 图论中大多数定义和概念是根据图的图形表示提出来的。例如边与它的两端点称为关联的；与同一条边相关联的两端点或者与同一个顶点相关联的两条边称为相邻的。两端点相同的边称为环。若无环图的顶点集可以划分为两个非空子集和使得中任何两顶点之间无边相连并且中任何两顶点之间也无边相连，则称该图为二分图，称为二部划分。 从上面的讨论中可以看到，图的本质内容是顶点和边之间的关联联系，至于顶点和边是否用平面上的几何点和线段来表示，则完全是不必要的，换句话说，图的概念可以抽象化。 定义 设和是图的顶点子集，使,且的每一条边的每一个端点在中，另一个端点在中，则称为二分图（。记作：. 如果中的顶点与中的每个顶点都相联，则成为完全二分图。若 ，（符号表示集合中元素的个数），则完全二分图记作. 图的顶点集分成两个子集和的分划，称为的二分划。 2.2 匹配的相关定义 定义1 设是无环非空图，是的非空子集，若中任何两条边在中均不相邻，则称为的匹配。例如，在图2.2.1所示图中，粗边所示的边集是该图的一个匹配。中与中边关联的顶点称为饱和点。反之，称为非饱和点。设. 若中每点都是饱和点，则称饱和.若饱和，则称为的完备匹配。若对的任何匹配均有，则称为的最大匹配。显然，每个完备匹配都是最大匹配。 如图2.2.1中粗边表示的匹配分别是该图的最大匹配和完备匹配。 (图2.2.1） 定义2 可增广道路 设是图的一个匹配，是的一条路，且在中，的边和 的边交替出现，则称是的一条交错路。若交错路的两个端点为非饱和点，则称为可增广路。 例如，图2.2.2所示图中，虚线所示为匹配，则是一条交错路，而是一条可增广路。 （图2.2.2） 定理2.2.1 的一个匹配是最大匹配的充要条件是不包含