Graphs

Let $G(V,E)$ be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the number of edges in that path.

Let $s\in V$ be a vertex in $G$. For every $u\in V$ and for every $k\ge 0$, let $d_k(u)$ denote the weight of a shortest path (in terms of weight) from $s$ to $u$ of length at most $k$. If there is no path from $s$ to $u$ of length at most $k$, then $d_k(u)=\infty$.

Consider the statements:

S1: For every $k\ge 0$ and $u\in V$, $d_{k+1}(u)\le d_k(u)$.

S2: For every $(u,v)\in E$, if $(u,v)$ is part of a shortest path (in terms of weight) from $s$ to $v$, then for every $k\ge 0$, $d_k(u)\le d_k(v)$.

Which one of the following options is correct?

Let $G(V,E)$ be a simple, undirected, edge-weighted graph with unique edge weights.

Which of the following statements about the minimum spanning trees (MST) of $G$ is/are true?

Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph $G(V,E)$ as input, where $d[v]$ and $f[v]$ are the discovery time and finishing time, respectively, of the vertex $v\in V$.

DFS(G):
  unmark all v ∈ V
  t ← 0
  for each v ∈ V
    if v is unmarked
      t ← Explore(G, v, t)
    end if
  end for

Explore(G, v, t):
  mark v
  t ← t + 1
  d[v] ← t
  for each (v, w) ∈ E
    if w is unmarked
      t ← Explore(G, w, t)
    end if
  end for
  t ← t + 1
  f[v] ← t
  return t

Suppose that the input directed graph $G(V,E)$ is a directed acyclic graph (DAG).

For an edge $(u,v)\in E$, which of the following options will NEVER be correct?

An undirected, unweighted, simple graph $G(V,E)$ is said to be 2-colorable if there exists a function $c:V\to \{0,1\}$ such that for every $(u,v)\in E$, $c(u)\ne c(v)$.

Which of the following statements about 2-colorable graphs is/are true?

Consider a complete graph $K_n$ with $n$ vertices ($n>4$). Note that multiple spanning trees can be constructed over $K_n$. Each of these spanning trees is represented as a set of edges. The Jaccard coefficient between any two sets is defined as the ratio of the size of the intersection of the two sets to the size of the union of the two sets.

Which one of the following options gives the lowest possible value for the Jaccard coefficient between any two spanning trees of $K_n$ ?

Let $G$ be a weighted directed acyclic graph with $m$ edges and $n$ vertices. Given $G$ and a source vertex $s$ in $G$, which one of the following options gives the worst case time complexity of the fastest algorithm to find the lengths of shortest paths from $s$ to all vertices that are reachable from $s$ in $G$?

Consider a directed graph $G=(V,E)$, where $V$ is the finite set of vertices and $E$ is the set of directed edges between the vertices. $G$ may contain cycles but there is no self-loop. Further, $G$ may not be strongly connected.

Let $G^R$ be the graph obtained by reversing the directions of all the edges in $G$ without changing the set of vertices.

Assume that Breadth First Search (BFS) or Depth First Search (DFS) from any given vertex $v$ of a graph visits only the reachable vertices from $v$ in that graph.

Which of the following statements must always be true, regardless of the structure of $G$?

Let $G$ be any undirected graph with positive edge weights, and $T$ be a minimum spanning tree of $G$. For any two vertices, $u$ and $v$, let $d_1(u,v)$ and $d_2(u,v)$ be the shortest distances between $u$ and $v$ in $G$ and $T$, respectively. Which ONE of the options is CORRECT for all possible $G$, $T$, $u$ and $v$?

Let $G(V,E)$ be an undirected and unweighted graph with 100 vertices. Let $d(u,v)$ denote the number of edges in a shortest path between vertices $u$ and $v$ in $V$. Let the maximum value of $d(u,v)$, $u,v\in V$ such that $u\ne v$, be 30. Let $T$ be any breadth-first-search tree of $G$. Which ONE of the given options is CORRECT for every such graph $G$?

The maximum value of $x$ such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is ________ . (answer in integer)

Graph (4 vertices A, B, C, D arranged as a square with both diagonals drawn, i.e. $K_4$):
- A connects to B with weight 7 (top edge)
- A connects to D with weight 6 (left edge)
- D connects to C with weight 8 (bottom edge)
- B connects to C with weight $x$ (right edge, unknown)
- B connects to D with weight 1 (one diagonal)
- A connects to C with weight 3 (other diagonal)

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph $G$ is/are TRUE?

Let $G$ be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant $\alpha$ is added to the weight of every edge.

Which ONE of the following statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in $G$ before and after the edge weight update?

Consider the following algorithm someAlgo that takes an undirected graph G as input.

someAlgo(G)
  1. Let v be any vertex in G. Run BFS on G starting at v. Let u be a vertex in G at maximum distance from v as given by the BFS.
  2. Run BFS on G again with u as the starting vertex. Let z be the vertex at maximum distance from u as given by the BFS.
  3. Output the distance between u and z in G.

