Definitions Applications to Benzoid Hydrocarbons



Download 173.63 Kb.
Page1/3
Date02.05.2018
Size173.63 Kb.
#47338
  1   2   3
OR 215 Spring 1999

Network Flows M. Hartmann

BIPARTITE MATCHING PROBLEMS


Definitions

Applications to Benzoid Hydrocarbons

Cardinality Bipartite Matchings

Minimum Cost Bipartite Matchings

Augmenting Path Approach

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






Download 173.63 Kb.

Share with your friends:
  1   2   3




The database is protected by copyright ©ininet.org 2024
send message

    Main page