1
GATE CSE 2015 Set 1
+2
-0.6
Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For $$x \in V$$, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u, v) is an edge of G that is not in T, then which one of the following CANNOT be the value of $$d\left( u \right) - d\left( v \right)$$?
A
-1
B
0
C
1
D
2
2
GATE CSE 2012
+2
-0.6
Let G be a weighted graph with edge weights greater than one and G' be the graph constructed by squaring the weights of edges in G. Let T and T' be the minimum spanning trees of G and G' respectively, with total weights t and t'. Which of the following statements is TRUE?
A
T' = T with total weight t' = t2
B
T' = T with total weight t' < t2
C
T' =! T but total weight t' = t2
D
None of these
3
GATE CSE 2010
+2
-0.6
Consider a complete undirected graph with vertex set {0,1,2,3,4}. Entry Wij in the matrix W below is the weight of the edge {i, j} $$W = \left( {\matrix{ 0 & 1 & 8 & 1 & 4 \cr 1 & 0 & {12} & 4 & 9 \cr 8 & {12} & 0 & 7 & 3 \cr 1 & 4 & 7 & 0 & 2 \cr 4 & 9 & 3 & 2 & 0 \cr } } \right)$$$What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T? A 7 B 8 C 9 D 10 4 GATE CSE 2010 MCQ (Single Correct Answer) +2 -0.6 Consider a complete undirected graph with vertex set {0,1,2,3,4}. Entry Wij in the matrix W below is the weight of the edge {i, j} $$W = \left( {\matrix{ 0 & 1 & 8 & 1 & 4 \cr 1 & 0 & {12} & 4 & 9 \cr 8 & {12} & 0 & 7 & 3 \cr 1 & 4 & 7 & 0 & 2 \cr 4 & 9 & 3 & 2 & 0 \cr } } \right)$$$ What is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?
A
7
B
8
C
9
D
10
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