英语原文共 5 页，剩余内容已隐藏，支付完成后下载完整资料

---

分数匹配数比和图形的匹配数的比的区别

IlkyooChoia,JaehoonKimb,SuilOc,*

a数学科学系,韩国科学技术院,大田,韩国

b数学学院,伯明翰大学, 埃德巴斯顿,伯明翰, 英国

c数学系, 西蒙弗雷泽大学,伯纳比,不列颠哥伦比亚,V5A2R7,加拿大

文章信息： 关键词：

2015年4月8号收到初稿 匹配数

2015年12月5号采纳 分数匹配数

2015年12月23号网络发行

摘要：

给定一个图，的匹配数，记为的最大的匹配，的分数匹配数，记为的最大的分数匹配。本文中我们证明了如果是一个定点的连接图且既不是也不是，则有和。显然两个都是不等式，然后我们描述了这些图的无限族在哪儿是相等的。

1 引言

未定义的术语见[5]。在本文中，将始终表示一个给定的图形的顶点数目。图中的一个匹配的是一组两两不相交的边缘。在图完美匹配，其中每个顶点具有匹配的入射边缘匹配;它的大小肯定是，且。的一个分数匹配是一个函数使得对于每个顶点，，且是一组边入射到，又分数匹配数的大小是。给定一个图，的匹配数，记为的最大匹配，的分数匹配数，记为的最大的分数匹配。

给定一个分数匹配，因为对于每个顶点，我们有，这意味着。通过观察每一个匹配作为一个分数匹配它遵循对于每一个图有，但是等式不一定成立。例如，一个正则图的分数匹配数等于通过在每个边设置权重，但是这个正则图的匹配数可以远小于。因此理所应当去找到和在一个(连接)图之间最大的区别。

在第三段跟第四段中，我们证明和的紧上界，分别，对于一个顶点连接图，我们刻画图的无限族实现了两个结果相等。由于这两个结果的推论，我们得到一个顶点连接图在和都有上界，这样我们描述的这些图在两个边界都实现了相等。

我们证明在匹配数中运用著名的贝格塔特公式[1]和它的分数类似物一样。我们也运用这样的事实，一个分数匹配，有，这样对于每个边有，还有一些事实的改进。我们可以用两种不同的技术证明定理8和6，为了读者着想，我们演示证明定理8和6的每一种方法。

2 工具

在本节中，我们将介绍我们证明主要成果所使用的工具。为了证明定理6，我们将利用定理1和定理2。对于一个图，用表示在中具有奇数个顶点部件的数量。给定一个图且，通过定义的不足之处，使得。定理1是著名的贝格塔特公式，是塔特的单因素定理[4]中的一个通用版本。

定理1（[1]）对于任意一个顶点图，。

对于贝格塔特公式中的分数类似物，用表示在中孤立顶点的数量。给定一个图且，有和。定理2是贝格塔特公式的分数版本。它也是贝特的单因素定理中的分数类似物，是这样说的有一个分数的完美匹配当且仅当对于所有（隐含在Pulleyblank[2]）有时,所以一个分数的完美匹配是一个分数匹配,即。

定理2（[3]见定理2.2.6）对于任意一个顶点图，。

当我们描述定理6和8在边界的等式时，我们需要下列命题。回想一下是由顶点集合的一个子集引起的图。

命题3（[3]见命题2.2.2）下面是一个等价的图

(1)有一个分数的完美匹配。

(2)顶点集的一个分割，有对于每一个,图为图或哈密顿图。

(3)顶点集的一个分割，有对于每一个,图为在一个有奇数个顶点的图或哈密顿图。

定理4和观察5被用来证明定理8。

定理4（[3]见定理2.1.5）对于任意一个图，都有一个分数匹配，这样对于每个边有。

给定一个分数匹配,一个未加权顶点是一个的顶点，一个完整的顶点是对于某一些顶点有的一个顶点。注意也是一个完整的顶点。一个边是一个的边。注意一条边的存在保证两个完整的顶点的存在。当时，一个图中的一个顶点集是独立的，所以图是图引起的。

观察5在满足定理4的条件的一个顶点图的分数匹配中，使得成为一个在中有着最多数量的边的一个分数匹配。然后，我们有以下几点：

(1)由边引起的图是奇数周期的联合。此外，如果和是在图中两个不相交的周期由边引起的，那么就没有边，使得的和。

(2)未加权顶点的集合是独立的。此外，每一个未加权的顶点相邻的只有一个完整的顶点。

(3)，，，所以，还有分别是未加权顶点的数量，一条边的数量，和由图的边引起的长度为的奇数周期的数量。

证明(1)一个由边引起的图不能有一个至少为3度的顶点，因为每个顶点有。因此图必须是路径或周期中一个不相交的并集，然后由路径或权重为或者的偶数周期上更换每个边的权重为，我们可以得到一个分数匹配其中有一样的分数匹配数和更多权重为的边，与的选择相矛盾。因此由边引起的图是奇数周期的并集。如果有一条边有和，所以和是有一些边引起的不同的两个奇数周期，此时，因此对于每个顶点有。通过替换分别在边上权重为和的边和在边上权重为在和上的边，还有在和上权重为和的边，不违反分数匹配的定义，我们得到一个分数匹配其中有一样的有更多权重为的边的分数匹配数，所以是一个矛盾。因此，我们得到了想要的结果。

