Graph Algorithms and Proofs: Exercises and Problems
Explore graph algorithms, proofs, and problem-solving strategies related to bipartite graphs, spanning trees, MSTs, and Dijkstra's algorithm. Discover how to test for bipartiteness, find odd cycles, characterize spanning trees, ensure MSTs include specific edges, and determine shortest paths using Dijkstra's algorithm.
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
Algorithms on Graphs Umang Bhaskar & Juhi Chaudhary Day 1, session 2: Proofs on graphs STCS Vigyan Vidushi 2024
Exercises: Day 1 Exercises: Day 1 Problem 1: Give a polynomial time algorithm to test if a graph is bipartite.
Exercises: Day 1 Exercises: Day 1 Problem 1: Give a polynomial time algorithm to test if a graph is bipartite. show that ? is bipartite iff ? has no odd cycles
Exercises: Day 1 Exercises: Day 1 Problem 1: Give a polynomial time algorithm to test if a graph is bipartite. show that ? is bipartite iff ? has no odd cycles use bfs to find odd cycles
Exercises: Day 1 Exercises: Day 1 Problem 2: Show that every MST must include both edges with weight 1. 3 b a 7 10 1 4 c f 8 1 2 6 e d
Exercises: Day 1 Exercises: Day 1 Problem 2: Show that every MST must include both edges with weight 1. how do you characterize a spanning tree? 3 b a 7 10 1 4 c f 8 1 2 6 e d
Exercises: Day 1 Exercises: Day 1 Problem 2: Show that every MST must include both edges with weight 1. how do you characterize a spanning tree? assume ? is an MST that doesn t contain both edges. What happens when you add the missing weight 1 edge? 3 b a 7 10 1 4 c f 8 1 2 6 e d
Exercises: Day 1 Exercises: Day 1 Problem 3: Find all shortest-paths from vtx a 4 Dijkstra ( ? = (?,?) , a) a b dist(a) = 0, dist(v) = for all others S = {a} \\ set of shortest-distance vertices update distance for vtxs adjacent to a 3 1 8 c 4 6 d h while S V add vtx v with smallest dist to S 3 3 2 3 e update distance for vtxs w adjacent to v add directed edge (v,w) (and remove other edges into w) 6 3 2 i g f
Exercises: Day 1 Exercises: Day 1 Problem 4: Prove that Dijkstra s algorithm terminates correctly.
Exercises: Day 1 Exercises: Day 1 Problem 4: Prove that Dijkstra s algorithm terminates correctly. prove that it terminates.
Exercises: Day 1 Exercises: Day 1 Problem 4: Prove that Dijkstra s algorithm terminates correctly. prove that it terminates. prove that when a vertex is added to S, it s distance is shortest-path distance.
