论文部分内容阅读
图论在近三十多年来发展十分迅速,其应用已涉及计算机科学、物理学、信息论、控制论、运筹学以及网络理论等领域。路覆盖是图论中的一个非常重要的概念,可以应用于并行算法设计,程序代码优化,应用程序测试,环协议设计等问题。本文主要讨论图的路覆盖问题。 连通图与其生成树的路覆盖数之间有非常密切的关联,我们将利用生成树的路覆盖数来研究一般连通图的路覆盖数问题,为此探讨树状图的路覆盖数是研究的基础。正则图是非常重要的一个图类。由于正则图具有很好的对称性,所以正则图的系列性质是图论中一直被研究的话题,同时也是图论研究中相当活跃的一个领域,因此其路覆盖数应该有更为精细的结论,本文将重点讨论正则图的路覆盖数问题。 图G的路覆盖是由顶点不相交的路所构成的一个集合,使得图G的每个顶点恰好包含于路覆盖的某条路中。在图G的所有路覆盖中,包含路条数最少的那个路覆盖称为图G的一个最小路覆盖,记为p。所包含路的条数称为G的路覆盖数,记为P(G)。 本文对图的路覆盖数进行了研究和探讨,主要得出了下面的结论: 1.本文从图的路覆盖数出发,讨论了简单连通图去掉一条边或者去掉一个顶点时的路覆盖数的变化情况;对k层完全二叉树T的路覆盖数进行了研究,分别得出了k为奇数和偶数时树T的最小路覆盖数;研究了某些线图的路覆盖数与原图边覆盖数之间的关系,以及k-拟正则图的路覆盖数;分情况研讨了树状图的路覆盖数与重边数之间的关系,同时也得到了不同重边数条件下路覆盖数的值;给出了2-sparse树的一个充分必要条件。 2. Magnant与Martin曾经对k≤5的情形给出了k-正则简单图路覆盖数的一个上界,即路覆盖数满足:p(G)≤n/k+1(k≤5) 本文对此进行了更细致深入的研究,在k≤4时给出了恰好达到这个上界的k-正则简单图路覆盖数的完全分类,即设图G是n阶k-正则简单图,其中0≤k≤4,则图G的路覆盖数为p(G)-n/k+1当且仅当G=tKk+1,其中t为G的连通分支数。