1
GATE CSE 2018
Numerical
+2
-0
Let $$G$$ be a graph with $$100!$$ vertices, with each vertex labelled by a distinct permutation of the numbers $$1,2, … , 100.$$ There is an edge between vertices $$u$$ and $$v$$ if and only if the label of $$u$$ can be obtained by swapping two adjacent numbers in the label of $$v.$$ Let $$𝑦$$ denote the degree of a vertex in $$G,$$ and $$𝑧$$ denote the number of connected components in $$G.$$ Then, $$𝑦 + 10𝑧 =$$ _____.
2
GATE CSE 2016 Set 2
+2
-0.6
In an adjacency list representation of an undirected simple graph $$G = (V,E),$$ each edge $$(u, v)$$ has two adjacency list entries: $$[v]$$ in the adjacency list of $$u,$$ and $$[u]$$ in the adjacency list of $$v.$$ These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If $$|E| = m$$ and $$|V| = n,$$ and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?
A
$$\Theta \left( {{n^2}} \right)$$
B
$$\Theta \left( {n + m} \right)$$
C
$$\Theta \left( {{m^2}} \right)$$
D
$$\Theta \left( {{n^4}} \right)$$
3
GATE CSE 2015 Set 3
Numerical
+2
-0
Let $$G$$ be a connected undirected graph of $$100$$ vertices and $$300$$ edges. The weight of a minimum spanning tree of $$G$$ is $$500.$$ When the weight of each edge of $$G$$ is increased by five, the weight of a minimum spanning tree becomes ________.
4
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
GATE CSE Subjects
EXAM MAP
Medical
NEET