ALGORITHMS(CONCEPTUAL)

Convert directed muligraphs into undirected simple graphs. Let G = (E, V) denote a directed multigraph. An undirected 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 pair of directed edges {(u,v), (v,u)} and (ii) all self-loops (u,u) have been removed. Describe and analyze an algorithm (explain how it works, give pseudocode if necessary, derives its running time and space usage and prove its correctness that takes O(V + E) time and space to convert G and G', and thereby will solve any of the Sphinx's questions. Assume both G and G' are stories as adjacency lists. DONT assume adjacencies Adj[u] are ordered in any particular way. You can add edges to the list and then remove ones you don't need.

BIG THANKS.

'

a c b d e d b a a c e d e d b c a e c a d e An example of transforming G G