ABSTRACT

Let G be a graph with a maximum matching M. A subset S ⊆ M is called a forcing set of M if S is contained in only one maximum matching M of G. A forcing set of M with minimum cardinality is the minimum forcing set of M and its cardinality is called the forcing number of M, denoted by f_m(G, M). The minimum forcing number of all maximum matchings in G is called the forcing number of G, denoted by f_m(G). In this paper, we obtain the forcing number of maximum matching in spiro hexagonal para-chain.

Keywords:Maximum Matching, Forcing Set, Forcing Number, Spiro Hexagonal Para-Chain

螺旋六角para-链的最大匹配的强迫数

李晶晶¹，边红¹，于海征²

¹新疆师范大学数学科学学院，新疆 乌鲁木齐

²新疆大学数学与系统科学学院，新疆 乌鲁木齐

收稿日期：2020年2月5日；录用日期：2020年2月20日；发布日期：2020年2月27日

摘 要

令M是图G的一个最大匹配，S是M的一个子集。如果S除了被M包含而不被G的其它最大匹配所包含，那么称S是M的一个强迫集(forcing set)。M的最小强迫集所包含的边数称作是M的强迫数(forcing number)，记为f_m(G, M)。图G的所有最大匹配的强迫数的最小值称为G的最小强迫数(Minimum forcing number)，记作f_m(G)。在本文中，我们给出了螺旋六角para-链的最大匹配的强迫数的确切值。

关键词 :最大匹配，强迫集，强迫数，螺旋六角para-链

Copyright © 2020 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

本文考虑的图是简单、连通图。令G是一个图，我们用 $V\left(G\right)$ 和 $E\left(G\right)$ 分别表示图的顶点集和边集。

匹配(matching)理论在图论中有着丰富的应用背景，许多问题或它们的子问题都可归结为匹配问题来解决。而图论中的完美匹配的概念起源于统计物理中的dimer计数问题，在化学分子骨架图中的完美匹配相当于有机化学分子的凯库勒结构。凯库勒结构及其相关性质的研究引起了化学家和图论学者的广泛关注，这是因为研究化学分子的凯库勒结构有助于研究化学分子的结构稳定性和芳香性等化学性质。在1985年的化学著作中，Randić和klein [1] 针对凯库勒结构提出了“内度自由度”的概念。之后Harary [2] 等人在1991年针对图的完美匹配也提出了类似的强迫数的概念。因此，匹配的强迫数的概念来源于化学上凯库勒结构的内度自由度(innate degree of freedom)。在图论和组合数学中，有很多问题的研究都体现了“强迫”的思想。如：拉丁方、区组设计、Steiner系统等。近几年来关于完美匹配的强迫数的概念也出现了不同形式的推广，相继提出了全局强迫数、反凯库勒数、反强迫数和强迫六边形等概念。匹配强迫数问题有着丰富的物理、化学背景，也存在着很多未解决的公开问题。

图G中的一个匹配是一个边子集 $M\subseteq E\left(G\right)$，它使得G中的每个点最多和M中的一条边相关联，M中包含的边的个数称为M的阶数。M称为G的一个最大匹配，如果G中不包含阶数比M更大的匹配。图G中的任何一个最大匹配的阶数，称为G的匹配数，记为。我们称匹配M是极大的，如果图G中没有匹配M'，使得。显然，每一个最大匹配都是极大匹配，但是反之不然。M中边的端点称为M饱和点，否则称为M非饱和点。G的一个完美匹配(或者1-因子，在化学上称作凯库勒结构(Kekulé Structure))是G的一个边不交的子集M，且M饱和G的所有顶点。图G中的一条边称为允许边，如果它包含在图G的某个完美匹配中；否则称为禁止边。图G中的一条边称为固定允许边，如果它包含在图G的每一个完美匹配中。很显然，偶数个点的图才可能有完美匹配，如果图G有奇数个点，并且，我们就说G有几乎完美匹配。

