团队指派与星匹配问题

论文摘要

图的最大星匹配问题是图的经典匹配问题的自然推广。给定图集合G,设M是图G的一个子图集合,若M中任意两个子图的顶点集合互不相交,且M中每个子图都同构于G中的某个元素,那么称M是图G的一个G-匹配。称包含顶点最多的G-匹配为G的最大G-匹配。最大G-匹配问题是指求出图的一个最大G-匹配。星匹配是指G中的元素均是星图。最大星匹配问题在团队指派等问题中有着广泛的应用,近年来得到了广泛而深入的研究。本文主要考虑无向无权图上的最大星匹配问题。文中用Si表示完全二部图K1,i。,当i≤T时,称S为T-星;当i ≥ T时,称S为T+-星;当1<i<T且i≠t时,称S为T星。在第二章中,我们应用动态规划给出了求解树上最大T+-星匹配的多项式时间算法。继而对算法进行推广,完全解决了树的最大星匹配问题。第三章讨论了 3-正则图上的几类最大星匹配问题。首先证明了 3-正则图总存在{S1,S2}-因子。然后估计了 3-正则图在最大{S1,S3}-匹配下的暴露点数。对3-正则图的最大S3-匹配问题,我们证明了该问题是NP-难的,然后运用分治法给出了指数时间的精确算法。第四章转向一般图的最大星匹配问题。首先,利用最小点覆盖问题简明地证明了当T≥2时,一般图的最大T+-星匹配问题是NP-难的,同时给出了最大2+-星匹配问题的不可近似度。而后本文分别给出了在i ≠ 1和t=1两种情况下,一般图最大T星匹配大小的紧下界。

论文目录

• 摘要
• Abstract
• 第一章 绪论
•   1.1 图论的基本符号和概念
•   1.2 最大星匹配的背景和已有结果
•   1.3 本文的主要工作
• 第二章 树的最大星匹配
• +-星匹配'>  2.1 树的最大T⁺-星匹配
•   2.2 树的最大星匹配
• 第三章 3-正则图的最大星匹配
• 1,S₂}-因子'>  3.1 3-正则图的{S₁,S₂}-因子
• 1,S₃}-匹配的暴露点数的估计'>  3.2 3-正则图最大{S₁,S₃}-匹配的暴露点数的估计
• 3-匹配问题的复杂度'>  3.3 3-正则图的最大S₃-匹配问题的复杂度
• 3-匹配的精确算法'>  3.4 3-正则图最大S₃-匹配的精确算法
•     3.4.1 归约规则
•     3.4.2 分枝规则
•     3.4.3 时间复杂度分析
• 第四章 一般图的最大星匹配
• +-星匹配'>  4.1 一般图的最大T⁺-星匹配
•   4.2 一般图的最大T\t-星匹配
• 致谢
• 参考文献

文章来源

类型: 硕士论文

作者: 李梦雅

导师: 林文松

关键词: 星因子,星匹配,正则图,算法

来源: 东南大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 东南大学

分类号: O157.5

DOI: 10.27014/d.cnki.gdnau.2019.000170

总页数: 48

文件大小: 2056K

下载量: 18