U of I CS 473 - Network Flow (16 pages)

Previewing pages 1, 2, 3, 4, 5 of 16 page document View the full content.
View Full Document

Network Flow



Previewing pages 1, 2, 3, 4, 5 of actual document.

View the full content.
View Full Document
View Full Document

Network Flow

32 views

Lecture Notes


Pages:
16
School:
University of Illinois
Course:
Cs 473 - Compiler Design

Unformatted text preview:

7 5 Bipartite Matching Chapter 7 Network Flow Slides by Kevin Wayne Copyright 2005 Pearson Addison Wesley All rights reserved 1 Matching Bipartite Matching Matching Input undirected graph G V E M E is a matching if each node appears in at most edge in M Max matching find a max cardinality matching Bipartite matching Input undirected bipartite graph G L R E M E is a matching if each node appears in at most edge in M Max matching find a max cardinality matching 1 1 2 2 3 3 4 4 5 5 matching 1 2 3 1 4 5 L 3 R 4 Bipartite Matching Bipartite Matching Bipartite matching Input undirected bipartite graph G L R E M E is a matching if each node appears in at most edge in M Max matching find a max cardinality matching Max flow formulation Create digraph G L R s t E Direct all edges from L to R and assign infinite or unit capacity Add source s and unit capacity edges from s to each node in L Add sink t and unit capacity edges from each node in R to t 1 1 2 2 3 3 4 4 5 5 G 1 max matching 1 1 2 2 3 3 4 4 5 5 1 1 1 2 2 3 3 4 4 L s L R t R 5 6 Bipartite Matching Proof of Correctness Bipartite Matching Proof of Correctness Theorem Max cardinality matching in G value of max flow in G Pf Given max matching M of cardinality k Consider flow f that sends 1 unit along each of k paths f is a flow and has cardinality k Theorem Max cardinality matching in G value of max flow in G Pf Let f be a max flow in G of value k Integrality theorem k is integral and can assume f is 0 1 Consider M set of edges from L to R with f e 1 each node in L and R participates in at most one edge in M M k consider cut L s R t G 1 1 2 2 3 3 4 5 1 1 1 2 2 3 3 4 4 4 5 5 5 s 1 1 1 t s G G 7 1 1 1 1 2 2 3 3 2 2 3 3 4 4 4 4 5 5 5 5 t G 8 Perfect Matching Perfect Matching Def A matching M E is perfect if each node appears in exactly one edge in M Notation Let S be a subset of nodes and let N S be the set of nodes adjacent to nodes in S Q When does a bipartite graph have a perfect matching Observation If a bipartite graph



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Network Flow and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Network Flow and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?