《含4—圈且不含3—圈的P4—等可覆盖图的刻画》-工学论文，软件工程论文-论文范文参考-科学狗论文网

标题

含4—圈且不含3—圈的P4—等可覆盖图的刻画

范文

王琪瑞++帅天平

摘要：覆盖问题是图论的主要研究内容，也是理论计算机科学中的重要内容之一，具有重要的理论意义与应用价值，在计算机图形学和运筹学中都有广阔的应用前景。在通信行业，基于覆盖问题的研究基础，可以简化通信网络的层次分布与优化。特殊的覆盖可以导出图的一些良好的性质，鉴于这类问题在实际应用中的价值，此类研究近期应用于图的结构性之上。图论中的覆盖问题有很多种，其中包括等可覆盖问题：如果一个图G的每个极小H-覆盖都是它的最小H-覆盖，则称G为H-等可覆盖的。本文仅考虑H为P4时的情形。经过讨论，本文通过对含4一圈且不合3一圈的图的特征进行刻画，给出了判定任意一个含4-圈且不含3-圈的图是否是P4-等可覆盖的充分必要条件。

关键词：计算机软件与理论；等可覆盖；图论；覆盖

中图分类号：0157.5 文献标识码：A DOI：10.3969/j.issn.1003-6970.2015.10.002

引言

图论是组合数学的一个重要分支，在计理论算机科学领域有着极其重要的地位和作用。近些年来，理论计算机科学的迅猛发展和理论需求大大推动了图论的发展，同时也为图论的研究带来了越来越多的新课题。图论中的问题相当丰富，其中，覆盖问题作为非常重要而又基本的问题，多年来一直受到国际组合学界的广泛重视。历史上，人们对覆盖的研究兴趣主要集中在它们的优化问题上。特殊的覆盖可以导出图的一些良好的性质，鉴于这类问题在实际应用中的价值，此类研究近期应用于图的结构性之上。事实表明，许多覆盖问题在组合优化理论、编码理论、计算几何、计算机图形学、结晶学及运筹学等领域都有十分重要的意义和广阔的应用前景，在网络设计中也能发挥其重要的应用价值。覆盖问题有很多种，在生活的各个领域都发挥着举足轻重的作用，比如在通信行业，基于覆盖问题的研究基础，可以简化通信网络的层次分布与优化；通过对覆盖图案的分析，可以运用CAD软件绘制出各种美感的图形；在医学和化学等行业，物质分子结构的构造也会涉及到覆盖问题的相关理论。总之，对此类问题的研究可以引起相关学者对此类研究问题的广泛关注与兴趣，从而促使覆盖理论的不断完善与丰富。等可覆盖问题就是其中的重要研究内容，它作为覆盖问题中一个活跃的分支，起源于Caro与Schonheim对P3-可分解图特征的刻画，具有重要的理论意义和实际意义。

1 研究背景与基本定义

1.1 研究背景

覆盖问题是理论计算机科学中一类非常重要而又基本的问题。在美国的贝尔实验室、普林斯顿大学等一些重要的研究机构，有许多专家在从事这方面的研究。1985年，S.Ruiz引入了随机H-可分解图的概念，并刻划了H分别为p3和M2时的随机H-可分解图的特征。作为随机H-可分解性的放松，数学家B.L.Harthell和P.D.Vestergaard引入H-等可填充图的概念，并刻划了围长大于等于5的H-等可填充图的特征。接下来，B.Randerath和P.D.Vestergaard给出了所有H-等可填充图的特征。2008年，Zhang引出H-等可填充图的对偶的概念：H-等可覆盖图的概念，并完全刻划了H-等可覆盖图的特征。2009年，Zhang等给出了M2-等可覆盖图的一些结论，并刻画了几类特殊的M2-等可覆盖图，并已完全刻画了M2-等可覆盖图的特征。在本文中，我们给出所有含4-圈且不含3-圈的P4-等可覆盖图的刻画。

1.2 基本定义

