论文部分内容阅读
填充与覆盖问题是图论中非常重要而又基本的问题，在物理学、计算机网络及组合优化等领域都有十分重要的意义。填充和覆盖是一对具有对偶性质的概念。作为填充与覆盖问题中一个活跃的分支，图论中的等可填充和等可覆盖问题起源于Caro与Schonheim对P3?可分解图和M2?可分解图特征的刻画。若图G的每个极大H?填充都是它的最大H?填充，则称图G为H?等可填充的。若图G的每个极小H?覆盖都是它的最小H?覆盖，则称图G为H?等可覆盖的。 本文主要研究图的分解、等可填充与等可覆盖的问题。 第一章对所研究问题的背景及发展进行综述，给出文章所得主要结果。 第二章主要给出了本文研究问题所需要的基础知识、基本定义、定理和相关符号。 第三章主要运用图的转化，数学归纳法研究P5?可分解的完全图、完全二部图、轮图及完全多部图。 第四章借助边矩阵研究P4?等可填充的完全图、完全二部图、扇图及轮图。 第五章主要研究等可覆盖问题，刻画了含圈的围长至少为5的P5?等可覆盖的图及部分Pk?等可覆盖的图。