
Graph Matching and Maximum Matching Problem Analysis
Explore the concepts of graph matching and the maximum matching problem in undirected graphs. Understand definitions like matching, augmenting path, and theorems related to maximum matching. Delve into proofs and strategies for constructing maximum matchings in graphs.
Download Presentation

Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSCE-411 Design and Analysis of Algorithms Spring 2025 Instructor: Jianer Chen Office: PETR 428 Phone: 845-4259 Email: chen@cse.tamu.edu Notes 30: Finding an augmenting path
Graph Matching (on undirected graphs) Definition. An edge set M in an undirected graph G is a matching in G if no two edges in M share a common end. The Maximum Matching Problem. Given an undirected graph G, construct a maximum matching in G. Definitions. M: a matching in G. A vertex is matched if it is an end of an edge in M, otherwise, unmatched. Definition. An augmenting path (w.r.t a matching M) starts and ends at unmatched vertices and goes alternatively with edges not in M and in M
Graph Matching (on undirected graphs) The Maximum Matching Problem. Given an undirected graph G, construct a maximum matching in G. Definition. An augmenting path (w.r.t. a matching M) starts and ends at unmatched vertices and goes alternatively with edges not in M and in M
Graph Matching (on undirected graphs) The Maximum Matching Problem. Given an undirected graph G, construct a maximum matching in G. Definition. An augmenting path (w.r.t. a matching M) starts and ends at unmatched vertices and goes alternatively with edges not in M and in M Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Proof. If M is maximum, then there is no augmenting path otherwise, we would be able to construct a larger matching.
Graph Matching (on undirected graphs) The Maximum Matching Problem. Given an undirected graph G, construct a maximum matching in G. Definition. An augmenting path (w.r.t. a matching M) starts and ends at unmatched vertices and goes alternatively with edges not in M and in M Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Proof. If M is maximum, then there is no augmenting path otherwise, we would be able to construct a larger matching. If M is not maximum, let M0 be a maximum matching. Consider the graph M = M M0, i.e., the graph consisting of edges belonging to exactly one of M and M0.
Graph Matching (on undirected graphs) The Maximum Matching Problem. Given an undirected graph G, construct a maximum matching in G. Definition. An augmenting path (w.r.t. a matching M) starts and ends at unmatched vertices and goes alternatively with edges not in M and in M Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Proof. If M is maximum, then there is no augmenting path otherwise, we would be able to construct a larger matching. If M is not maximum, let M0 be a maximum matching. Consider the graph M = M M0, i.e., the graph consisting of edges belonging to exactly one of M and M0. M and M0 have the same number of edges that are in both M and M0. Thus, M0 has more edges in M than M.
Graph Matching (on undirected graphs) The Maximum Matching Problem. Given an undirected graph G, construct a maximum matching in G. Definition. An augmenting path (w.r.t. a matching M) starts and ends at unmatched vertices and goes alternatively with edges not in M and in M Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Proof. If M is maximum, then there is no augmenting path otherwise, we would be able to construct a larger matching. If M is not maximum, let M0 be a maximum matching. Consider the graph M = M M0, i.e., the graph consisting of edges belonging to exactly one of M and M0. M and M0 have the same number of edges that are in both M and M0. Thus, M0 has more edges in M than M. Each component of M looks like:
Graph Matching (on undirected graphs) The Maximum Matching Problem. Given an undirected graph G, construct a maximum matching in G. Definition. An augmenting path (w.r.t. a matching M) starts and ends at unmatched vertices and goes alternatively with edges not in M and in M Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Proof. If M is maximum, then there is no augmenting path otherwise, we would be able to construct a larger matching. If M is not maximum, let M0 be a maximum matching. Consider the graph M = M M0, i.e., the graph consisting of edges belonging to exactly one of M and M0. M and M0 have the same number of edges that are in both M and M0. Thus, M0 has more edges in M than M. Each component of M looks like: An augmenting path w.r.t. M
Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G.
Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. An augmenting path P w.r.t. M will give a matching larger than M
Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. An augmenting path P w.r.t. M will give a matching larger than M G
Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. An augmenting path P w.r.t. M will give a matching larger than M G G
Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. An augmenting path P w.r.t. M will give a matching larger than M G G Graph-Matching(G) 1. M = ; 2. while (there is an aug. path P) use P to make M larger; 3. Return (M)
Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Finding an augmenting path: start from an unmatched vertex, try to find an augmenting path ending at another unmatched vertex. An augmenting path P w.r.t. M will give a matching larger than M G G Graph-Matching(G) 1. M = ; 2. while (there is an aug. path P) use P to make M larger; 3. Return (M)
Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Finding an augmenting path: start from an unmatched vertex, try to find an augmenting path ending at another unmatched vertex. An augmenting path P w.r.t. M will give a matching larger than M G level 0 1 G Graph-Matching(G) 1. M = ; 2. while (there is an aug. path P) use P to make M larger; 3. Return (M) 2 3 4
Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Finding an augmenting path: start from an unmatched vertex, try to find an augmenting path ending at another unmatched vertex. An augmenting path P w.r.t. M will give a matching larger than M Pretty much similar to BFS but: at even levels, expand all possible ways, but at odd levels, expand on a single matching edge. G level 0 1 G Graph-Matching(G) 1. M = ; 2. while (there is an aug. path P) use P to make M larger; 3. Return (M) 2 3 4
Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Finding an augmenting path: start from an unmatched vertex, try to find an augmenting path ending at another unmatched vertex. An augmenting path P w.r.t. M will give a matching larger than M Pretty much similar to BFS but: at even levels, expand all possible ways, but at odd levels, expand on a single matching edge. G level 0 1 G Graph-Matching(G) 1. M = ; 2. while (there is an aug. path P) use P to make M larger; 3. Return (M) 2 3 4
Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Finding an augmenting path: start from an unmatched vertex, try to find an augmenting path ending at another unmatched vertex. An augmenting path P w.r.t. M will give a matching larger than M Pretty much similar to BFS but: at even levels, expand all possible ways, but at odd levels, expand on a single matching edge. G level 0 1 G Graph-Matching(G) 1. M = ; 2. while (there is an aug. path P) use P to make M larger; 3. Return (M) 2 3 4
Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Finding an augmenting path: start from unmatched vertices, try to find an augmenting path that connects two unmatched vertices. level 0 1 An augmenting path P w.r.t. M will give a matching larger than M G 2 3 4 G Pretty much similar to BFS but: at even levels, expand all possible ways, but at odd levels, expand on a single matching edge. Graph-Matching(G) 1. M = ; 2. while (there is an aug. path P) use P to make M larger; 3. Return (M)
Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Finding an augmenting path: start from unmatched vertices, try to find an augmenting path that connects two unmatched vertices. level 0 1 Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) 2 3 4 Pretty much similar to BFS but: at even levels, expand all possible ways, but at odd levels, expand on a single matching edge.
Graph Matching (on undirected graphs) Theorem. A matching M is maximum if and only if there is no augmenting path w.r.t. M in G. Finding an augmenting path: start from unmatched vertices, try to find an augmenting path that connects two unmatched vertices. level 0 1 Augment(G, M) \\ Q is a queue 1. for (each vertex v of G) level[v] = -1; 2. for (each unmatched vertex v) level[v] = 0; dad[v] = -1; Q v; 3. while (Q ) v Q; if (level[v] is even) for (each edge [v, w]) if (level[w] == -1) level[w] = level[v]+1; dad[w] = v; Q w; else if (level[v] == level[w]) return an augmenting path; else \\ level[v] is odd let [v, w] be the edge in M; if (level[v] == level[w]) return an augmenting path; else level[w] = level[v]+1; dad[w] = v; Q w; 4. Return (false) 2 3 4 Pretty much similar to BFS but: at even levels, expand all possible ways, but at odd levels, expand on a single matching edge. The matching M can be given as an array M[1..n] such that M[i] = j (also M[j] = i) means that the edge [i, j] is in M. Time = O(n+m)