K1,3-等可填充图和K1,3-等可覆盖图

摘要

填充与覆盖问题是图论中非常重要而又基本的问题，在物理学、计算机网络及组合优化等领域都有十分重要的意义.
　　本论文研究一类具有对偶性质的填充和覆盖问题: Ki,3-等可填充图和3-等可覆盖图的特征刻划问题.若图G的每个极大H-填充都是它的最大H-填充，则称图G为H-等可填充的.若图G的每个极小H-覆盖都是它的最小H-覆盖，则称图G为H-等可覆盖的.论文首先研究了几类特殊的Ku-等可填充的毛虫图，然后给出了所有Ku-等可填充的毛虫图的特征，并在此基础上刻划了不含度3结点的K1;3-等可填充树的特征，接着给出了几类特殊的Ki,3-等可填充图.最后研究了几类特殊的Ki,3-等可覆盖树，并给出粘合的定义：G i和G2为G的导出子图，当满足G=Gi U G2且v=V(Gi)nV(G2)时，称G是由Gi和G2通过v粘合而成的.通过粘合，完全刻划了Ki,3-等可覆盖树的特征.

目录

第一个书签之前