(30 pts) Deep in the heart of the Hogwarts School of Witchcraft and Wizardry, th

Question

(30 pts) Deep in the heart of the Hogwarts School of Witchcraft and Wizardry, there lies a magical grey parrot that demands that any challenger efficiently convert directed multigraphs into directed simple graphs. If the wizard can correctly solve a series of arbitrary instances of this problem, the parrot will unlock a secret passageway.

Let G = (E,V) denote a directed multigraph. A directed simple graph is a G = (V,E), such that E is derived from the edges in E so that (i) every directed multi- edge, e.g., {(u, v), (u, v)} or even simply {(u, v)}, has been replaced by a single directed

edge {(u, v)} and (ii) all self-loops (u, u) have been removed.

Describe and analyze an algorithm (explain how it works, give pseudocode if neces- sary, derive its running time and space usage, and prove its correctness) that takes O(V + E) time and space to convert G into G, and thereby will solve any of the Sphinx’s questions. Assume both G and G are stored as adjacency lists.

Explanation / Answer

The problem is called element distinctness problem in adjancency list.

This problem can be solved by sorting in O(nlogn)

Sort the adjacency list - remove the similar elements

or

, or by using O(n) extra space in O(n).

create a new adjacency matrix and put into it only distinct elements

You can use set() to only keep distinct elements.

proof -

Given a directed graph G = (V, E), we come up with an adjacency list representation, then we build a new adjacency list of an undirected graph as specified in the problem, where for every vertex vi if there exists an adjacent vertex vj that is greater, we’ll add it to the new adjacency list. We can call this adList. The second part would be to do the same thing for the new undirected graph where the only difference would be to check every vjfor a vi and if vi is greater then add vi to the list (rather than vj). Hence, since the process is pretty much the same, the overall time would remain O ( V + E ).

pseudocode in python -

Using networkX library for graphs

This will create an undirected graph of your multigraph where multiple edges are merged into single edges. However, if you have different attributes for the edges that get merged, I don't know if there's any way of determining which attribute is kept.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.