一些乘积图和完全二部图的k路顶点覆盖

代理获取

页面导航

目录
摘要
著录项
相似文献
相关主题

摘要

图的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□□P2n）的下界.
　　本文所得结论是全新的，可以通过构造k路顶点覆盖集的方式得以验证.每一章都给出了构造的相应k路顶点覆盖集，证明了所得结论的正确性及有效性.所得结果为更复杂图的k路顶点覆盖问题提供了一定的理论基础.

著录项

作者
李钊;
展开▼
作者单位

天津师范大学;

展开▼
授予单位天津师范大学;
学科数学；运筹学与控制论
授予学位硕士
导师姓名左连翠;
年度 2018
页码
总页数
原文格式 PDF
正文语种中文
中图分类图论;
关键词
乘积图; 完全二部图; k路顶点覆盖; 笛卡尔积; 强积;

相似文献

中文文献
外文文献
专利

1. 几类笛卡尔乘积图的k路顶点覆盖数问题 [J] . 李钊1 ,左连翠1 . 应用数学进展 . 2017,第009期
2. 完全图与树、圈、完全图、完全二部图的笛卡尔乘积图的消圈数 [J] . 沈传锦 . 海南大学学报（自然科学版） . 2009,第004期
3. 一个路与一个完全二部图直积的L(2,1)-标号 [J] . 徐礼礼 ,董晓媛 ,马登举 . 牡丹江师范学院学报（自然科学版） . 2016,第002期
4. 路与路的字典乘积图的消圈数 [J] . 沈传锦 . 唐山师范学院学报 . 2011,第005期
5. 路与路的乘积图的λ′_(1,1)-数与λ′_(2,1)-数 [J] . 冯宁 ,孙学香 . 扬州大学学报：自然科学版 . 2010,第3期
6. 一种求解图最小顶点覆盖问题的混合遗传算法 [C] . Zhou Benda ,周本达 ,Chen Minghua . 第三届中国智能计算大会 . 2009
7. 一些乘积图的k-路顶点覆盖 [A] . 张弼弢 . 2016

一些乘积图和完全二部图的k路顶点覆盖

目录

摘要

著录项

相似文献

相关主题

期刊订阅