Edit the RMarkdown source file for this assignment in RStudio. When you finish, Knit the file to HTML and upload the .html output to Canvas.

Reversal of a graph

Consider the following graph \(G\).

library(igraph) #load the igraph library
digraph_list <- list(c(2,3), 
                    c(3,6), 
                    c(4,5,6), 
                    c(1,5,6), 
                    c(2), 
                    c(1))
M <- graph_from_adj_list(digraph_list, mode="out")

  1. Create an adjacency list for the reversal \(\mbox{rev}(G)\) of the above graph \(G\), and use the igraph package to check your answer by plotting the reversal.

  2. Let A[1..V] be an adjacency list for a directed graph \(G\), where A[i] is a linked list of out-neighbors of vertex i. Describe an algorithm for computing the adjacency list B[1..V] for \(\mbox{rev}(G)\) in \(O(V+E)\) time.

Semiconnected graphs

A directed graph \(G\) is called semi-connected if, for any pair of vertices \(u,v\), there is a directed path from \(u\) to \(v\), or there is a directed path from \(v\) to \(u\). The following algorithm returns True iff the the graph G is semi-connected.

IsSemiConnected(G):
   compute scc(G)
   let v_1..v_n be a topological sort of scc(G)
   for i in 1..n
      if v_i v_[i+1] is not an edge of scc(G)
         return False
   return True
  1. Explain why this algorithm is correct. In particular,
    1. Why is it correct to return False if there is no edge from v_i to v_[i+1]?
    2. Why is it correct to return True at the end?
  2. Give the running time of the IsSemiConnected function as an asymptotic estimate in terms of the number of vertices \(V\) and the number of edges \(E\) in the graph \(G\). Explain your reasoning.