1
GATE CSE 2003
+2
-0.6
Let G = (V, E) be a directed graph with n vertices. A path from vi to vj in G is sequence of vertices (vi, vi+1, ……., vj) such that (vk, vk+1) ∈ E for all k in i through j – 1. A simple path is a path in which no vertex appears more than once. Let A be an n x n array initialized as follow
$$A[j,k] = \left\{ {\matrix{ {1\,if\,(j,\,k)} \cr {1\,otherwise} \cr } } \right.$$\$ Consider the following algorithm.
for i = 1 to n
for j = 1 to n
for k = 1 to n
A [j , k] = max (A[j, k] (A[j, i] + A [i, k]); 
Which of the following statements is necessarily true for all j and k after terminal of the above algorithm ?
A
$$A\left[ {j,{\rm{ }}k} \right]{\rm{ }} \le {\rm{ }}n$$
B
If $${\rm{A[j, k] = n }} - 1$$, then G has a Hamiltonian cycle
C
If there exists a path from j to k, A[j, k] contains the longest path lens from j to k
D
If there exists a path from j to k, every simple path from j to k contain most A[j, k] edges
2
GATE CSE 2003
+2
-0.6
What is the weight of a minimum spanning tree of the following graph?
A
29
B
31
C
38
D
41
3
GATE CSE 2000
+2
-0.6
Let G be an undirected connected graph with distinct edge weight. Let emax be the edge with maximum weight and emin the edge with minimum weight. Which of the following statements is false?
A
Every minimum spanning tree of G must contain emin
B
If emax is in a minimum spanning tree, then its removal must disconnect G
C
No minimum spanning tree contains emax
D
G has a unique minimum spanning tree
4
GATE CSE 1992
Fill in the Blanks
+2
-0
Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing n vertices and m edges if the edges are sorted is _______.
GATE CSE Subjects
EXAM MAP
Medical
NEET