最优指派问题算法及其应用+源程序(2)
时间:2018-05-11 11:45 来源:毕业论文 作者:毕业论文 点击:次
1.2 国内外研究现状与发展趋势[15] 1.3 基本概念及符号说明 1.3.1 基本概念 匹配(Match)[1]：图 中的一个子集 ，若它的元素均为边，且 中的元素互不相邻，则称 是 的一个匹配。 被匹配(Be Matched)[1]： 中的边的两个顶点称为在 下被匹配。 饱和的( Saturated)[1]：若 被 匹配，则称 是 饱和的。 完美匹配(Perfect Match)[1]：若 中的每一个顶点均 饱和，则称 是 的完美匹配。 子图(Sub-graph)[1]：若 ， ，且 为 在 上的限制。则称 为 的子图。 完全图(Complete Graph)[1]：如果简单图 中每一对不同顶点恰有一条边连接，那么称 为完全图。 二部图(Bipartite Graph)[1]：设 和 是 的顶点子集，使 ， 且 的每一条边的一个端点在 中，另一个端点在 中，则称 为二部图，记作 。 完全二部图(Complete Bipartite Graph)[1]：如果 中的顶点与 中的每一个顶点都邻接，那么该图称为完全二部图。 增广路（ Augmenting）[1]：若 是图 中一条连通两个未匹配顶点的路径，并且属于 的边和不属于 的边(即已匹配和待匹配的边)在 上交替出现，那么称 为相对于 的一条增广路径。 度数（Degree）[2]：已知图 ，称与 关联的边的数目（一条环要计算两次）为 的度数（degree），记为 。 正则图( Regular Simple Graph)[2]：若对 均有 ，则称 为 正则图。 覆盖（Cover）[3]：设 是拓扑空间 的子集族，称 是 的一个覆盖，如果对任意 ， 至少包含在 的一个成员之中。 1.3.2 符号说明 ：表示指派问题的人数 ：表示需要完成的任务数 ：表示指派第 人去完成第 项任务所消耗的资源 ：表示决策变量 ： 元素的数目 ：覆盖所有0元素的最少直线数 ：是足够大的常数 ：隶属矩阵 (责任编辑：qin) |