Consider the following directed graph:

The number of different topological orderings of the vertices of the graph is ________________.

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?

Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.

Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing

In a depth-first traversal of a graph G with n vertices,k edges are marked as tree edges. The number of connected components in G is

Consider the following graph among the following sequences
I. a b e g h f
II. a b f e h g
III. a b f h g e
IV. a f g h b e

Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2,…,100. There is an edge between vertices U and V if and only if the label of U can be obtained by swapping two adjacent numbers in the label of V. Let y denote the degree of a vertex in G, and 𝑧 denote the number of connected components in G. Then, 𝑦+10𝑧= _____.

In an adjacency list representation of an undirected simple graph G=(V,E), each edge (u,v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E|=m and |V|=n, and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?

Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x∈V, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u, v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u)−d(v)?

Let G be a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of G is 500. When the weight of each edge of G is increased by five, the weight of a minimum spanning tree becomes ________.

Let G be a weighted graph with edge weights greater than one and G' be the graph constructed by squaring the weights of edges in G. Let T and T' be the minimum spanning trees of G and G' respectively, with total weights t and t'. Which of the following statements is TRUE?

Consider a complete undirected graph with vertex set {0,1,2,3,4}. Entry W_ij in the matrix W below is the weight of the edge {i, j}

What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?

What is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?

What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees?

Consider the depth-first-search of an undirected graph with 3 vertices P, Q, and R. Let discovery time d(u) represent the time instant when the vertex u is first visited, and finish time f(u) represent the time instant when the vertex u is last visited. Given that
d(P) = 5 units      f(P) = 12 units
d(Q) = 6 units      f(Q) = 10 units
d(R) = 14 unit      f(R) = 18 units
Which one of the following statements is TRUE about the graph