Description
Problem 1. Given a directed graph G = (V,E) defined the graph GR = (V,ER) with all edge directions reversed, that is, ER = {(v,u)|(u,v) ∈ E}.
- Suppose G is represented as an adjacency matrix. Give an O(|V |2) algorithm for finding the adjacency matrix representation of GR. (4)
- Suppose G is represented as an adjacency list. Given an O(|V | + |E|) algorithm for finding the adjacency matrix representation of GR. (4)
- A source vertex in G is a vertex s such that there is no vertex v ∈ G such that (v,s) ∈ E. A sink vertex in G is a vertex u such that there is no vertex v ∈ G such that (u,v) ∈ G. Relate the source and sink vertices of G and GR. Relate the strong components of G with the strong components of GR. (2+2)
Problem 2. A connected graph G = (V,E) is said to be bi-partite if V can be partitioned into two non-empty and disjoint partitions V = V1 ∪ V2 such that any edge {u,v} in E has u ∈ V1 and v ∈ V2. That is, there are no edges among vertices in V1 or among vertices in V2. Consider the following test for bi-partition. Run BFS on G starting from vertex s. Let u.d be the shortest distance (as per BFS) from s to u.
- Show that G is bipartite iff for every edge {u,v} ∈ E, |d − v.d| = 1. (12)
1
- Extend the BFS algorithm slightly to give an O(|V |+|E|) algorithm to test if G is bi-partite. (12)
Problem 3. Give an O(|V |+|E|) algorithm that takes a directed graph and a given edge e = (u,v) and tests if there is a cycle involving e in the graph. (20)
Problem 4. Given a graph G = (V,E), consider the following alternative outline for finding a topological order that repeatedly removes source nodes from G.
Repeat until the graph is empty
Find a source, output it and delete it.
Design an O(|V | + |E|) time algorithm to implement this (alternative) outline and prove your complexity. (22)
Problem 5. Given a directed graph G = (V,E), design an algorithm to find a vertex u that has
paths to all vertices in V in G.
