Algorithmica (2013) 66:87-92 DOI 10.I 007/s00453-012-9625-7
Maximum Matching in Regular and Almost Regular Graphs
Raphael Yuster
Received: 24 October 2011 / Accepted: 15 February 2012 / Published online: 24 February 2012
copy;Springer Science Business Media. LLC 2012
Abstract Wepresent an O(n2 Iogn)-time algorithm that finds a maximum matching in a regular graph with n vertices. More generally, the algorithm runs in O(rn2 Iogn) time if the difference between the maximum degree and the minimum degree is less than r. This running time is faster than applying the fastest known general
matching algorithm that runs in O(石m)-time for graphs with m edges. whenever m = w(rnl.5 logn).
Keywords Maximum matching·Regular graph·Algorithm
- Introduction
A matching in a graph is a set of pairwise disjoint edges. A maximum matching is a matching of largest possible cardinality. The problem of finding a maximum matching is fundamental in both practical and theoretical computer science, and has numerous applications.
Maximum matching in bipartite graphs is significantly simpler than in general
graphs, as computations of augmenting paths do not encounter odd cycles. The sernshy; mal algorithm of Hopcroft and Karp [ I0] solves maximum bipartite matching in 0(,./nm) time, for graphs with n vertices and m edges. The first polynomial time algorithm for finding a maximum matching in a general graph was obtained by Edshy; monds [5]. The currently fastest deterministic algorithm for this problem, obtained
by Micali and Vazirani, runs in0 (radic;nm) time (see (7, 11, 12]). Faster algorithms are
known for several important special classes of graphs.
In this paper we consider the problem of finding a maximum matching in regular and almost regular graphs. Recently, there has been much progress in the bipartite
R. Yuster (区）
Department of Mathematics, University of Haifa, Haifa 31905, Israel e-mail: raphy@math.haifa.ac.il
全 Sp rin ger
88 Algorithmica (2013) 66:87-92
version of this problem, and the complexity of the bipartite case is now fairly undershy; stood. A simple consequence of Halls Theorem (see [3]) asserts that a regular bishy; partite graph has a perfect matching. Now, if the graph is d-regular and dis a power of 2, the following recursive approach due to Gabow and Kariv [6] yields an O(m)shy; time algorithm, which is significantly faster than applying the algorithm of Hopcroft and Karp. First, compute an Euler tour of the graph in time O(m) and then take all the even numbered edges of the tour, to obtain a spanning subgraph of degree d/2. Repeating this process eventually gives the desired I-regular spanning subgraph, i.e., a perfect matching. Extending this idea to the case where d is not a power of 2 is quite difficult. The fastest deterministic algorithm for this problem is due to Cole, Ost, and Schirra [4] and runs in O(m) time. This running time was recently shown to be optimal. It is shown by Goel, Kapralov, and Khanna in [8], that any deterministic algorithm for maximum bipartite matching requires Q(m) time (i.e., a deterministic algorithm must, essentially, examine all the edges). In fact, in the same paper, they achieve a breakthrough by presenting a randomized algorithm that computes a pershy; fect matching in O(n logn) expected time, with high probability. This improves an earlier randomized algorithm given in [9].
Unfortunately, these algorithms cease to work for non-bipartite graphs. Presently, the fastest algorithms for regular non-bipartite graphs are obtained using the general algorithms, and require 0(,./nm) time. The main result of this paper presents a sigshy; nificantly faster algorithm for sufficiently dense graphs. It also applies to graphs that are not necessarily regular, but are not too far from being regular.
For a graph G, the notations A(G) and /j (G) denote the maximum and minimum degree of G. respectively. A graph G is called r-almost-regular if A(G) - 8(G) lt; r. Thus, regular graphs are I -almost-regular. Our main result is the following.
Theorem 1.1 Let G be an r-almost-regular graph with n vertices. There is an algoshy; rithm that finds a maximum matching of G in O(rn2 logn)-time. In particular, if G is a regular graph then a maximum matching of G isfiJUnd in O(n2 logn)-time.
The main idea of the proof is to overcome three obstacles that arise when trying to extend the bipartite approach of [4, 6] to the non-bipartite case. The first probshy; lem is that the Euler tour approach causes imbalances when applied to non-bipartite graphs. and these need to be controlled. The second problem is that general regular graphs need not have a perfect matching, and hence maximum matchings computed on their subgraphs need to be considerably augmented. Finally, the number of such augmentations needs to be controlled in such a way that denser subgraphs require less augmentations, as computing augmenting paths requires time that is proportional to the number of edges. The details of the proof appear in the following section. The final section contains some concluding remarks.
-
Proof of the Main Result
- Almost Regular Subgraphs of Almost Regular Graphs
For a graph G, let m(G) denote the cardinality of a maximum matching of G. Supshy; pose that G has n vertices and is r-almost-regular. The following lemma establishes
全 Spri nger
Algorithrnica (2013) 66:87-92 89
a simple lower bound for m(G) in terms of n, r, (G). It isa consequence of Vizshy; ings Theorem [13] that states that E(G) can be partitioned into at most (G) I
matchings.
Lemma 2.1 lfG is an n-vertex graph which is r-almost-regularand (G) = d, then m(G ) 王 (d - r l)n/(2d 2).
Proof By the assumption, we have that 21E ( G ) I 王 (d - r l)n. By Vizings Theoshy;lt;
剩余内容已隐藏，支付完成后下载完整资料
正则和几乎正则图的最大匹配
拉斐尔·尤斯特
摘要 表示在具有n个顶点的常规图中找到最大匹配的O（n2 Iogn）时间算法。更一般来说，如果最大程度和最小程度之间的差值小于r，算法将以O（rn2 Iogn）时间运行。这个运行时间比应用最快的通用速度要快匹配算法在O（radic;nm）时间内运行，具有m个边缘的图形。每当m = w（rnl.5 logn）。
关键词 最大匹配·正则图·算法
简介
图中的匹配是一组成对不相交的边。最大匹配是最大可能的基数匹配。找到最大匹配的问题在实践和理论计算机科学中是至关重要的，并且具有许多应用。二分图中的最大匹配比一般来说要简单得多图形，因为增加路径的计算不会遇到奇数周期。Hopcroft和Karp [10]的sern mal算法在0(radic;nm）时间内解决了n个顶点和m个边缘的图形的最大二分匹配。通过Ed monds [5]获得用于在一般图中找到最大匹配的第一个多项式时间算法。这个问题的目前最快的确定性算法是获得的由Micali和Vazirani，运行在0（radic;nm）时间（见（7,11,12））。更快的算法是已知几个重要的特殊类图表。在本文中，我们考虑在常规和几乎规则的图形中找到最大匹配的问题。 最近，这个问题的两面版本已经取得了很大的进展，而且这个二分案件的复杂性现在已经相当得到了体现。霍尔定理的简单后果（参见[3]）断言，一个常规的二分图具有完美匹配。现在，如果图是d常规的，并且功率为2，则由Gabo和Kariv [6]得出的以下递归方法产生一个O（m）时间算法，这显着快于应用Hopcroft和Karp算法。首先，在时间O（m）中计算图的欧拉巡视，然后取出巡视的所有偶数边，以获得度d / 2的跨越子图。 重复该过程最终给出期望的I定期跨越子图，即完美匹配。将这个想法扩展到d不是2的幂的情况是相当困难的。这个问题的最快的确定性算法是由于Cole，Ost和Schirra [4]，并且运行在O（m）时间。这个运行时间最近被证明是最佳的。 Goel，Kapralov和Khanna在[8]中表明，任何用于最大二分匹配的确定性算法都需要Q（m）时间（即确定性算法本质上必须检查所有边缘）。事实上，在同一篇论文中，他们通过提出一种以O（n logn）预期时间计算每个匹配的随机算法，实现了突破。这改进了[9]中给出的较早的随机算法.
不幸的是，这些算法对于非二分图不再起作用。目前，使用通用算法获得了常规非二分图的最快算法，并且需要0（radic;nm）时间。本文的主要结果为足够密集的图形提供了显着更快的算法。 它也适用于不一定是规则的图形，但不是太常规的图形。
对于曲线G，符号△（G）和/ delta;（G）分别表示G的最大和最小程度。如果△（G）-delta;（G）lt;r，则图G被称为r-几乎规则。 因此，常规图表是我最常规的。 我们的主要结果如下。
定理1.1令G是一个具有n个顶点的r-几乎常规的图。有一个算法在O（rn2 logn）-time中找到G的最大匹配。特别地，如果G是常规图，则在O（n2 logn）-time中，G isfiJUnd的最大匹配。
证明的主要思想是克服在将[4,6]的二分法扩展到非两极案件时出现的三个障碍。第一个问题是，欧拉之旅方法在应用于非二分图时会导致不平衡。这些都需要控制。第二个问题是普通的常规图形不需要完美的匹配，因此在子图上计算的最大匹配度需要相当大的增加。 最后，需要以这样的方式来控制这种增加的数量，使得更密集的子图需要较少的增加，因为计算增加路径需要与边缘数成正比的时间。验证的详细信息将在以下部分中显示。 最后一节包含一些结语。
2 主要结果证明
2.1几乎常规图表的几乎常规子图
对于图G，令m（G）表示G的最大匹配的基数。表示G具有n个顶点并且几乎是常规的。以下引理用n，r，（G）来建立m（G）的简单下界。这是Vizing的定理[13]的结果，表明E（G）最多可以划分为（G） 1比赛。
引理2.1 lfG是一个n-顶点图，它是r-几乎规则的，（G）= d，则m（G）ge;（d-r 1）n /（2d 2）。
证明根据假设，我们有2|E（G）Ige;（d-r 1）n。 通过Vizing的Theorem m(G)ge;|E(G)| /（d I）。 因此，m（G）ge;（d-r 1）n /（2d 2）。
我们还需要遵循下列引理：遵循欧拉旅游在连续图形的多重图形中具有均匀度。
引理2.2任何图G =（V，E）都有跨越子图G使得「△（G）/2 - 1le;△（G）le;「△（G）/ 2 和 在这种情况下，。此外，G可以在O（|V| |E|）时间内构建。
证明我们可以假设G是连接的，否则我们可以分别证明每个连接的组件的结果。 让我们首先补充G，通过添加一个arbi trary完美匹配的Son顶点的奇数。因此，如果有奇数的2k个顶点，我们添加k个边，使得在所得到的多格式G *中，所有的度都是均匀的。当G *连接时，它具有由边缘e1，...，es组成的欧拉旅程其中在之前并且s=|E| k。如果 kgt; 0 我们总是选择e1到成为S的边缘。让F = { }是旅游偶数位置的边集。
跨越子图G具有边缘集合F E = F S.由于欧拉旅程可以构造在线性时间，复杂性要求如下。 仍然表明，G的最低程度和最大程度满足声明中的要求。 令x表示旅程的起始顶点，所以e1 =（x,y）和es =（z,x）。 首先考虑一个任意的顶点v，使得vx。 令（v）（（v））为G（resp.G）中的v的程度。 如果（v）是偶数，则（v）=（v）/ 2，这样我们就完成了。 如果（v）为奇数，则取决于S的独特边缘是否与S的入射有关，否则，（v）=（（v）十I）/ 2或（v）=（（v）-1）/2不在。因此，我们也在这种情况下完成， 仍然考虑x。 如果（x）是偶数，则我们对e1选择的假设意味着k = 0，并且G的所有度均为偶数。 在这种情况下，我们可以将x作为任何顶点，所以我们可以假设x是G中最大度的顶点。显然，（x）=（x）/ 2或（x）=（x）/ 2 - 1我取决于|E|是偶数还是奇数。 无论如何，我们完成了。 最后，如果（x）是奇数，则根据是偶数还是奇数，（x）=（（x） 1）/ 2或（x）=（（x）-1）/2 ）（显然我们必须有esisin;E，因为e1notin;E是具有x的S个事件的唯一边缘）。 因此，我们也在这种情况下完成。
从初始图G = Go开始，我们可以重复应用引理2.2获得跨越子图Go，...，Gt的序列，其中对于i = 1，...，t，和分别扮演G和G的角色。 更准确地说，我们得到以下推论：
推论2.3 令G为r-几乎规则的一个n顶点图，△（G）= d，令t = O（logd）为正整数。 有一系列n顶点图Go，...，G，其中Go = G，具有以下属性：
1. 是的跨越子图，对于i = 1，...，t。
2. △（）le;「d / 」。
3. 是O（max {r / ，1}）几乎是规则的。
此外，序列可以在O（nd）时间内构建。
证明该属性直接来自引理2.2。 复杂度要求遵循具有O（nd /）边缘以及从O（nd /））中由构成的事实。
2.2定理证明1.1
我们首先简要介绍定理1.1的证明。 该算法首先构建Go，...，G t的序列，其中Go = G，具有在推论2.3中列出的属性。 然后，我们逐渐计算最大匹配“自下而上”。 我们首先使用一般图形的标准匹配算法计算Gt的最大匹配Mt。然而，由于Gt相对稀疏，计算Mt相对较快。 然后我们移动到包含Gt的Gt-1，因此M1是Gt-1修改M1与Gt-1的最大匹配Mt-1的（不一定最大）匹配，需要相对较少的扩充路径步骤，我们显示如何快速执行。这个过程重复一遍，我们计算最大匹配Mi 的Gi 使用匹配的Mi 1作为起点。 最后，我们获得与G的最大匹配的期望的匹配Mo。本节的其余部分包含算法的形式描述。 我们从两个引理开始，说明我们的算法所需的已知结果。
正如引言中所指出的，目前最快的一般图表中最快匹配的算法运行在0（radic;nm）时间（见[7,11,12]）。
引理2.4 可以在O（radic;nm）时间内计算具有n个顶点和m个边缘的图形中的最大匹配。
Edmond的算法以及Micali-Vazirani算法[1]和Goldberg-Tarjan算法[7]是基于扩展路径的算法。 回想一下，匹配M的扩充路径P是以不匹配的顶点开始和结束的路径，并且其边缘在不匹配的边和边匹配之间交替。 显然，如果M是最大匹配，则不存在M的增加路径。证明相反也很容易 如果M不是最大匹配，则存在扩充路径。 因此，从任意匹配开始，并迭代地计算增加路径，最终以最大匹配结束。 [2,7,11]的算法都显示了如何在线性时间内计算扩充路径。
引理2.5 可以在O（m）时间内计算具有n个顶点和m个边缘的图中给定匹配M（ifit存在）的连接路径。
定理证明1.1 给定具有n个顶点和m个边缘的图G =（V，E），我们计算（线性时间）其最大度d =△（G），其最小度delta;（G），因此r = d-delta;（G） 1是最小的整数，使得G几乎是规则的。
我们可以假定mgt; r（特别是r lt;radic;n）否则运行定义为引理2.4的一般匹配算法的运行时间比定理1.1中规定的更快。
令t为d / le;radic;n的最小整数，并观察t = O（log d）。我们在O（nd）时间内构造Go = G的序列，Go = G，由推论2.3保证。 令si = m（Gi）表示i = 0，...，t的Gi的最大匹配的基数。 接下来我们将展示如何为每个Gi计算与|Mi|= si匹配的Mi。
使用称为引理2.4的算法计算Gt的最大匹配Mt。 假设我们已经计算了Mi，并希望计算Mi-1。 因为Gi是Gi-1的（跨越）子图，我们认为Mi是Gi-1（不一定是最大）匹配。 使用si-1-si扩充路径迭代序列，从Mi开始并重复应用引理2.5，直到不存在进一步的扩充路径，得到Gi-1的最大匹配Mi-1。 最后，算法根据需要返回M是最大匹配的M0。
仍然要分析该算法的时间复杂度，该算法由引理2.4的单一应用主导，以获得Mt，以及引理2.5的重复应用。 为了说明清楚，令mi表示i = 0，...，t，因此m = m0的Gi的边数。
使用引理2.4计算Mt需要O（nmt）时间。 由于△（Gt）le;d /le;radic;n 。我们有mt = O（），因此计算Mt的时间是O（）。
使用引理2.5从Mi获得Mi-1所需的应用数量为Si-1-si，每个应用程序需要O（mi-1）时间。因此，仍然要证明，当t = O（logd）时，仍然表明最后一个和的每个项是O（r）。
考虑图形Gi。 表示di =△（Gi），并记住Gi是O（max {r / 2i，1}）几乎是规则的。 特别地，ri = O（r）是ri-几乎常规的。 由引理2.1，由于si-1 lt;n / 2，我们有si-1-si = O（rn / di）。 此外，平凡地，mi-1 lt;d i-i / 2。 因此，我们得到了我们在最后一个等级中使用引理2.1的地方，特别指出di =△（Gi）gt;△（Gi一1）/ 2 -1 = di-1 / 2-1，意味着di-1 / di lt;3。
3结语
我们提出了一个O（rlogn）算法，用于在几乎常规的图形中进行最大匹配。 最有趣的开放问题是是否存在更快的算法。对于常规情况，[8]的结果表明任何确定性算法需要Omega;（m）时间。 我们注意到，对于3常规无桥图的特殊情况，已知几乎线性时间算法。 通过彼得森定理，这样的图形具有完美匹配，而Biedl等人 [I]显示如何在O（n n）时间中找到这样的匹配。
参考：
1. Biedl，T.C.，Bose，P.bull;Demaine，E.D.bull;Lubiw，A .:效率算法Petersen的匹配定理。 In：Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms（SODA），pp.130-139。 SIAM，Philadelphia（1999）
2. Blum，N .:一般图形中最大匹配的新方法。 In：Proceedings of the 17th International Colloquium on Automata，Languages and Programming（ICALP），pp。586-597（1990）
3. Bollobas，B .:极值图论。学术出版社，圣地亚哥（1978）
4. Cole，R.，Ost，K.bull;Schirra，S。：o-e-elogd中的边缘着色二分法。 Combinatorica 21（1），5-12（2001）
5. Edmonds，J .:路径，树木。和花。能够。 J. Math。 17（3），449-467（1965）
6. Gabow，H.N.，Kariv，0：边缘着色二分图和多图的算法。 SIAM J. Comput。 11多1 17（1982）
7. Gabow，H.N.，Tarjan，R.E。：用于一般图匹配问题的更快缩放算法。 J.ACM 38（4）
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[28300]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
