More
Consider a weighted complete graph G on the vertex set {v1, v2, ..vn} such that the weight of the edge (vi, vj) is $$2|i... GATE CSE 2006 To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure ... GATE CSE 2006 Let$$G$$be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increase... GATE CSE 2016 Set 1 ## Marks 2 More Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph G with n vertices and m edges has the time c... GATE CSE 1991 The weighted external path length of the binary tree in figure is ___________. ... GATE CSE 1991 Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing n vertices and... GATE CSE 1992 Let G be an undirected connected graph with distinct edge weight. Let emax be the edge with maximum weight and emin the ... GATE CSE 2000 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) = ...
GATE CSE 2003
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...
GATE CSE 2003
What is the weight of a minimum spanning tree of the following graph? ...
GATE CSE 2003
Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge-weighted directed graph with verte...
GATE CSE 2004
Consider the following graph: Which one of the following cannot be the sequence of edges added, in that order, to a min...
GATE CSE 2006
Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. Which of the follo...
GATE CSE 2007
Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight ...
GATE CSE 2007
Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. What is the averag...
GATE CSE 2007
In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most effic...
GATE CSE 2007
Dijkstra's single source shortest path algorithm when run from vertex a in the above graph, computes the correct shorte...
GATE CSE 2008
Consider the following graph: Which one of the following is NOT the sequence of edges added to the minimum spanning tree...
GATE CSE 2009
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W(ij) in the matrix W below is the weight of...
GATE CSE 2010
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W(ij) in the matrix W below is the weight of...
GATE CSE 2010
An undirected graph G(V, E) contains n ( n > 2 ) nodes named v1 , v2 ,….vn. Two nodes vi , vj are connected if and only ...
GATE CSE 2011
An undirected graph G(V, E) contains n ( n > 2 ) nodes named v1 , v2 ,….vn. Two nodes vi , vj are connected if and only ...
GATE CSE 2011
Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which...
GATE CSE 2012
Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a ...
GATE CSE 2014 Set 2
The number of distinct minimum spanning trees for the weighted graph below is ________ ...
GATE CSE 2014 Set 2
The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 an...
GATE CSE 2015 Set 1
A Young tableau is a $$2D$$ array of integers increasing from left to right and from top to bottom. Any unfilled entries...
GATE CSE 2015 Set 2
Consider the weighted undirected graph with $$4$$ vertices, where the weight of edge $$\left\{ {i,j} \right\}$$ is given...
GATE CSE 2016 Set 1
$$G = (V,E)$$ is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. W...
GATE CSE 2016 Set 1
Consider the weights and values of items listed below. Note that there is only one unit of each item. .tg {border-col...
GATE CSE 2018
Consider the following undirected graph $$G:$$ Choose a value for $$x$$ that will maximize the number of minimum weig...
GATE CSE 2018
Let G = (V, E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency...
GATE CSE 2020
Consider a graph G = (V, E), where V = {v1, v2, ...., v100}, E = {(vi, vj) | 1 ≤ i i, vj) is |i - j|. The weight of the...
GATE CSE 2020