图G的一个完美匹配M的强迫集S是M的一个子集，使得这个子集不包含在图G的其它任何完美匹配中。完美匹配M的最小强迫集所包含的边数称作M的强迫数，记。一个图的完美匹配的强迫集和强迫数的概念是用“局部”的方法来定义的，它是针对该图的某一个特定的完美匹配而言的。2004年，Vukĭcević和Sedlar [3] 首次引入了“全局强迫”这一概念，即考虑的是图G的所有完美匹配而不只是一个特定的完美匹配。图G的全局强迫集定义为G的一个边子集S，且满足图G的关于完美匹配的特征函数限制到S上是单射。图G的最小全局强迫集所包含的边数称为图G的全局强迫数，记为gf(G)。2015年徐守军等人 [4] 结合“强迫”和“全局强迫”的概念，提出了另外一个关于图G的所有完美匹配的全局性的概念，称作完全强迫数，并针对六角系统得到了一些基础性的结果。图G的完全强迫集，指的是G的一个边子集S，该边子集限制在图G的任何一个完美匹配上都是该完美匹配的一个强迫集。图G的最小完全强迫集所包含的边数称为该图的完全强迫数，记作cf(G)。以上这些定义都是针对于图的完美匹配而言的，而最大匹配是非常有用并且有趣的一类匹配，Lovász和Plummer [5] 曾给出了图G的最大匹配的Gallai-Edmonds结构定理，但是目前有关最大匹配的研究还相对较少。最近Damir Vukĭcević等人 [6] 对极大匹配的全局强迫数进行了研究，它们将全局强迫集和全局强迫数的概念从完美匹配推广到极大匹配，并给出了一些图类的极大匹配的全局强迫数的上、下界。

本文在上述研究基础上，将强迫集的概念从完美匹配推广到最大匹配。设M是图G的一个最大匹配，S是M的一个子集，如果S除了M以外，不被G的其它最大匹配所包含，那么称S是最大匹配M的一个强迫集。最大匹配M的最小强迫集的阶数称作是M的强迫数，记为。图G的所有最大匹配的强迫数的最小值称为图G的最小强迫数(minimum forcing number)，记作。

螺环烃是环烷烃中的一个重要子集类。而螺环烃是一个任意两个碳环仅有一个公共碳原子的环烷烃，也就是说，螺环烃是一个任意两个圈仅有一个公共点(该点被称为螺旋点 [7]，是一个4-度点)的连通图。螺旋六角系统(或六角仙人掌图 [8] )是一个仅含有六边形并且任意两个六边形仅有一个螺旋点的连通图，并且该螺旋点仅连接两个六边形。一个螺旋六角链是指图中任意一个六边形至多含有两个螺旋点的螺旋六角系统。我们给出了螺旋六角para-链(偶数个六边形)中最大匹配的强迫数的确切值。

2. 螺旋六角para-链的最大匹配的强迫数

一个螺旋六角链简记为，其中是中第i个六边形，两个六边形共用的点(是一个4度点)为图的螺旋点，即一个螺旋点当且仅当被两个六边形占用。任意两个螺旋点，，若u，v在中是相邻的，称它们是ortho-连接；若u，v的距离为2，则称它们是meta-连接；若u，v的距离为3，则称它们是para-连接。只含有一个螺旋点的六边形称为端六边形，即和。其余的六边形称为内部六边形。若一个螺旋六角链的一个内部六边形的螺旋点以para-(或meta-或ortho-)相衔接，则这个内部六边形被称作para-六边形(或meta-六边形或ortho-六边形)。若这个螺旋六角链的内部六边形都是para-六边形(或meta-六边形或ortho-六边形)，则这个螺旋六角链被称为螺旋六角para-链，记为 (或螺旋六角meta-链，记为，或螺旋六角ortho-链，记为)。

本文我们只考虑螺旋六角para-链，很显然螺旋六角para-链有5n + 1个点和6n条边。如果n是偶数，那么的点数为奇数，易知不存在完美匹配，此时我们考虑螺旋六角para-链的最大匹配。

若图G的顶点集能划分为两个非空子集A和B，使得A中任何两个顶点之间无边相连，并且B中任何两点之间也没有边相连，则称该图是二部图(bipartite graph)，称为其二部划分，记为。如果对A的任意非空子集X，都有则称二部图G关于A有正赢量，简称G有正赢量。设M是图G的一个最大匹配，M非饱和点的个数称为图G的亏量，记为def(G)。

