# math代写|算法代写|algorithm代写 – CSCB63 Assignment 2

math代写|算法代写|algorithm代写 : 典型的一个算法代写题目
1. [10 marks] This question is about the fact that there can be exponentially many shortest paths in a
graph. But proving that sentence involves annoying technicalities that distract from the core idea. So
here is a more convenient and still without-loss-of-generality version.
Prove that for every natural number n, there is an undirected graph of bn + c vertices such that for
some pair of vertices s and t in the graph, there are 2
n
shortest paths from s to t.
The constants b and c are up to you.
2. [18 marks] Given a directed graph G = (V, E), the strongly connected components graph GSCC of G
is the directed graph defined by V
SCC = {C | C is a SCC of G} and ESCC = {(Ci
, Cj ) | ∃(u, v) ∈
E where u ∈ Ci
, v ∈ Cj}. We can relax the definition of strongly connected by saying that G is
nearly strongly connected if for each pair of vertices s, t ∈ V , either there exists a path from s to t or
a path from t to s.
Answer the following questions to design an algorithm to recognize whether a graph G is nearly
strongly connected.
(a) [3 marks] Prove that GSCC is a directed acyclic graph (known as a DAG).
(b) [4 marks] Given a DAG G = (V, E), prove that G is nearly strongly connected iff there exists