(n，n)图的k-终端割与（n，n+1）图的3-终端割问题研究

论文摘要

在一个边权无向图中,取定结点集的一个子集,子集中的元素称为终端。k-终端割问题（k-terminal cut problem）指的是寻找一个边子集,使得图中去掉该边子集后,各终端互不连通,且该边子集权和最小。近年来,k-终端割问题在理论界引起了极大的关注,并被广泛地应用于许多实际领域中,诸如并行与分布计算、VLSI电路设计以及网络连接等。本文主要研究无向简单连通（n,n）图的k-终端问题和（n,n+1）图的3-终端割问题,并限定图中边权为正且两两不同。 在充分考虑（n,n）图结构特点的基础上,本文给出了它的一个重要性质,即:当最小k-终端割中包含有Pc（（n,n）图中唯一的基本回路）上边时,一定包含Pc上的最小加权边。利用这个性质,文中巧妙地将（n,n）图与树联系起来,并结合树的最小k-终端割算法给出了Pc上终端数不小于2的情况下,（n,n）图上时间复杂度为O（kn）的k-终端割问题确定算法。进而,为了解决（n,n）图中只上终端数小于2时的k-终端割问题,在没有增加算法的时间复杂度的情况下,本文对该算法作了适当修改,并指出修改后的算法实际上可以作为求解（n,n）图中k-终端割问题的通用算法,从而在一定意义上较好地解决了（n,n）图中的k-终端割问题,与已有算法相比较,其运算效率也有了明显提高（已知最好算法在解决（n,n）图中k-终端割问题时的时间复杂度为O（nk3+（nlogn）k2））。 为了寻求（n,n+1）图中3-终端割问题的有效解决方案,本文充分分析了（n,n+1）图的结构特点,并在此基础上将其适当分类,从而将此类图中的3-终端割问题分解为多个较小的子问题。结合已有的终端在同一面边界上的平面图3-终端割问题的线性时间算法,文中相应给出了这些子问题的线性时间算法,并最终在线性时间内完整地解决了（n,n+1）图的3-终端割问题,在一定程度上降低已有算法在解决此类问题时的运算复杂度（已有最好算法在解决（n,n+1）图中3-终端割问题时的时间复杂度为O（n3logn））。

论文目录

• 第1章 绪论
• 1.1 k-终端割问题及产生背景
• 1.2 k-终端割问题及相关问题的发展现状
• 1.3 平面加权无向图上k-终端割问题
• 1.3.1 一般平面加权无向图上k-终端割问题
• 1.3.2 加权无向树的k-终端割问题
• 1.4 本文的主要研究对象与研究结果
• 第2章 预备知识
• 2.1 基本概念和记号
• 2.2 图的基本性质
• 第3章 （n，n）图的k-终端割问题
• 3.1 树的k-终端割问题
• 3.2 基本回路上终端数目不小于2的k-终端割问题
• 3.2.1 一些相关的定理与定义
• 3.2.2 基本回路上终端数目不小于2的算法设计
• 3.2.3 算法的复杂度分析
• 3.3 基本回路上终端数目小于2的k-终端割问题
• 第4章 （n，n十1）图的3-终端割问题
• 4.1 终端在同一面边界上的平面图3-终端割问题
• 4.2 （n，n+1）图的分类
• 4.3 （n，n+1）图的3-终端割问题
• 4.3.1 终端在不同面边界上的θ类图的3-终端割问题
• 4.3.1.1 终端在不同面边界上的θ图算法设计
• 4.3.1.2 终端在不同面边界上的θ类图算法设计
• 4.3.2 （n，n+1）图的3-终端割问题算法设计
• 第5章 结束语
• 攻读学位期间公开发表的论文
• 致谢
• 参考文献
• 研究生履历