Editing Bipartite graph (section)

===Matching===
{{main|Matching (graph theory)}}
A [[Matching (graph theory)|matching]] in a graph is a subset of its edges, no two of which share an endpoint. [[Polynomial time]] algorithms are known for many algorithmic problems on matchings, including [[maximum matching]] (finding a matching that uses as many edges as possible), [[maximum weight matching]], and [[stable marriage]].<ref>{{citation
 | last1 = Ahuja | first1 = Ravindra K.
 | last2 = Magnanti | first2 = Thomas L.
 | last3 = Orlin | first3 = James B.
 | contribution = 12. Assignments and Matchings
 | pages = 461–509
 | publisher = Prentice Hall
 | title = Network Flows: Theory, Algorithms, and Applications
 | year = 1993}}.</ref> In many cases, matching problems are simpler to solve on bipartite graphs than on non-bipartite graphs,<ref>{{harvtxt|Ahuja|Magnanti|Orlin|1993}}, p. 463: "Nonbipartite matching problems are more difficult to solve because they do not reduce to standard network flow problems."</ref> and many matching algorithms such as the [[Hopcroft–Karp algorithm]] for maximum cardinality matching<ref>{{citation|first1=John E.|last1=Hopcroft|author1-link=John Hopcroft|first2=Richard M.|last2=Karp|author2-link=Richard Karp|title=An ''n''<sup>5/2</sup> algorithm for maximum matchings in bipartite graphs|journal=SIAM Journal on Computing|volume=2|issue=4|pages=225–231|year=1973|doi=10.1137/0202019}}.</ref> work correctly only on bipartite inputs.

As a simple example, suppose that a set <math>P</math> of people are all seeking jobs from among a set <math>J</math> of jobs, with not all people suitable for all jobs. This situation can be modeled as a bipartite graph <math>(P,J,E)</math> where an edge connects each job-seeker with each suitable job.<ref>{{harvtxt|Ahuja|Magnanti|Orlin|1993}}, Application 12.1 Bipartite Personnel Assignment, pp. 463–464.</ref> A [[perfect matching]] describes a way of simultaneously satisfying all job-seekers and filling all jobs; [[Hall's marriage theorem]] provides a characterization of the bipartite graphs which allow perfect matchings. The [[National Resident Matching Program]] applies graph matching methods to solve this problem for [[Medical education in the United States|U.S. medical student]] job-seekers and [[Residency (medicine)|hospital residency]] jobs.<ref>{{citation
 |last         = Robinson
 |first        = Sara
 |date         = April 2003
 |issue        = 3
 |journal      = SIAM News
 |page         = 36
 |title        = Are Medical Students Meeting Their (Best Possible) Match?
 |url          = http://www.siam.org/pdf/news/305.pdf
 |access-date  = 2012-08-27
 |archive-url  = https://web.archive.org/web/20161118115832/http://www.siam.org/pdf/news/305.pdf
 |archive-date = 2016-11-18
 |url-status     = dead
}}.</ref>

The [[Dulmage–Mendelsohn decomposition]] is a structural decomposition of bipartite graphs that is useful in finding maximum matchings.<ref>{{harvtxt|Dulmage|Mendelsohn|1958}}.</ref>