论文部分内容阅读
填充与覆盖问题是图论的主要研究内容之一，在网络设计、组合优化理论、结晶学及运筹学等领域都有十分重要的意义。填充和覆盖是图的一对具有对偶性质的概念，对研究图的结构性质也具有重要的意义。图论中的填充与覆盖问题有多种，本论文研究了其中互为对偶的一类：H-等可填充图与H-等可覆盖图的特征刻划问题。设Hi，H2，…，Hl为图G的一个H-填充，若G-∪(i=1,l)E(Hi)不含同构于H的子图，则称Hi，H2，…，Hl为G的一个极大H-填充。若G中不存在多于l个同构于H的两两不交的子图，则称H1，H2，…，Hl为G的一个最大H-填充。若G的每个极大H-填充都是它的最大H-填充，则称G为H-等可填充的。设Hi，H2，…，Hl为G的一个H-覆盖，若对于任意Hj(j∈{1，2，…，l}），∪(i≡1,l)E(Hi)-E(Hj)都不是G的一个覆盖，则称H1，H2，…，Hl为G的一个极小覆盖。若不存在少于l个同构于H的子图可覆盖G，则称H1，H2，…，Hl为G的一个最小H-覆盖。若G的每个极小H-覆盖都是G的最小H-覆盖，则称G为H-等可覆盖的。P3-等可填充图、M2-等可填充图、P3-等可覆盖图和M2-等可覆盖图的特征已经被刻划。本论文首先在M3-可分解图、随机M3-可分解图及M2一等可填充图的研究基础上，完全刻划了M-等可填充图的特征。然后刻划了Mk-等可填充的路和圈，Pk-等可填充的路和圈，及Pm∪Pk-等可填充的路和圈的特征。最后刻划了Mk-等可覆盖的路和圈，Pk-等可覆盖的路和圈，及Pm∪Pk-等可覆盖的路和圈的特征。