1
GATE CSE 2006
MCQ (Single Correct Answer)
+1
-0.3
If all the edge weights of an undirected graph are positive, then any subject of edges that connects all the vertices and has minimum total weight is a
A
Hamiltonian cycle
B
grid
C
hypercube
D
tree
2
GATE CSE 2006
MCQ (Single Correct Answer)
+1
-0.3
Consider a weighted complete graph $$G$$ on the vertex set $$\left\{ {{v_1},\,\,\,{v_2},....,\,\,\,{v_n}} \right\}$$ such that the weight of the edge $$\left( {{v_i},\,\,\,\,{v_j}} \right)$$ is $$2\left| {i - j} \right|$$. The weight of a minimum spanning tree of $$G$$ is
A
$$n - 1$$
B
$$2n - 2$$
C
$$\left( {\matrix{ n \cr 2 \cr } } \right)$$
D
$${n^2}$$
3
GATE CSE 2005
MCQ (Single Correct Answer)
+1
-0.3
Let $$G$$ be a simple connected planar graph with 13 vertices and 19 edges. Then, the number of faces in the planar embedding of the graph is:
A
6
B
8
C
9
D
13
4
GATE CSE 2005
MCQ (Single Correct Answer)
+1
-0.3
Let $$G$$ be the simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of $$G$$ is 8. Then, the size of the maximum independent set of $$G$$ is:
A
12
B
8
C
Less than 8
D
More than 12
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
CBSE
Class 12