Quiz - MO412 - Julia Pietro

How does the Kosaraju–Sharir algorithm identify Strongly Connected Components (SCC)? a.) Performs a DFS on a graph G . Then, it orders the nodes by decreasing finishing times. The branches found by the DFS are considered strongly connected components. b.) Applies only to cyclic graphs. If a cycle has more than three nodes, then it is considered a strongly connected component. c.) Performs a DFS on a graph G . Then, it orders the nodes by decreasing finishing times. This order is used to perform a second DFS on the transposed graph G′ (where all edges are reversed). The trees formed during this DFS are considered strongly connected components. d.) Identifies cycles in a graph G , where for any pair of nodes u and v , there is a path from u to v and from v to u . e.) None of the above Original idea by: Julia de Pietro Bigi

What do BFS and DFS have in common? What about their differences?  a.) Common: They both use an adjacency list as input. Both of them can be used to calculate distances and classify edges. Differences: BFS doesn't restart the search when it reaches a target node or when a tree is finished like DFS does. BFS visits all nodes reachable from a given node, so not necessarily the entire tree will be visited. b.) Common: they both use an adjancency list and starting + ending times of node's visits as input.  Differences: BFS can be used to calculate distances and finding connected components. While DFS can be used to detect cycles and classify edges.  c.) Common: they both use an adjancency list as input.  Differences: BFS doesn't restart the search when it reaches a target node or when a tree is finished like DFS does. BFS visits all nodes reachable from a giving node, so not necessarily the entire tree will be visited.  d.) Common: they both need an adjancency list ...

Consider the following network: Which statements are TRUE or FALSE? 1. The degree distribution of this network would generate a graph with equal values of pk for k values.  2. If link (4-5) were to be removed, then the network would have 2 components. This makes the connection between nodes 4 and 5 to be called a bridge. 3. Considering node 4 as the zero node, the diameter of this network is dmax = 4. 4. The degrees of the two mostl connected nodes are equivalent to 2/3 and 1.  a.) T F F T b.) F F T T c.) T T F T  d.) F T T F  e) None of the above Original idea by: Julia de Pietro Bigi