令H为某一固定的图。如果图G的每一条边都至少出现在某一个子图Hi（i=1，2，…k中，即，则称为G的一个H-覆盖。设为图G的一个H-覆盖，若对于任意Hj（j∈{l，2，3，…k}），均不是G的一个覆盖，则称为G的一个极小H-覆盖。设H1，H2，…Hk为G的一个H-覆盖，如果不存在少于k个同构于H的子图可以覆盖图G，则称H，H2，…Hk为G的一个最小H-覆盖。如果G的每个极小H-覆盖都是G的最小H-覆盖，则称G为H-等可覆盖的。我们用MG（L）表示G的一个极小H-覆盖L=H1，H2，…Hk的覆盖数，用mG（L）表示G的最小H-覆盖的覆盖数。

命题 1.1 一个连通图G是P4-可覆盖的当且仅当它有一个子图P4。

显然，如果一个连通图G是P4-可覆盖的，它至少含有3条边。注意到当G同构于K1，t（t>3），那么它不是P4-可覆盖的。所以在下文中描述的阶数大于等于4的P4-可覆盖图中，不含有K1，t（t>3）。

命题 1.2 一个图G是P4-可覆盖的当且仅当它的每一个连通分支都是P4-可覆盖的。

引理 1.3G是一个连通图。如果G可以分解为几个连通的P4-可覆盖图，且它们中的至少一个不是P4-等可覆盖的，那么G不是P4-等可覆盖的。

引理 1.4G是一个树。我们将G中不相邻的两点合并为一点从而得到了一个含圈的新图G。如果G不是P4-等可覆盖的，那么G不是P4-等可覆盖的。

2 主要结论

首先，我们刻画了p4-等可覆盖的路和圈。

引理 2.1 路Pn是P4-等可覆盖的当且仅当n=4，5，6，7，8，11.

引理 2.2 圈Cn是P4-等可覆盖的当且仅当n=4，5，7.

下面，我们给出一个有用的结论。

定义 2.3 对于星Ki，t，我们将其中度为k的结点称为中心结点，其他结点称为端点（树叶）。在星K1，t的每条边上都插入一个2度结点所得的树称为一个k-扩星。即k-扩星有一个度k结点（称为扩星的中心），k个度2结点，k片树叶。我们记之为在k-扩星的每条边上都插入一个2度结点所得的树称为一个二阶k-扩星，记之为类似地，n阶k-扩星是通过在n-l阶k-扩星的每条边上都插入一个2度结点所得到的。

下面的引理很容易验证是正确的：

引理 2.4 每一个二阶k扩星都是P4-等可覆盖的。

注释 2.5 显然，P4可以表示为而P7可以表示为.

引理 2.6 G是一个连通图且非圈。如果G不含3-圈且含有4-圈，那么G不是P4-等可覆盖的，除非G是（n>l）或者G是由n个P2·K1，t（t>3）中p2部分的度1结点与C4中的同一个结点合并而构成的图。

证明：情形1：G是由若干个p2和C4合并而成的图。

（1）如果C4的每一个结点只能与至多一个P2的端点合并，那么G只可能是图1中的五种情况之一。对于图1中的每一个图，我们都可以找到一个极小覆盖L，使得它的覆盖数MG（L）大于最小覆盖的覆盖数m （G）。所以图1中的图都不是P4-等可覆盖的。

（2）如果C4的每一个结点可以与多个p2的端点合并，那么G可以看作是由多个P2的端点与G中的4-圈部分的结点合并而成，其中G为图1中的图之一。如果p2的数目为n，我们可以找到一个覆盖数为M（G）+n的极小P4覆盖（用M（G）个P4覆盖G部分，用n个P4覆盖其余部分），而最小覆盖的覆盖数不会多于m（G）+n。对于每一个G，都存在一个它的极小覆盖，其覆盖数M（G）>m（G），因此G不是P4-等可覆盖的。

情形 2：G是由若干个P3和C4合并而成的图。

注意到我们是将每一个P3的端点而不是中心点与C4的结点合并，否则的话G就与情形1中的某些图重复了。

