论文部分内容阅读
图的k-路顶点覆盖理论在无线传感网络和交通控制领域都有很重要的应用。近几年来在国内外得到了广泛的研究。图的k-路顶点覆盖问题,也简称为k-VCP,找到一个最小的顶点子集F,使得在图G每一条长度为k的路中至少含有F中的一个顶点。k-路顶点覆盖的最小基数叫做图G的k-路顶点覆盖数,记做ψk(G)。实际上,我们用路的顶点数来表示次序,同时我们用长度来表示路的边数。由图G =(V(G),E(G))和图H=(V(H),E(H))构成的笛卡尔乘积图G□H的顶点集为V(G)× V(H),并且当u1 = u2且v1v2∈E(G)或u1u2 ∈E(G)且v1=v2时,顶点(u1,v1)和顶点(u2,v2)是相连的.由图G =(V(G),E(G))和图H=(V(H),E(H))构成的字典乘积图GoH的顶点集为V(G)×V(H),并且当 u1u2 ∈ E(G),或 u1 = u2 且v1v2∈E(H)时,顶点(u1,v1)和顶点(u2,v2)是相连的.由图G =(V(G),E(G))和图H =(V(H).E(H))构成的强乘积图G(?)H的顶点集为V(G)×V(H),并且当u1u2 ∈ E(G)且v1 = v2,或u1 = u2 且 v1v2 ∈ E(H),或u1u2 ∈ E(G)且巧v1v2 ∈E(H)时,顶点(u1,v1)和顶点(u2,v2)是相连的.本文主要研究了乘积图的k-路顶点覆盖问题.第一章首先简单介绍了预备知识和图的k路顶点覆盖的相关研究背景.第二章给出了 Pm□Cn的k路顶点覆盖数的上下界.根据引理1.1和1.2我们证明了 ψk(Wn+1)的精确值,并且在此结果的影响下得到了Pm和Wn+1之间各类乘积图的k路顶点覆盖数的估计值.第三章证明了Km,n的k路顶点覆盖数的确切的值.与此同时在Km,n的结果下,我们得到Km,n和P2的笛卡尔乘积图的k路顶点覆盖数的估计值第四章研究了笛卡尔乘积图Pm□Cn和强乘积图Pm(?)Cn的k路顶点覆盖的更加精确的上界,并且给出了ψk(Cm□Pn2)的下界.本文所得结论是全新的.可以通过构造k路顶点覆盖集的方式得以验证.每一章都给出了构造的相应k路顶点覆盖集.证明了所得结论的正确性及有效性.所得结果为更复杂图的k路顶点覆盖问题提供了一定的理论基础.