关于图的分解、等可填充与等可覆盖的一些结果

来源 :天津大学 | 被引量 : 0次 | 上传用户:ReganCai
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
填充与覆盖问题是图论中非常重要而又基本的问题,在物理学、计算机网络及组合优化等领域都有十分重要的意义。填充和覆盖是一对具有对偶性质的概念。作为填充与覆盖问题中一个活跃的分支,图论中的等可填充和等可覆盖问题起源于Caro与Schonheim对P3?可分解图和M2?可分解图特征的刻画。若图G的每个极大H?填充都是它的最大H?填充,则称图G为H?等可填充的。若图G的每个极小H?覆盖都是它的最小H?覆盖,则称图G为H?等可覆盖的。  本文主要研究图的分解、等可填充与等可覆盖的问题。  第一章对所研究问题的背景及发展进行综述,给出文章所得主要结果。  第二章主要给出了本文研究问题所需要的基础知识、基本定义、定理和相关符号。  第三章主要运用图的转化,数学归纳法研究P5?可分解的完全图、完全二部图、轮图及完全多部图。  第四章借助边矩阵研究P4?等可填充的完全图、完全二部图、扇图及轮图。  第五章主要研究等可覆盖问题,刻画了含圈的围长至少为5的P5?等可覆盖的图及部分Pk?等可覆盖的图。
其他文献
有理函数Julia集的拓扑是复解析动力系统研究的重要问题之一,多项式Julia集的连通性由于Branner-Hubbard猜想的证明[47]已得到较为完整的刻画.对于有理函数动力系统,二次有理