令G是一个图。若D(G)是G中至少不被某个最大匹配所覆盖的顶点所构成的集合，而A(G)是V(G) − D(G)中与D(G)中至少一个顶点相邻的点所构成的集合，。根据Gallai-Edmonds分解定理，G[D(G)]的每一个分支是因子临界图，G[C(G)]是具有完美匹配的图；令U(G)表示D(G)的每个分支收缩成的点所构成的集合，则以U(G)和D(G)为二部划分的二部图是一个具有正赢量的二部图。显然，若G有完美匹配，则C(G) = V(G)。

引理1 [5] ：令图是一个二部图，若G关于A有正赢量，则，，且。

引理2 [9] ：设G是有完美匹配M的平面二部图，则M的匹配强迫数等于不交的M-交错圈的最大数目，即有，。

定理3：令G是含有2n个六边形的螺旋六角para-链，则G存在几乎完美匹配。

图1. 有2n个六边形的螺旋六角para-链图G

证明：假设G是含有2n个六边形的螺旋六角para-链。给图G的顶点进行如图1所示的标号，用分别表示G中所有的点，分别表示G中所有的边。

图2. 二部图G = (A, B)

显然图G也是一个平面二部图，其二部图的二部划分为，其中A部分的点集记为：

；

B部分的点集记为：

，

如图2所示，显然G关于A有正赢量。根据引理1，，，且，即图G存在几乎完美匹配。

定理4：令G是含有2n个六边形的螺旋六角para-链，则图G含有个最大匹配。

证明：假设G是含有2n个六边形的螺旋para-链。根据定理3，图G存在几乎完美匹配。则该图去掉B中任意一点，得到的新图存在完美匹配。我们将B中的点分成三部分。即。其中：

；

；

。

情形1：最大匹配M不饱和中一个顶点，图G删去中任意一点，得到的图恰好有两个一度点，并且存在完美匹配，且这两个一度点相关联的两条边一定是固定允许边。继续删去中这两条固定允许边相关联的点，得到图是含有2n − 1个六边形的螺旋para-链，且具有完美匹配。把中的六边形用阿拉伯数字进行标记，对于的任意一个完美匹配M，中所有被标记为奇数的六边形一定为M-交错六边形，中所有被标记为偶数的六边形中的两条平行边(边的端点都是二度点)是中固定允许边。中每一个M-交错六边形有两个完美匹配，中每一个M-交错六边形的一个完美匹配的并，加上中所有被标记为偶数的六边形的两条固定允许边，以及的两个一度点相关联的两条固定允许边构成的一个完美匹配，从而是G的一个最大匹配，可得G的最大匹配的个数为2ⁿ个。

情形2：最大匹配M不饱和中一个顶点，图G删去中任意一点，得到的图恰好有一个一度点，且存在完美匹配，故这个一度点相关联的边一定是固定允许边，继续删去中这条固定允许边相关联的点，得到的图有两种子情况。子情形一：存在一个一度点，则这个一度点相关联的边也必是固定允许边，再删去其相关联的点，得到图是含有2n − 1个六边形的螺旋para-链。与情形1类似可得有2ⁿ个完美匹配，从而G有2ⁿ个最大匹配。子情形二：存在三个一度点，这三个一度点相关联的三条边必是固定允许边，再删去这三条固定允许边相关联的点，得到包含两个分支，分别是两个含有奇数个六边形的螺旋para-链。其不交的M-交错六边形共有n个中每一个M-交错六边形有两个完美匹配，中每一个M-交错六边形的一个完美匹配的并，加上中所有剩下的六边形的两条固定允许边，以及的三个一度点相关联的固定允许边，以及的一度点相关联的边构成的一个完美匹配，从而是G的一个最大匹配，最大匹配的个数为2ⁿ个。

情形3：最大匹配M不饱和中一个顶点，图G删去中任意一点，得到的图含有四个一度点，它们相关联的边也一定是固定允许边，继续删去这四条固定允许边覆盖的点，得到的图是两个分支，分别是含有奇数个六边形的螺旋六角para-链。其M-交错六边形的个数共n个，中每一个M-交错六边形有两个完美匹配，中每一个M-交错六边形的一个完美匹配的并，加上中所有剩下的六边形的两条固定允许边，以及的四个一度点相关联的固定允许边，构成的一个完美匹配，从而是G的一个最大匹配，最大匹配的个数为2ⁿ个。

