Definitions Applications to Benzoid Hydrocarbons

Download 173.63 Kb.
Size173.63 Kb.
  1   2   3
OR 215 Spring 1999

Network Flows M. Hartmann



Applications to Benzoid Hydrocarbons

Cardinality Bipartite Matchings

Minimum Cost Bipartite Matchings

Augmenting Path Approach

Bipartite Matching Algorithm


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.


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?



Download 173.63 Kb.

Share with your friends:
  1   2   3

The database is protected by copyright © 2023
send message

    Main page