Kosaraju's distinct orders of SCC discovery

When performing Kosaraju’s algorithm on the directed graph shown below, in how many distinct orders can the strongly connected components be found?

    A. 5

    B. 12

    C. 72

    D. 720

    E. None of the above

Original idea by: Pedro Ferreira

How many back edges?

When performing a depth-first search (DFS) on the following undirected graph with \(14\) vertices and \(32\) edges, how many back edges are obtained?

    A. \(17\)

    B. \(18\)

    C. \(19\)

    D. \(20\)

    E. None of the above

Original idea by: Pedro Ferreira 

Number of connected triplets

Let \(A\) be the \(N \times N\) adjacency matrix of an undirected unweighted network, without self-loops. Let \(\mathbf{1}\) be a column vector of \(N\) elements, all equal to \(1\), i.e., 
\(\mathbf{1} = (1,1,\dots,1)^T\). Let \(Tr(A)\) denote the trace of matrix \(A\), 
i.e., the sum of the elements on its main diagonal.

Which of the following expressions gives the number of connected triplets 
in the network?

A. \(\frac{1}{2} (\textbf{1}^T A^2 \textbf{1})\)

B. \(\frac{1}{2} [\textbf{1}^T A^2 \textbf{1} - Tr(A^2)]\)

C. \(\frac{1}{2} [\textbf{1}^T A^2 \textbf{1} - Tr(A^2) - Tr(A^3)]\)

D. \(\frac{1}{2} [\textbf{1}^T A^2 \textbf{1} - Tr(A^2)] - \frac{1}{6} Tr(A^3)\) 

E. None of the above

 Original idea by: Pedro Ferreira