笛卡尔乘积图的配对控制数

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:lxzshenzhen
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
设图G=(V,E)是一个没有孤立点的无向简单图.如果V的一个非空子集D满足VD中的每个顶点都有一个邻点在D中,则称D是图G的一个控制集.进一步,如果D是图G的一个控制集并且由D导出的子图G[D]中有一个完美匹配,则称D是图G的一个配对控制集.一个图G的配对控制数,即图G的最小的配对控制集的大小,记为γp(G).配对控制数最初是由Haynes和Slater提出的,同时他们证明了对于一般图,确定其配对控制数是NP-完全的.  本文确定了一些特殊图的配对控制数,主要内容分为四章.第一章介绍了配对控制数的背景以及本论文所涉及的有关定义,并对路和圈的笛卡尔乘积的配对控制数的研究现状做了一个综述.第二章根据圈和圈的笛卡尔乘积的结构,利用反证法,确定了n圈和5圈的笛卡尔乘积的笛卡尔乘积的配对控制数.第三章给出n圈和m(m=2,3)路和n路和m(m=3,4,5)圈的配对控制数.第四章对本文进行了总结并给出笛卡尔乘积图配对控制数的一些可研究问题.
其他文献
摘 要 中小企业信息化建设是其提高运营效率,增强竞争力的重要手段。然而,在我国的现实经济中,中小企业信息化水平偏低,实施中的高失败率等现象普遍存在。本文针对中小企业信息化建设中的观念误区的诸种表现及产生根源进行分析,并有针对性地提出矫正的策略。  关键词 中小企业 信息化 观念误区 矫正策略  中图分类号:F276.3文献标识码:A    一、前言    随着全球信息化的迅猛发展和知识经济时代的到
设C是一个范畴,T是C中的单子(monad).本文将范畴C中代数和余代数的一些命题和结论推广到单子和余单子(comonad)上,得到一些有意义的结论.全文共分为五章. 第一章主要介绍单子与
本文主要证明了所有非次正规子群形成一个共轭类的群的一些性质. 定理2.2.若有限群G只含两个非次正规子群共轭类H=H,H,…,H和K=K,K,…,K,则G有下列性质: (1)至少有一个非次正规
论文分为三部分.第一部分讨论了度量空间中相容映象和非相容映象对的一些公共不动点问题;第二部分讨论了拓扑空间中(φ)-压缩映象的公共不动点问题;第三部分讨论了Banach空间