Talk:Matching (graph theory)

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)

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)

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

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

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)

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)

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)

---

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)

---

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)

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)

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)

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)

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)

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)

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

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)

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)

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)

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)

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)

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)