综上所述，去掉B中任意一点，得到的新图都有2ⁿ个完美匹配，故原图都有2ⁿ个最大匹配，又有，则图G含有个最大匹配。

定理5：令G是含有2n个六边形的螺旋六角para-链，M是G的一个最大匹配，则或n + 2或n + 4。

证明：由定理3和定理4可知，图G也是一个平面二部图，图的二部划分为，其中A部分的点集记为：；B部分的点集记为：，其中；；。根据图G的最大匹配不饱和的点所在的位置分为以下三种情形：

情形1：若G的最大匹配M是不饱和中任意一点的最大匹配，则这个最大匹配M是由 (G删去中任意一点，得到的图)的两个一度点相关联的固定允许边，并上 (是删去中这两条匹配边相关联的点，而得到的含有2n − 1个六边形的螺旋para-链)的一个完美匹配所构成的。已知含有最大边不交的M-交错圈的个数为n个。根据引理2，可知的完美匹配的强迫数是n，又已知G的最大匹配是不饱和中任意一点的最大匹配，那么两个一度点相关联的边一定是固定允许边，否则就不满足G的最大匹配是不饱和中任意一点的最大匹配。因此，不饱和中任意一点的最大匹配的强迫数是n + 2。

情形2：若G的最大匹配M是不饱和中任意一点的最大匹配，则这个最大匹配M有两种子情形。子情形1：最大匹配M是由 (G删去中任意一点，得到的图)的一个一度点相关联的边，加上 (删去中一度点关联的这条匹配边饱和的点，得到的图)的一个一度点相关联的边，以及 (删去中这一个一度点关联的匹配边所覆盖的点，是含有2n − 1个六边形的螺旋para-链)的一个完美匹配所构成的。根据引理2，可知的完美匹配的强迫数是n。子情形2：最大匹配M是由 (G删去中任意一点，得到的图)的一个一度点相关联的边，加上 (删去中一度点关联的这条匹配边饱和的点而得到的图)的三个一度点相关联的固定允许边，以及 (删去中这三个一度点关联的匹配边所饱和的点后是两个分支，分别是含有奇数个六边形的螺旋para-链)的一个完美匹配所构成的。的完美匹配是这两个分支各自的完美匹配的并。设其中一个分支含有x个不交的M-交错圈，那么另一个分支含有n − x个不交的交错圈。根据引理2，可知的完美匹配的强迫数是n。又由已知G的最大匹配是不饱和中任意一点的最大匹配，那么的这个一度点相关联的边一定是固定允许边，否则就不满足G的最大匹配是不饱和中任意一点的最大匹配，故不饱和中任意一点的最大匹配的强迫数是。

情形3：若G的最大匹配M是不饱和中任意一点的最大匹配，则M是由 (G删去中任意一点，得到的图)四个一度点相关联的边，并上 (删去中这四个一度点关联的这条匹配边饱和的点后是两个分支，分别是两个含有奇数个六边形的螺旋六角para-链)的一个完美匹配所构成的。的完美匹配是这两个分支各自的完美匹配的并。设其中一个分支含有x个不交的M-交错圈，那么另一个分支含有n − x个不交的M-交错圈。同理可知的完美匹配的强迫数是n。又由已知G的最大匹配是不饱和中任意一点的最大匹配，那么的这四个一度点相关联的边一定是固定允许边，否则就不满足G的最大匹配是不饱和中任意一点的最大匹配，故不饱和中任意一点的最大匹配的强迫数是n + 4。

推论6：令G是含有2n个六边形的螺旋六角para-链，则。

基金项目

国家自然科学基金项目(11761070，61662079)；2020年新疆维吾尔自治区研究生创新基金项目；新疆师范大学实验室开放课题(XJNUSYS082017A02)。

文章引用

李晶晶,边 红,于海征. 螺旋六角para-链的最大匹配的强迫数
The Forcing Number of Maximum Matching in Spiro Hexagonal Para-Chain[J]. 应用数学进展, 2020, 09(02): 251-256. https://doi.org/10.12677/AAM.2020.92029

参考文献