（1）如果C4的每一个结点只能与至多一个P3的端点合并，那么G只可能是图2中的五种情况之一，对于图2中的每一个图，我们都可以找到一个极小覆盖L，使得它的覆盖数MG（L）大于最小覆盖的覆盖数m（G）。所以图2中的图都不是P4-等可覆盖的。

（2）如果C4的每一个结点可以与多个P2的端点合并，那么G可以看作是由多个P2的端点与G中的4-圈部分的结点合并而成，其中G为图2中的图之一。如果P2的数目为n，我们可以找到一个覆盖数为M（G）+n的极小P4覆盖（用M（G）个P4覆盖G部分，用n个P4覆盖其余部分），而最小覆盖的覆盖数不会多于m（G）+n。对于每一个G，都存在一个它的极小覆盖，其覆盖数M（G）>m（G），因此G不是P4-等可覆盖的。

情形 3：G是由若干个P2和若干个P3与C4合并而成的图。

如果只有若干个P2或者若干个P3，那么与情形1或情形2相同。否则，

（1）如果C4的每一个结点只能与至多一个P2或P2的端点合并，那么G只可能是图3中的九种情况之一。对于图3中的每一个图，我们都可以找到一个极小覆盖L，使得它的覆盖数MG（L）大于最小覆盖的覆盖数m（G）。所以图3中的图都不是P4-等可覆盖的。

（2）如果C4的每一个结点可以与多个P2或P2的端点合并，那么G可以看作是由多个P2或P3的端点与G中的4-圈部分的结点合并而成，其中G为图2中的图之一。如果p2和P3的总数目为n，我们可以找到一个覆盖数为M（G）+n的极小P4覆盖（用M（G）个P4覆盖G部分，用n个P4覆盖其余部分），而最小覆盖的覆盖数不会多于m（G）+n。对于每一个G，都存在一个它的极小覆盖，其覆盖数M（G）>m（G），因此G不是P4-等可覆盖的。

（3）容易验证，图4中的图不是P4-等可覆盖的。如果C4中的一个或多个结点与至少一个P，和一个P2的端点合并，那么G可分解为两部分： P4和一个非P4-等可覆盖的图。

情形4：G是由若干个星K1，t（t>3）和C4合并而成的图。

注意到我们是将每一个星K1，t（t>3）的端点而不是中心点与C4的结点合并，否则的话G就与情形1中的某些图重复了。

当t=3时，

（1）如果C4的每一个结点只能与至多一个星K1，（t>3）的端点合并，那么只可能得到5个可能的图。容易验证这5个图都不是P4-等可覆盖的。

（2）如果C4的每一个结点可以与多个P2或P3的端点合并，那么G可以分解为n个K1，t和一个图G，其中图G是（1）中一个非P4-等可覆盖的图。记G的一个极小P4覆盖的覆盖数为M（G），那么图G存在一个覆盖数为M（G）+n的极小P4覆盖，而图G的最小P4覆盖的覆盖数不会大于m（G）+n.于是G不是P4-等可覆盖的。

当t >4时，我们可以找到G的一个极小P4覆盖，其覆盖数为M（G-）+（t一3）>m（G-）+（t-3）（用M（G）个P4覆盖G-部分，用（t-3）个P4覆盖其余部分）。而图G的最小P4覆盖的覆盖数不会大于m（G）+n.于是G不是P4-等可覆盖的。

情形 5：G是由若干个p2和若干个K1，t（t>3）与C4合并而成的图。

注意到我们是将每一个星K1，t（t>3）的端点而不是中心点与C4的结点合并。如果只有若干个p2或者若干个K1，t（t>3），那么与情形1或情形4相同。否则，

当t=3时，

（1）如果C4的每一个结点只能与至多一个P，或K1，3的端点合并，那么G只可能是图5中的九种情况之一。对于图5中的每一个图，我们都可以找到一个极小覆盖L，使得它的覆盖数MG （L）大于最小覆盖的覆盖数m（G）。所以图5中的图都不是P4-等可覆盖的。

