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
Discrete Mathematics
Programming Languages
Theory of Computation
Operating Systems
Digital Logic
Computer Organization
Database Management System
Data Structures
Computer Networks
Algorithms
Compiler Design
Software Engineering
Web Technologies
General Aptitude
EXAM MAP
Joint Entrance Examination