Editing Matching (graph theory) (section)

== Applications ==

=== Matching in general graphs ===
* A '''Kekulé structure''' of an [[Aromaticity|aromatic compound]] consists of a perfect matching of its [[skeletal formula|carbon skeleton]], showing the locations of [[double bond]]s in the [[chemical structure]]. These structures are named after [[Friedrich August Kekulé von Stradonitz]], who showed that [[benzene]] (in graph theoretical terms, a 6-vertex cycle) can be given such a structure.<ref>See, e.g., {{citation|title=On some solved and unsolved problems of chemical graph theory|last1=Trinajstić|first1=Nenad|author-link=Nenad Trinajstić|last2=Klein|first2=Douglas J.|last3=Randić|first3=Milan |author-link3=Milan Randić|journal=International Journal of Quantum Chemistry|year=1986|volume=30|issue=S20|pages=699–742|doi=10.1002/qua.560300762}}.</ref>
* The [[Hosoya index]] is the number of non-empty matchings plus one; it is used in [[computational chemistry]] and [[mathematical chemistry]] investigations for organic compounds.
* The [[Chinese postman problem]] involves finding a minimum-weight perfect matching as a subproblem.

=== Matching in bipartite graphs ===
* [http://community.topcoder.com/stat?c=problem_statement&pm=2852&rd=5075 Graduation problem] is about choosing minimum set of classes from given requirements for graduation.
* [[Transportation theory (mathematics)|Hitchcock transport problem]] involves bipartite matching as sub-problem.
* [[Subgraph isomorphism problem|Subtree isomorphism]] problem involves bipartite matching as sub-problem.