（2）如果C。的每一个结点可以与多个P，或K1，t的端点合并，那么G可以看作是由多个P2或K1，3的端点与G中的4-圈部分的结点合并而成，其中G为图5中的图之一。如果P，和K1，3的总数目为n，我们可以找到一个覆盖数为M（G）+n的极小P4覆盖（用M（G）个P4覆盖G部分，用n个P4覆盖其余部分），而最小覆盖的覆盖数不会多于m （G）+n。对于每一个G，都存在一个它的极小覆盖，其覆盖数M（G）>m（G），因此G不是P4-等可覆盖的。

（3）我们将图6中的图记为G。由于存在一个极小覆盖，其覆盖数M（G）=4>3=m（G），所以G不是P4-等可覆盖的。如果C4的一个或多个结点与至少一个P2和K1，3合并，那么G可以被分解为两部分：P2和一个非P4-等可覆盖图。

当t >4时，我们可以找到G的一个极小P4覆盖，其覆盖数为M（G）+（t-3）>m （G）+（t-3）（用M（G）个P4覆盖G部分，用（t-3）个P4覆盖其余部分）。而图G的最小P4覆盖的覆盖数不会大于m（G）+n.于是G不是P4-等可覆盖的。

情形 6：G是由若干个P2和若干个K1，t（t>3）与C4合并而成的图。

注意到我们是将每一个星K1，t（t>3）的端点而不是中心点与C4的结点合并。如果只有若干个P3或者若干个K1，t（t>3），那么与情形2或情形4相同。否则，

与情形5类似，G不是P4-等可覆盖的。

情形 7：G是由若干个P2，P3和若干个K1，t（t>3）与C4合并而成的图。

注意到我们是将每一个星Kl，t（t>3）的端点而不是中心点与C4的结点合并。我们只需要考虑若干个P2，P3和若干个K1，t（t>3）同时与C4合并的情形。否则，G与之前情形中的某些图相同。

与情形5类似，G不是P4-等可覆盖的。

情形8：G是由若干个P4和C4合并而成的图。

注意到我们是将每一个P4的端点与C4的结点合并，否则的话G就与之前情形中的某些图重复了。

（1）如果n个P4的端点只能与C4的一个结点合并，那么极小覆盖数MG（L）和最小P4覆盖数m（G）都是n+2。我们将这个图记作，它是P4-等可覆盖的。

（2）如果n个P4的端点可以与C4的至少两个结点合并，那么存在一个覆盖数MG（L）=n+3的极小P4覆盖，而最小P4覆盖数m（G）是n+2，因为MG（L）>m（G），所以G不是P4一等可覆盖的。

情形9：G是由若干P2K1，t（t>3）和C4合并而成的图。

我们将P2的一个端点与K1，t（t>3）的一个端点合并得到的图记作P2·K1，t（t>3）。我们将P2.K1，t（t>3）中的P2部分的端点与C4的结点合并，否则G就与之前情形中的某些图重复了。

（1）如果n个P2·K1，t（t>3）只能与C4的一个结点合并，那么极小覆盖数MG （L）和最小P4覆盖数m（G）都是n（t-l）+2。它是P4-等可覆盖的。

（2）如果n个P2·Kl·t（t>3）可以与C4的至少两个结点合并，那么存在一个覆盖数MG（L）=n（t-1）+3的极小P4覆盖，而最小P4覆盖数m（G）是n（t-1）+2，因为MG（L）>m（G），所以G不是P4-等可覆盖的。

情形10：G不属于情形1-9。

每一个图G可以被分解为2个连通的部分：一个包含于情形1-9中的非P4-等可覆盖图和一个P4-可覆盖图。由引理1.4，G不是P4-等可覆盖的。

综上，G不是P4-等可覆盖的，除非G是C4·Sn2*（n>l）或者是由n个P2·Kl，t（t>3）与C4的同一个结点合并而成的图。

随便看

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。