(2)如果两个未加权顶点和是相邻的，此时我们可以加一个正权在边上，所以跟的选择相矛盾。如果存在一个未加权顶点，没有入射到任何完整的顶点，此时必须与一个顶点相邻，所以对于一些顶点和有和。通过，，的权重由，和替换为，，，我们得到一个分数匹配其中有一样的有更多权重为的边的分数匹配数，所以是一个矛盾。

(3)由，和的定义，我们可以得到想要的结果。

图1定理6(i)和8(i)中所有有五个顶点的图

图2定理6(ii)和8(ii)所有的图

3 ,的上确界

该图有分数匹配数和顶点连通图的匹配数之间的最大差异的结构是什么？该图可能有大的分数匹配数和小的匹配数。所以，由贝格塔特公式及其分数版本，它们可以具有一个顶点子集，使得几乎所有的的奇数分量的至少三个顶点，以获得具有小的分数缺乏和大缺陷。这是我们的定理6的证明背后的想法。

定理6设，如果是一个个结点的连通图，则有，且仅当有以下条件时等式才成立：

(i)和是的一个子图或者是的一个子图（见图1），或

(ii)有一个顶点所以组成了所有除了只有一个顶点的图（见图2）。

证明 在所有的最大缺陷顶点子集，令为最大集。根据贝格塔特公式有，通过的选择，所有的组件都有一个奇数的顶点数。令为的孤立点，再令为其他组成部分的数量。这意味着。如果，则，取决于的奇偶性。在这种情况下，，因为。

现在，假设表示非空。

情况1：。因为，，且，我们可以得到

。

情况2：。因为，，且，我们可以得到

。

在计算的每一步中，等式中的等式是相等的。当时，我们得到结论(i)由命题3所示。在情况1中，我们得不到相等。在情况2中，我们可以得到，，还有。因为是连通的，是或除了只有一个顶点的成分。如果的组件是一个复制的，然后通过选择中央顶点的路径，我们可以得到，但，所以矛盾。因此，我们得到了想要的结果。

推论7 对于任意顶点图，我们可以得到，且等式仅当是复制中不相交的并集时成立。

证明 首先，我们表明当时，是连通的，则，仅当等式成立。当时，则，这意味着。当，则。注意有，还有。此外仅当等式成立。当时，则有或者中包含为一个子集。因为，又，我们得出结论对于任意正整数，有。事实上， 当时，此时根据定理6，区别肯定最多为。因此，对于连通图，仅当等式成立。

现在如果我们假设是不连通的，为连通图的不相交并集。令，且。因为

，

仅当每个都是的一个复制时等式成立，且。

4 的上确界

为了证明定理8的上界，我们还可以利用贝格塔特公式和它类似的分数。不过，我们提供另一种方法去证明这个定理。

定理8设，如果是一个有个结点的连通图，则，仅当有以下条件的情况下等式成立：

(i)和是的一个子图或者是的一个子图（见图1），或

(ii)有一个顶点所以组成了所有除了只有一个顶点的图（见图2）。

证明 在一个大小等于的个结点的图中的所有分数匹配，令为一个分数匹配使得的边是最大的。我们遵循观察5中的符号。

情况1：。因为是连通的，且，这里只存在一个使得，且不等于零，。现在我们可以得到

。

情况2：且。通过观察5中的(2)部分，这不可能发生。

情况3：且。因为，通过观察5中的(3)部分，我们可以得

情况4：且。因为，通过观察5中的(3)部分，我们可以得到

在每一步计算中边界中的等式需要相等；我们只需要检查情况1和情况2。在情况1中，我们有，这说明和包含一个的复制。在情况3中，我们有和，这说明被边引起的图是的并。因此有一些正整数的一个子图。注意通过观察5中的(2)部分这里有一个边在的复制和任意的复制之间。当然，通过观察5中的(1)部分这里没有边在任何一对三角形中。令和为对应于复制的两个结点。如果在中有两个不同的三角形跟，那么和分别是随着跟来的，现在我们有，这意味着我们不能在情况3中的第一个不等式中得到等式。因此，我们得出结论包含一个作为的复制的子图或者一个顶点，所以的所有组成是除了只有一个顶点的。

推论8 设至少有一个边的任意顶点的图为，我们有，仅当为的复制中不相交的并时等式成立。

证明 通过推论7的证明，当，是连通的，则，仅当时等式成立。如果我们假设是不连通的，为连通图的不相交并集。令，且。不失一般性，我们可能假设，且所有。现在我们可以得到

仅当每个为的一个复制时等式成立，且。

致谢

第一作者是部分由政府朝鲜（MSIP）（NRF-2015R1C1A1A02036398）资助的韩国（NRF）授予的国家研究基金会的支持。第二作者研究了部分在欧盟第七框架计划（FP/2007-2013）/ ERC资助协议No.306349的欧洲研究理事会的支持。

参考文献

[1] C.Berge,Surlecouplagemaximumdrsquo;ungraphe,C.R.Acad.Sci.Paris247(1958)258–259. [2]W.R.Pulleyblank,Minimumnodecoversand2-bicriticalgraphs,Math.Program.17(1)(1979)91–103.

[3]E.R.Scheinerman,D.H.Ullman,FractionalGraphTheory:ARationalApproachtotheTheoryofGraphs,Wileyamp;Sons,2008.

[4] W.T.Tutte,Thefactorizationoflineargraphs,J.Lond.Math.Soc.22(1947)107–111. [5]D.B.West,IntroductiontoGraphTheory,PrenticeHall,Inc.,UpperSaddleRiver,NJ,2001.

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[31195]，资料为PDF文档或Word文档，PDF文档可免费转换为Word