1
GATE CSE 2003
+2
-0.6
Let G=(V,E) be an undirected graph with a subgraph G1=(V1,E1). Weights are assigned to edges of G as follows. $$w(e) = \begin{cases} 0 \text{, if } e \in E_1 \\1 \text{, otherwise} \end{cases}$$$A single-source shortest path algorithm is executed on the weighted graph (V,E,w) with an arbitrary vertex v1 of V1 as the source. Which of the following can always be inferred from the path costs computed? A The number of edges in the shortest paths from v1 to all vertices of G B G1 is connected C V1 forms a clique in G D G1 is a tree 2 GATE CSE 2003 MCQ (Single Correct Answer) +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
3
GATE CSE 2003
+1
-0.3
Ram and Shyam have been asked to show that a certain problem Π is NP-complete. Ram shows a polynomial time reduction from the 3-SAT problem to Π, and Shyam shows a polynomial time reduction from Π to 3-SAT. Which of the following can be inferred from these reductions ?
A
Π is NP-hard but not NP-complete
B
Π is in NP, but is not NP-complete
C
Π is NP-complete
D
Π is neither NP-hard, nor in NP
4
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
GATE CSE Papers
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
2000
1999
1998
1997
1996
1995
1994
1993
1992
1991
1990
1989
1988
1987
EXAM MAP
Joint Entrance Examination