Algorithms problem set 8

1. (10 pts) Hermione needs your help with her wizardly homework. She’s trying to come
up with an example of a directed graph G = (V; E), a source vertex s 2 V and a set
of tree edges Eπ ⊆ E such that for each vertex v 2 V , the unique path in the graph
(V; Eπ) from s to v is a shortest path in G, yet the set of edges Eπ cannot be produced
by running a breadth-first search on G, no matter how the vertices are ordered in each
adjacency list. Include an explanation of why your example satisfies the requirements.
2. (15 pts) Prof. Dumbledore needs your help to compute the in- and out-degrees of all
vertices in a directed multigraph G. However, he is not sure how to represent the
graph so that the calculation is most efficient. For each of the three possible representations, express your answers in asymptotic notation (the only notation Dumbledore
understands), in terms of V and E, and justify your claim.
(a) An edge list representation. Assume vertices have arbitrary labels.
(b) An adjacency list representation. Assume the vector’s length is known.
(c) An adjacency matrix representation. Assume the size of the matrix is known.
3. (25 pts) Professor Snape gives you the following unweighted graph and asks you to
construct a weight function w on the edges, using positive integer weights only, such
that the following conditions are true regarding minimum spanning trees and singlesource shortest path trees:
• The MST is distinct from any of the seven SSSP trees.
• The order in which Jarn´ık/Prim’s algorithm adds the safe edges is different from
the order in which Kruskal’s algorithm adds them.
Justify your solution by (i) giving the edges weights, (ii) showing the corresponding
MST and all the SSSP trees, and (iii) giving the order in which edges are added by
each of the three algorithms. (For Bor _uvka’s algorithm, be sure to denote which edges
are added simultaneously in a single round.)
4. (25 pts extra credit) Deep in the heart of the Hogwarts School of Witchcraft and
Wizardry, there lies a magical Sphinx that demands that any challenger efficiently
convert directed multigraphs into undirected simple graphs. If the wizard can correctly
solve a series of arbitrary instances of this problem, the Sphinx will unlock a secret
passageway.
a
b c
e
d
a b e d
c b
d
b a a
d a d
a
b c
e
d
a b e d
c b
d
b c a
d a c
d e
a
e
c e d e c a d e
An example of transforming G ! G0
Let G = (E; V ) denote a directed multigraph. An undirected simple graph is a
G0 = (V; E0), such that E0 is derived from the edges in E so that (i) every directed
multi-edge, e.g., f(u; v); (u; v)g or even simply f(u; v)g, has been replaced by a single
pair of directed edges f(u; v); (v; u)g and (ii) all self-loops (u; u) have been removed.
Describe and analyze an algorithm (explain how it works, give pseudocode if necessary, derive its running time and space usage, and prove its correctness) that takes
O(V + E) time and space to convert G into G0, and thereby will solve any of the
Sphinx’s questions. Assume both G and G0 are stored as adjacency lists.
Hermione’s hints: Don’t assume adjacencies Adj[u] are ordered in any particular way,
and remember that you can add edges to the list and then remove ones you don’t need.