The output of someAlgo($T$) for the tree shown in the given figure is ___________. (Answer in integer)

Let $G$ be a simple, unweighted, and undirected graph. A subset of the vertices and edges of $G$ are shown below.

It is given that $a-b-c-d$ is a shortest path between $a$ and $d$; $e-f-g-h$ is a shortest path between $e$ and $h$; $a-f-c-h$ is a shortest path between $a$ and $h$. Which of the following is/are NOT the edges of $G$?

Consider a directed graph $G=(V,E)$, where $V=\{0,1,2,\dots ,100\}$ and $E=\{(i,j):0<j-i\le 2,\text{ for all }i,j\in V\}$. Suppose the adjacency list of each vertex is in decreasing order of vertex number, and depth-first search (DFS) is performed at vertex 0. The number of vertices that will be discovered after vertex 50 is ______ (Answer in integer)

Let $G$ be a directed graph and $T$ a depth first search (DFS) spanning tree in $G$ that is rooted at a vertex $v$. Suppose $T$ is also a breadth first search (BFS) tree in $G$, rooted at $v$. Which of the following statements is/are TRUE for every such graph $G$ and tree $T$ ?

The number of edges present in the forest generated by the DFS traversal of an undirected graph $G$ with 100 vertices is 40. The number of connected components in $G$ is _____ (answer in integer)

Let $G$ be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in $G$ has even weight. Which of the following statements is/are TRUE for every such graph $G$?

The number of distinct minimum-weight spanning trees of the following graph is ____.

Graph description: Vertices a, b, c, d, e, f, g. Edges and weights:
- a-b: 1
- a-f: 1
- a-g: 2
- b-c: 3
- b-g: 2
- c-g: 2
- c-d: 1
- g-f: 2
- g-e: 2
- g-d: 2
- f-e: 3
- e-d: 1

Consider performing depth-first search (DFS) on an undirected and unweighted graph $G$ starting at vertex $s$. For any vertex $u$ in $G$, $d[u]$ is the length of the shortest path from $s$ to $u$. Let $(u,v)$ be an edge in $G$ such that $d[u]<d[v]$. If the edge $(u,v)$ is explored first in the direction from $u$ to $v$ during the above DFS, then $(u,v)$ becomes a ______ edge.

Consider the directed acyclic graph (DAG) below. Which of the following is/are valid vertex orderings that can be obtained from a topological sort of the DAG?

Let $U=\{1,2,3\}$. Let $2^U$ denote the powerset of $U$. Consider an undirected graph $G$ whose vertex set is $2^U$. For any $A,B\in 2^U$, $(A,B)$ is an edge in $G$ if and only if (i) $A\ne B$, and (ii) either $A⊊B$ or $B⊊A$. For any vertex $A$ in $G$, the set of all possible orderings in which the vertices of $G$ can be visited in a Breadth First Search (BFS) starting from $A$ is denoted by $\mathcal{B}(A)$.

If $\varnothing$ denotes the empty set, then the cardinality of $\mathcal{B}(\varnothing )$ is ______.

Consider a simple undirected weighted graph $G$, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of $G$ is/are TRUE?

Let $G=(V,E)$ be a weighted undirected graph and let $T$ be a Minimum Spanning Tree (MST) of $G$ maintained using adjacency lists. Suppose a new weighted edge $(u,v)\in V\times V$ is added to $G$. The worst case time complexity of determining if $T$ is still an MST of the resultant graph is

Let $G=(V,E)$ be a directed, weighted graph with weight function $w:E\to \mathbb{R}$.

For some function $f:V\to \mathbb{R}$, for each edge $(u,v)\in E$, define $w^{\prime }(u,v)$ as

Which one of the options completes the following sentence so that it is TRUE?

"The shortest paths in $G$ under $w$ are shortest paths under $w^{\prime }$ too, ___."

Consider a graph $G=(V,E)$, where $V=\{v_1,v_2,\dots ,v_{100}\}$, $E=\{(v_i,v_j)\mid 1\le i<j\le 100\}$, and weight of the edge $(v_i,v_j)$ is $|i-j|$. The weight of minimum spanning tree of $G$ is ____________.

Let $G$ be a simple undirected graph. Let $T_D$ be a depth first search tree of $G$. Let $T_B$ be a breadth first search tree of $G$. Consider the following statements.

(I) No edge of $G$ is a cross edge with respect to $T_D$. (A cross edge in $G$ is between two nodes neither of which is an ancestor of the other in $T_D$.)

(II) For every edge $(u,v)$ of $G$, if $u$ is at depth $i$ and $v$ is at depth $j$ in $T_B$, then $|i-j|=1$.

Which of the statements above must necessarily be true?

Consider the following undirected graph G. Choose a value for x that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of x is ______.