Definitions Applications to Benzoid Hydrocarbons
Download 173.63 Kb.
|
- Navigate this page:
- Examples
- Proposition
- AUGMENTING PATH THEOREM Theorem.
- BIPARTITE CARDINALITY MATCHING ALGORITHM algorithm
- LABELLING APPROACH Idea
- UNIQUE LABEL PROPERTY
AUGMENTING PATH APPROACHThe graph can only be oriented if it is bipartite, so next we reinterpret the augmenting path approach in terms of matchings. 
Let M
be a matching. (1,4), (2,6), (7,11), (9,12) and (10,14) are matched arcs. 1, 2, 4, 6, 7, 9, 10, 12 and 14 are matched nodes. A path P (or cycle C) is alternating (with respect to M) if it alternates between matched and unmatched arcs. An alternating path is even or odd depending on how many arcs it contains (an alternating cycle must be even). Examples: 8-12-9-13 is even; 10-14-11-7-3 is odd. An augmenting path is an alternating path that starts and ends at an unmatched node. Examples: 8-12-9-13 or 13-10-14-11-7-3. Must augmenting paths be odd or even? Redesignating arcs along an augmenting path increases the size of a matching: 
This is conveniently described in terms of the symmetric difference, S T = (S \ T) (T \ S).
M M P is called an augmentation. Proposition: If M and M* are two matchings, then every component of the subgraph G* = (N, M M*) has one of the following structures: isolated nodes, alternating paths, or alternating cycles. Proof: Every node in G* has degree 0, 1 or 2. Thus G* is composed of isolated nodes, paths and cycles, which must necessarily be alternating. 
AUGMENTING PATH THEOREM Theorem. If a node p is unmatched in a matching M, and there is no augmenting path starting at p, then p is unmatched in some maximum matching. Proof: Let M* be a maximum matching. If node p is un-matched in M* then there is nothing to show. If p is matched in M*, consider M M*. The fact that p is unmatched in M implies that p must be the endpoint of an alternating path in G*. The only two possibilities are: 
The first identifies an augmenting path starting at p. If P is a path of the second kind, then M' = M* P is a maximum matching not containing p. BIPARTITE CARDINALITY MATCHING ALGORITHM algorithm CARDINALITY mATCHING; begin M := ;
for each unmatched node p N do if there is an augmenting path P starting at p then augment M M P else delete p and its incident arcs from G; end Improvement: Instead of M := , start with a maximal matching, which can be found in O(m) time. Is the algorithm correct? How can we find an augmenting path?
LABELLING APPROACH Idea: Grow a tree T of alternating paths rooted at p. Label each node “odd” or “even” based on the type of alternating path.    
root How can we extend such a path? 
root
UNIQUE LABEL PROPERTY Does the labelling procedure always find an augmenting path when there is one? Unique label property. A graph G has the unique label property (with respect to a matching M and a node p) if the same labels (even or odd) are assigned, irrespective of the order in which the nodes are examined.
root
Note: Bipartite graphs have the unique label property. Directory: downloads downloads -> Northern England’s set-jetting locations downloads -> Dynatest 3031 lwd light Weight Deflectometer downloads -> Forth coming competitive exams downloads -> Brush High School Morning Announcements Friday, September 05, 2014 all school downloads -> Year 9 The Arts — Music downloads -> Years 7 and 8 standard elaborations — Australian Curriculum: Music draft downloads -> Chris Young sets 2016 “I’m Comin’ Over” Tour headlining dates downloads -> Slavery and Abolition: the Plymouth Connection Introduction downloads -> Summer Assignment Download 173.63 Kb. Share with your friends:
|