OR 215 Spring 1999
Network Flows M. Hartmann
BIPARTITE MATCHING PROBLEMS
Definitions Applications to Benzoid Hydrocarbons Minimum Cost Bipartite Matchings Bipartite Matching Algorithm
DEFINITIONS
A matching M in an undirected graph is a set of arcs no two of which meet at a common node.
A matching
in a bipartite graph which has no per-
fect matching.
A matching M is perfect if every node is met by some arc in the matching.
The cardinality matching problem asks for a maximum cardinality matching.
Suppose there is a cost cij associated with each arc (i,j).
The min-cost (perfect) matching problem asks for a minimum cost (perfect) matching.
DETERMINING CHEMICAL BONDS
Certain properties of chemical compounds can be studied using a topological model in which atoms are represented by nodes and chemical bonds by lines. Organic chemists are intersted in benzoid hydrocarbons, whose “resonance energy” is related to the number of perfect matchings.
A perfect matching in the bipartite graph of a benzoid hydrocarbon, correspon-ding to an assignment of single and double chemical bonds.
This graph has 12 perfect matchings, some of which may represent more stable configurations of bonds.
How can we determine if such an abstract graph has
a perfect matching? How can we count the number of perfect matchings in such a (planar bipartite) graph?
Which of these chemical compounds is more stable?
anthracene,
benzo[de]napthalene
Share with your friends: | 
