Question 1 |

Let G(V, E) be a directed graph, where V = \{1, 2, 3, 4, 5 \} is the set of vertices and
E is the set of directed edges, as defined by the following adjacency matrix A.

A[i][j]= \left \{ \begin{matrix} 1 &1 \leq j \leq i \leq 5 \\ 0& otherwise \end{matrix} \right.

A[i][j]=1 indicates a directed edge from node i to node j . A directed spanning tree of G , rooted at r \in V , is defined as a subgraph T of G such that the undirected version of T is a tree, and T contains a directed path from r to every other vertex in V . The number of such directed spanning trees rooted at vertex 5 is ____

A[i][j]= \left \{ \begin{matrix} 1 &1 \leq j \leq i \leq 5 \\ 0& otherwise \end{matrix} \right.

A[i][j]=1 indicates a directed edge from node i to node j . A directed spanning tree of G , rooted at r \in V , is defined as a subgraph T of G such that the undirected version of T is a tree, and T contains a directed path from r to every other vertex in V . The number of such directed spanning trees rooted at vertex 5 is ____

24 | |

36 | |

12 | |

6 |

Question 1 Explanation:

Question 2 |

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?

**MSQ**The edge with the second smallest weight is always part of any minimum spanning tree of G . | |

One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G . | |

Suppose S\subseteq V be such that S\neq \phi and S\neq V . Consider the edge with the minimum weight such that one of its vertices is in S and the other in V \ S . Such an edge will always be part of any minimum spanning tree of G . | |

G can have multiple minimum spanning trees. |

Question 2 Explanation:

Question 3 |

Let G be a connected undirected weighted graph. Consider the following two statements.

S1: There exists a minimum weight edge in G which is present in every minimum spanning tree of G.

S2: If every edge in G has distinct weight, then G has a unique minimum spanning tree.

Which one of the following options is correct?

S1: There exists a minimum weight edge in G which is present in every minimum spanning tree of G.

S2: If every edge in G has distinct weight, then G has a unique minimum spanning tree.

Which one of the following options is correct?

Both S1 and S2 are true | |

S1 is true and S2 is false | |

S1 is false and S2 is true | |

Both S1 and S2 are false |

Question 3 Explanation:

Question 4 |

Consider the following undirected graph with edge weights as shown:

The number of minimum-weight spanning trees of the graph is __________

The number of minimum-weight spanning trees of the graph is __________

4 | |

6 | |

5 | |

3 |

Question 4 Explanation:

Question 5 |

Consider a graph G=(V,E), where V=\{v_1,v_2,...,v_{100}\}, E=\{(v_i,v_j)|1\leq i \lt j\leq 100\}, and weight of the edge (v_i,v_j)\; is \; |i-j|. The weight of minimum spanning tree of G is _________

100 | |

99 | |

199 | |

90 |

Question 5 Explanation:

There are 5 questions to complete.

in ques 24 plz update option B (b-c) –> (d-c)

Thank You Amar,

We have updated the option.

Q 32 it should have been Emax with maximum weight instead of Emin.

Thank You Kushagra Dasila,

We have updated it.

In Question 26, please update option C to (d-f),(a-b),(d-c),(b-f),(d-e)

Option updated for GATE CSE

Hello Sir/Ma’am

In Q.26, C option has repeated edges it should be like this….

(C) (d—f),(a—b),(d—c),(b—f),(d—e)

We have updated option c for GATE 2006 CSE question.