CSCB63 Assignment 2
Due: 11.59pm, Monday Feb 28, 2022
0. (not for marks) Make sure you are capable of applying BFS, DFS, Prim’s algorithm, Kruskal’s algo-
rithm and Dijkstra’s algorithm to an appropriate type of graph (directed, not directed or weighted).
1. A unicyclic graph is a connected graph with exactly one simple cycle. Give an efficient algorithm
that, given a connected undirected graph G = (V,E) (represented by its adjacency lists) and a weight
function w : E → R, finds a unicyclic subgraph of G of minimum weight spanning G. Prove that
your algorithm is correct and analyze its worst case time complexity as a function of n = |V | and
m = |E|. Note: the cycle itself need not include all vertices in V .
HINT: You may find it easier to first prove a claim about unicyclic subgraphs ofG of minimum weight
spanning G and then use that claim to design your algorithm.
2. In class we saw Dijkstra’s algorithm to solve the single source shortest paths problem. Now consider
the scenario where each edge’s weight is a bandwidth. We wish to find the single source fastest path
to each node. Notice that a path is only as fast as its slowest edge.
Explain how to modify Dijkstra’s algorithm to solve this new problem. Notice that the operator you
use to compare paths must be a total order and your path measure operator an associative operator.
If you don’t know these terms you may look them up. Prove that your algorithm is correct.
3. Your friend claims that the algorithm for strongly connected components would be simpler if it used
the original (instead of the transpose) graph in the second depth-first search and scanned the vertices
in order of increasing finishing times. Does this simpler algorithm always produce correct results?
Give a proof for your answer.
4. Recognizing bipartite graphs.
A graph is bipartite if and only if it is possible to partition its vertices into two sets so that all edges
have one endpoint in each set. There are many fast graph algorithms for bipartite graphs, so it is
important to be able to recognize whether a given graph is bipartite.
(a) Prove that a graph is bipartite if and only if it contains no odd cycle.
(b) Describe a O(|E|)-time algorithm BFS BIPARTITE(G) that, given a connected graph G in
terms of its adjacency-list, uses a BFS as part of the algorithm and returns TRUE if G is bi-
partite and FALSE otherwise. Prove that your algorithm works and has the required running
time.
(c) Describe a different algorithm DFS BIPARTITE(G) that, given a connected graph G in terms of
its adjacency-list, uses a DFS to create a partition of the vertices by assigning to each node a 0
or a 1 when the graph is bipartite, and outputs “not bipartite” when the graph is not bipartite.
5. Recall Kruskal’s algorithm that builds an MST by repeatedly adding a least weight edge to the tree as
long as it doesn’t create a cycle. Consider another greedy algorithm that works as follows. Repeatedly
remove the largest weight edge from G as long as it doesn’t disconnect the graph until only a tree
remains. Either prove that this algorithm constructs a MST or provide an example that makes it fail.
1