Talk:Matching (graph theory)

This is the talk page for discussing improvements to the Matching (graph theory) article.
This is not a forum for general discussion of the article's subject.

Put new text under old text. Click here to start a new topic.
New to Wikipedia? Welcome! Learn to edit; get help.

Article policies

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL

Not quite clear, or at least to me not quite clear

What is "non-adjacent edges" or "pairwise non-adjacent edges"? — Preceding unsigned comment added by 2001:4643:E6E3:0:2DBF:E087:EDBA:7D21 (talk) 11:08, 8 September 2018 (UTC)[reply]

Non-adjacent edges means that the edges do not 'touch' (they have no common vertices). Pairwise, I agree, is not required here (I don't know what that would even mean in this context). Have removed. Montyevans (talk) 12:02, 26 April 2023 (UTC)[reply]

Pairwise means that each pair of edges does not touch. It is stronger than merely requiring that there be no common point where all the edges touch. —David Eppstein (talk) 16:12, 26 April 2023 (UTC)[reply]

Missing aspects

There is something I miss on this page. It does not mention that there are both maximum cardinality and maximum value matching problems. I am not sure if these are the "correct" names. Maximum cardinality bipartite matching: All edges are worth equally much. Can be solved with Maximum flow by adding a super-source and a super-sink. Maximum value bipartite matching: Edges are not worth the same, and you want to maximize the sum of the chosen edges. Can be solved with Minimum cost maximum flow. Nils Grimsmo 16:22, 6 December 2005 (UTC)[reply]

The former is a subset of the latter, wherein all edges have equal weights.

we should mention the difference between maximal matchings and maximum matchings. The first is set-theoretical maximum, which holds that there are no other edge, we can add to the matching without destroying its matching character. The latter is a matching with the maximal number of chosen edges, which is - of course - also maximal. Please corerct my mistakes if ayou see any of them w.r.t. the difference mentiones above.

I think it needs correction: a matching cannot contain an augmenting path (can it? but the graph can). But I'm not familiar with this result so I'm not going to edit it.

A matching can contain an Augmenting path. A Perfect Matching cannot, and a Maximum Sized Matching (one with the largest number of edges possible) cannot. A single edge in any graph is technically considered a matching. ANY collection of disjoint edges is a matching. Rob 00:52, 25 August 2006 (UTC)[reply]

Really the graph contains an augmenting path with respect to the (non-maximum) matching. Adking80 (talk) 21:49, 18 July 2008 (UTC)[reply]

Why does Kekule structure redirect here?137.205.74.230 (talk) 00:23, 8 November 2008 (UTC)[reply]

Because a Kekule structure is a type of matching and there is not currently a more appropriate article to redirect to. In the notes section of the matching article, it says “In chemistry, a Kekulé structure of an aromatic compound consists of a perfect matching of its carbon skeleton...” —David Eppstein (talk) 00:29, 8 November 2008 (UTC)[reply]

Mathematically David Eppstein's statement is correct: "Kekule structure is a type of matching", but unfortunatelly this is not obviously for majority of chemists. There is a good link in Benzene article: A. J. Rocke (1985). "Hypothesis and Experiment in the Early Development of Kekule's Benzene Theory". Annals of Science 42: 355–81. doi:10.1080/00033798500200411 I am sure Kekule structure may be redirected to the Benzene article, it would be more appropriate article to redirect to. Surely the section about Kekule structure should be added to the article -- the article is incomplete, but it is not reason for this strange redirection. Also a single article about Kekule structures in chemistry is necessary - see, John D. Roberts, Marjorie C. Caserio, Basic Principles of Organic Chemistry,(W. A. Benjamin,Inc.,1964) for source. Kekule structure has to be linked to chemical article ruther then to mathematical article. --Tim32 (talk) 23:51, 8 November 2008 (UTC)[reply]

I'm guessing a separate article on Kekule structures, that describes both what they mean in chemistry and how they can be interpreted mathematically as matchings, would be preferable either to the present redirect or to an alternative chemical redirect. It seems to be a sufficiently notable topic to deserve its own article. But I don't have the expertise to write that article. —David Eppstein (talk) 01:33, 9 November 2008 (UTC)[reply]

From the article: "A maximum weighted bipartite matching is defined as a perfect matching where the sum of the values of the edges in the matching have a maximal value".

Does this mean the maximum WBGM is the one that maximizes the total cost? From the assignment problem article, one infers the opposite. Or does "value" mean something different in this context? Budsbd (talk) 12:32, 13 February 2009 (UTC)[reply]

The article says: "There is a polynomial time algorithm to find a maximum matching or a maximum weight matching in a graph that is not bipartite; it is due to Jack Edmonds, is called the paths, trees, and flowers method or simply Edmonds's algorithm, and uses bidirected edges."

I believe that the Edmond's algorithm is not the one that we want, so I removed the link. I think we want an article that explains Edmonds' perfect matching papers:

Jack Edmonds. 'Maximum matching and a polyhedron with 0,1-vertices'. Journal of Research of the National Bureau of Standards, 69B:125-130, 1965.
Jack Edmonds. 'Paths, trees, and flowers'. Canadian Journal of Mathematics, 17:449-467, 1965.

Is there an article on max-weighted perfect matchings and blossom-shrinking? If not, than there probably should be one. Although I am not qualified enough to write it. 203.143.165.110 (talk) 08:13, 20 July 2009 (UTC)[reply]

Invalid sentence

This article says, "However, a remarkable theorem of Kasteleyn states that the number of perfect matchings in a planar graph can be computed exactly in polynomial time." However, if this were the case, FP=#P, which is an even stronger claim than P=NP! If this sentence were true you would get P=NP and a whole lot more! Please contrast with [[1]]. I deleted this sentence a few days ago, but someone reverted the page to its original (very wrong) state. —Preceding unsigned comment added by 131.107.0.81 (talk) 21:49, 2 July 2010 (UTC)[reply]

Actually, I just realized you put planar graph. My mistake! So sorry! —Preceding unsigned comment added by 131.107.0.81 (talk) 21:56, 2 July 2010 (UTC)[reply]

I think there is also an invalid sentence describing the maximum matchings. Both figures show "maximum matchings" with red edges.... But the two are clearly different. — Preceding unsigned comment added by 68.229.202.24 (talk) 02:01, 14 April 2012 (UTC)[reply]

Try reading it again. The first one shows maximAL matchings, the second one shows maximUM matchings. They mean different things. —David Eppstein (talk) 02:06, 14 April 2012 (UTC)[reply]

I think there is a typo in the sentence "the sum of the matching number and the edge covering number equals the number of vertices.[2] If there is a perfect matching, then both the matching number and the edge cover number are |V| / 2" -- the sum should equal |E|, not |V|.

Rename Matching (graph theory)

I think this article could be renamed to Matching (graph theory), so that the Matching page could be a disambiguation page for all other senses of the term. When googling the term, the top results were rather for Matching (statistics) or Matchmaking. Mikael Häggström (talk) 15:17, 9 October 2009 (UTC)[reply]

Seems like a reasonable plan to me. —David Eppstein (talk) 15:31, 9 October 2009 (UTC)[reply]

I agree. Renamed. Feel free to create the disambiguation page. I can try to disambiguate at least some links pointing to matching. — Miym (talk) 15:51, 9 October 2009 (UTC)[reply]

And to clarify: we already have Matching (disambiguation) which should be used to replace the current redirect Matching, but I don't know how to do it properly without losing history, etc. — Miym (talk) 15:53, 9 October 2009 (UTC)[reply]

I moved it to Matching — it required an admin to delete the redirect left behind by the earlier move of the graph matching article, but other than that there were no significant complications with getting the history in the right place. —David Eppstein (talk) 16:00, 9 October 2009 (UTC)[reply]

Better Introduction

I think the introduction could be made far more interesting and explain what it is graph theory is trying to achieve, not just the formal definitions. This could include some interesting applications and examples, especially where graph matching is a better solution than most other approaches. The introduction should pull the reader in so that he/she thinks: "wow, this is cool, I could use this ...". This is definitely not the case currently as it seems to be aimed more at mathematicians. — Preceding unsigned comment added by Jecilliers (talk • contribs) 20:10, 1 March 2011 (UTC)[reply]

Matching Polynomial

I posted a comment on the talk page for the article for Mathching polynomials (not in the section here) about a possible error for K_m,n in terms of the Laguerre polynomial. If anyone would have a look, thanks. --Steve K — Preceding unsigned comment added by 98.141.141.194 (talk) 15:57, 30 November 2012 (UTC)[reply]

Complexity section question

The complexity section says the general counting problem is #P-complete, but does not mention clearly whether this is also true for the bipartite case.

Thomaso (talk) 19:29, 30 April 2013 (UTC)[reply]

very doubtful statement

It is currently stated that

"Given a matching M, an alternating path is a that begins with an unmatched vertex and is a [2]path in which the edges belong alternatively to the matching and not to the matching. "

This seems dubious. There is a word missing. Also, if the path begins at an unmatched vertex, then the first edge in the path, which starts from the unmatched vertex, therefore by definition cannot be an edge which belongs to the matching. Also, alternatively is not the same as alternately. The last part of the quoted sentence should probably read " is a path in which the edges belong alternately to the sets of edges which are not, and which are, in the matching. Or something like that.Lathamibird (talk) 14:23, 2 December 2015 (UTC)[reply]

Is simpleness assumed?

Some results seem to require the absence of loops. I read:

In some matchings, all the vertices may be incident with some edge of the matching, but this is not required and can only occur if the number of vertices is even.

But if we take V = {a} and E = {aa} then we have a perfect matching in an odd-order graph. Likewise,

A near-perfect matching is one in which exactly one vertex is unmatched. This can only occur when the graph has an odd number of vertices, (...)

But we can take V = {a, b} and E = {aa} and we have a near-perfect matching in an even-order graph. So are the results wrong, or the definition incomplete?__Gamren (talk) 16:03, 30 May 2018 (UTC)[reply]

Loops are unusable because they share a common end vertex with themselves. —David Eppstein (talk) 18:15, 30 May 2018 (UTC)[reply]

@David Eppstein: But... so does a non-loop edge. A non-loop edge shares two end vertices with itself.__Gamren (talk) 19:25, 30 May 2018 (UTC)[reply]

Edges have two endpoints. Loops have both endpoints in the same place. So their two endpoints are shared by a single vertex. That doesn't happen with other edges. —David Eppstein (talk) 20:03, 30 May 2018 (UTC)[reply]

Okay, I've added that requirement, even though it might be already lie in the word "non-adjacent".__Gamren (talk) 17:54, 5 June 2018 (UTC)[reply]

Misleading reference

Under "Algorithms and computational complexity", the reference the nlog^3(n) algorithm is quite misleading, since that algorithm is only valid for planar graphs. The Hopcroft-Karp algorithm should be mentioned there instead. — Preceding unsigned comment added by 2607:B400:24:0:DC56:2355:87F2:F908 (talk) 11:40, 25 March 2019 (UTC)[reply]

Not the only problem there. Also the weighted case is listed with times from unweighted algorithms. I've rearranged, I hope for the better. —David Eppstein (talk) 12:24, 25 March 2019 (UTC)[reply]