Graph Matching and Analysis of Algorithms in Spring 2025
Explore the world of graph matching and algorithm analysis with Professor Jianer Chen in CSCE 411. Dive into topics such as constructing arrays for graphs, testing for negative cycles, and more. Get insights from Midterm II reports and learn about key concepts in algorithm design.
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 29: Graph matching
Max: 95, Min: 63, Averge: 78.7, median 79 100-90: 3, 89-80: 10, 79-70: 10, <70: 5 Midterm II Report
Max: 95, Min: 63, Averge: 78.7, median 79 100-90: 3, 89-80: 10, 79-70: 10, <70: 5 Midterm II Report Question 1. Construct the arrays T[1..10] and SCC[1..10] for a given graph G
Max: 95, Min: 63, Averge: 78.7, median 79 100-90: 3, 89-80: 10, 79-70: 10, <70: 5 Midterm II Report Question 1. Construct the arrays T[1..10] and SCC[1..10] for a given graph G Answer: Array T[1..10]: 1 2 3 4 5 6 7 8 9 10 1 7 9 10 5 8 2 3 4 6 Array SCC[1..10]: 1 1 1 2 3 2 1 1 3 3 1 2 3 4 5 6 7 8 9 10
Max: 95, Min: 63, Averge: 78.7, median 79 100-90: 3, 89-80: 10, 79-70: 10, <70: 5 Midterm II Report Question 1. Construct the arrays T[1..10] and SCC[1..10] for a given graph G Answer: Array T[1..10]: 1 2 3 4 5 6 7 8 9 10 1 7 9 10 5 8 2 3 4 6 Array SCC[1..10]: 1 1 1 2 3 2 1 1 3 3 1 2 3 4 5 6 7 8 9 10 Question 2. Test if there is a negative cycle in a directed and weighted graph that has only one negative edge.
Max: 95, Min: 63, Averge: 78.7, median 79 100-90: 3, 89-80: 10, 79-70: 10, <70: 5 Midterm II Report Question 1. Construct the arrays T[1..10] and SCC[1..10] for a given graph G Answer: Array T[1..10]: 1 2 3 4 5 6 7 8 9 10 1 7 9 10 5 8 2 3 4 6 Array SCC[1..10]: 1 1 1 2 3 2 1 1 3 3 1 2 3 4 5 6 7 8 9 10 Question 2. Test if there is a negative cycle in a directed and weighted graph that has only one negative edge. Answer: A negative cycle must contain the negative edge [u,w]. If G has a negative cycle, then the shortest path from w to u without using [u,w] must be a negative cycle.
Max: 95, Min: 63, Averge: 78.7, median 79 100-90: 3, 89-80: 10, 79-70: 10, <70: 5 Midterm II Report Question 1. Construct the arrays T[1..10] and SCC[1..10] for a given graph G Answer: Array T[1..10]: 1 2 3 4 5 6 7 8 9 10 1 7 9 10 5 8 2 3 4 6 Array SCC[1..10]: 1 1 1 2 3 2 1 1 3 3 1 2 3 4 5 6 7 8 9 10 Question 2. Test if there is a negative cycle in a directed and weighted graph that has only one negative edge. Answer: A negative cycle must contain the negative edge [u,w]. If G has a negative cycle, then the shortest path from w to u without using [u,w] must be a negative cycle. NegCycle(G) 1. find the negative edge [u,w]; 2. G = G - [u,w]; 3. call Dijkstra(G , w) to find a shortest path P from w to u; 4. If (wt(P) + wt(u, w) < 0) return( yes ) else return( no ). time O(m log n)
Max: 95, Min: 63, Averge: 78.7, median 79 100-90: 3, 89-80: 10, 79-70: 10, <70: 5 Midterm II Report Question 1. Construct the arrays T[1..10] and SCC[1..10] for a given graph G Answer: Array T[1..10]: 1 2 3 4 5 6 7 8 9 10 1 7 9 10 5 8 2 3 4 6 Array SCC[1..10]: 1 1 1 2 3 2 1 1 3 3 1 2 3 4 5 6 7 8 9 10 Question 2. Test if there is a negative cycle in a directed and weighted graph that has only one negative edge. Answer: A negative cycle must contain the negative edge [u,w]. If G has a Question 3. Find the center of a tree T negative cycle, then the shortest path from w to u without using [u,w] must be a negative cycle. NegCycle(G) 1. find the negative edge [u,w]; 2. G = G - [u,w]; 3. call Dijkstra(G , w) to find a shortest path P from w to u; 4. If (wt(P) + wt(u, w) < 0) return( yes ) else return( no ). time O(m log n)
Max: 95, Min: 63, Averge: 78.7, median 79 100-90: 3, 89-80: 10, 79-70: 10, <70: 5 Midterm II Report Question 1. Construct the arrays T[1..10] and SCC[1..10] for a given graph G Answer: Array T[1..10]: 1 2 3 4 5 6 7 8 9 10 1 7 9 10 5 8 2 3 4 6 Array SCC[1..10]: 1 1 1 2 3 2 1 1 3 3 1 2 3 4 5 6 7 8 9 10 Question 2. Test if there is a negative cycle in a directed and weighted graph that has only one negative edge. Answer: A negative cycle must contain the negative edge [u,w]. If G has a Question 3. Find the center of a tree T Answer: First get the solution M[1..n, 1..n] to the All-Pairs-Shortest-Path problem for T. For each vertex u, max1 j n{M[u, j]} is the value D[u], and the vertex v that has the smallest D[v] is the center. negative cycle, then the shortest path from w to u without using [u,w] must be a negative cycle. NegCycle(G) 1. find the negative edge [u,w]; 2. G = G - [u,w]; 3. call Dijkstra(G , w) to find a shortest path P from w to u; 4. If (wt(P) + wt(u, w) < 0) return( yes ) else return( no ). time O(m log n)
Max: 95, Min: 63, Averge: 78.7, median 79 100-90: 3, 89-80: 10, 79-70: 10, <70: 5 Midterm II Report Question 1. Construct the arrays T[1..10] and SCC[1..10] for a given graph G Answer: Array T[1..10]: 1 2 3 4 5 6 7 8 9 10 1 7 9 10 5 8 2 3 4 6 Array SCC[1..10]: 1 1 1 2 3 2 1 1 3 3 1 2 3 4 5 6 7 8 9 10 Question 2. Test if there is a negative cycle in a directed and weighted graph that has only one negative edge. Answer: A negative cycle must contain the negative edge [u,w]. If G has a Question 3. Find the center of a tree T Answer: First get the solution M[1..n, 1..n] to the All-Pairs-Shortest-Path problem for T. For each vertex u, max1 j n{M[u, j]} is the value D[u], and the vertex v that has the smallest D[v] is the center. D[u] = dist[j]; 2. v = 1; 3. for (j=2; j n; j++) if (D[v] > D[j]) v = j; 4. output(v). Center(T) 1. for (each vertex u) call Dijkstra(T, u); D[u] = dist[1]; for (j=2; j n; j++) if (D[u] < dist[j]) negative cycle, then the shortest path from w to u without using [u,w] must be a negative cycle. NegCycle(G) 1. find the negative edge [u,w]; 2. G = G - [u,w]; 3. call Dijkstra(G , w) to find a shortest path P from w to u; 4. If (wt(P) + wt(u, w) < 0) return( yes ) else return( no ). time O(m log n)
Max: 95, Min: 63, Averge: 78.7, median 79 100-90: 3, 89-80: 10, 79-70: 10, <70: 5 Midterm II Report Question 1. Construct the arrays T[1..10] and SCC[1..10] for a given graph G Answer: Array T[1..10]: 1 2 3 4 5 6 7 8 9 10 1 7 9 10 5 8 2 3 4 6 Array SCC[1..10]: 1 1 1 2 3 2 1 1 3 3 1 2 3 4 5 6 7 8 9 10 Question 2. Test if there is a negative cycle in a directed and weighted graph that has only one negative edge. Answer: A negative cycle must contain the negative edge [u,w]. If G has a Question 3. Find the center of a tree T Answer: First get the solution M[1..n, 1..n] to the All-Pairs-Shortest-Path problem for T. For each vertex u, max1 j n{M[u, j]} is the value D[u], and the vertex v that has the smallest D[v] is the center. D[u] = dist[j]; 2. v = 1; 3. for (j=2; j n; j++) if (D[v] > D[j]) v = j; 4. output(v). is O(n2log n) Center(T) 1. for (each vertex u) call Dijkstra(T, u); D[u] = dist[1]; for (j=2; j n; j++) if (D[u] < dist[j]) negative cycle, then the shortest path from w to u without using [u,w] must be a negative cycle. NegCycle(G) 1. find the negative edge [u,w]; 2. G = G - [u,w]; 3. call Dijkstra(G , w) to find a shortest path P from w to u; 4. If (wt(P) + wt(u, w) < 0) return( yes ) else return( no ). Complexity: n Dijkstra s: O(n m log n), but m = n-1, so the time time O(m log n)
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.
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.
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.
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. Applications. Job assignments, course scheduling,
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.
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.
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) 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.
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.
