Recent questions tagged graph-algorithms
Register

Recent questions tagged graph-algorithms

Recent questions tagged graph-algorithms
0 votes
0 answers 37 views
GATE2016-1-11 Video Solution
Consider the following directed graph: The number of different topological orderings of the vertices of the graph is _____________.
admin asked in Algorithms Apr 18, 2020
by admin
589 points
37 views
0 votes
0 answers 21 views
GATE2006-12 Video Solution
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is: Queue Stack Heap B-Tree
admin asked in Algorithms Apr 18, 2020
by admin
589 points
21 views
0 votes
0 answers 31 views
GATE2012-40 Video Solution
Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices $S$ and $T$. Which one will be reported by Dijkstra’s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex $v$ is updated only when a strictly shorter path to $v$ is discovered. $\text{SDT}$ $\text{SBDT}$ $\text{SACDT}$ $\text{SACET}$
admin asked in Algorithms Apr 18, 2020
by admin
589 points
31 views
0 votes
0 answers 25 views
GATE2008-45 Video Solution
Dijkstra's single source shortest path algorithm when run from vertex $a$ in the above graph, computes the correct shortest path distance to only vertex $a$ only vertices $a, e, f, g, h$ only vertices $a, b, c, d$ all the vertices
admin asked in Algorithms Apr 18, 2020
by admin
589 points
25 views
0 votes
0 answers 24 views
GATE2016-2-41 Video Solution
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 ... $\Theta\left(n^{2}\right)$ $\Theta\left(n+m\right)$ $\Theta\left(m^{2}\right)$ $\Theta\left(n^{4}\right)$
admin asked in Algorithms Apr 18, 2020
by admin
589 points
24 views
0 votes
0 answers 25 views
GATE2018-43 Video Solution
Let $G$ be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers $1, 2,\ldots, 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 ... denote the degree of a vertex in $G$, and $z$ denote the number of connected components in $G$. Then, $y+10z$ = ____
admin asked in Algorithms Apr 18, 2020
by admin
589 points
25 views
0 votes
0 answers 13 views
GATE2006-48 Video Solution
Let $T$ be a depth first search tree in an undirected graph $G$. Vertices $u$ and $ν$ are leaves of this tree $T$. The degrees of both $u$ and $ν$ in $G$ are at least $2$ ... exist a cycle in $G$ containing $u$ and $ν$ There must exist a cycle in $G$ containing $u$ and all its neighbours in $G$
admin asked in Algorithms Apr 18, 2020
by admin
589 points
13 views
0 votes
0 answers 17 views
GATE2003-67 Video Solution
Let $G =(V,E)$ be an undirected graph with a subgraph $G_1 = (V_1, E_1)$. 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 ... edges in the shortest paths from $v_1$ to all vertices of $G$ $G_1$ is connected $V_1$ forms a clique in $G$ $G_1$ is a tree
admin asked in Algorithms Apr 18, 2020
by admin
589 points
17 views
0 votes
0 answers 30 views
GATE2011-54 Video Solution
An undirected graph $G(V,E)$ contains $n \: (n>2)$ nodes named $v_1,v_2, \dots, v_n$. Two nodes $v_i, v_j$ are connected if and only if $ 0 < \mid i-j\mid \leq 2$. Each edge $(v_i,v_j)$ is assigned a weight $i+j$. A sample graph with $n=4$ is shown below. ... spanning tree (MST) of such a graph with $n$ nodes? $\frac{1}{12} (11n^2 - 5 n)$ $n^2-n+1$ $6n-11$ $2n+1$
admin asked in Algorithms Apr 18, 2020
by admin
589 points
30 views
0 votes
0 answers 21 views
GATE2015-1-45 Video Solution
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 ... that is not in $T$, then which one of the following CANNOT be the value of $d(u) - d(v)$? $-1$ $0$ $1$ $2$
admin asked in Algorithms Apr 18, 2020
by admin
589 points
21 views
0 votes
0 answers 23 views
GATE2018-47 Video Solution
Consider the following undirected graph $G$: Choose a value for $x$ that will maximize the number of minimum weight spanning trees (MWSTs) of $G$. The number of MWSTs of $G$ for this value of $x$ is ____.
admin asked in Algorithms Apr 18, 2020
by admin
589 points
23 views
0 votes
0 answers 26 views
GATE2009-13 Video Solution
Which of the following statement(s) is/are correct regarding Bellman-Ford shortest path algorithm? P: Always finds a negative weighted cycle, if one exists. Q: Finds whether any negative weighted cycle is reachable from the source. $P$ only $Q$ only Both $P$ and $Q$ Neither $P$ nor $Q$
admin asked in Algorithms Apr 18, 2020
by admin
589 points
26 views
0 votes
0 answers 28 views
GATE2003-70 Video Solution
Let $G= (V,E)$ be a directed graph with $n$ vertices. A path from $v_i$ to $v_j$ in $G$ is a sequence of vertices ($v_{i},v_{i+1}, \dots , v_j$) such that $(v_k, v_{k+1}) \in E$ for all $k$ in $i$ through $j-1$. A simple path is a path in ... length from $j$ to $k$ If there exists a path from $j$ to $k$, every simple path from $j$ to $k$ contains at most $A[j,k]$ edges
admin asked in Algorithms Apr 18, 2020
by admin
589 points
28 views
0 votes
0 answers 20 views
GATE2007-41 Video Solution
In an unweighted, undirected connected graph, the shortest path from a node $S$ to every other node is computed most efficiently, in terms of time complexity, by Dijkstra’s algorithm starting from $S$. Warshall’s algorithm. Performing a DFS starting from $S$. Performing a BFS starting from $S$.
admin asked in Algorithms Apr 18, 2020
by admin
589 points
20 views
0 votes
0 answers 19 views
GATE2005-IT-14 Video Solution
In a depth-first traversal of a graph $G$ with $n$ vertices, $k$ edges are marked as tree edges. The number of connected components in $G$ is $k$ $k+1$ $n-k-1$ $n-k$
admin asked in Algorithms Apr 18, 2020
by admin
589 points
19 views
0 votes
0 answers 19 views
GATE2005-38 Video Solution
Let $G(V,E)$ be an undirected graph with positive edge weights. Dijkstra’s single source shortest path algorithm can be implemented using the binary heap data structure with time complexity: $O\left(|V|^2\right)$ $O\left(|E|+|V|\log |V|\right)$ $O\left(|V|\log|V|\right)$ $O\left(\left(|E|+|V|\right)\log|V|\right)$
admin asked in Algorithms Apr 18, 2020
by admin
589 points
19 views
0 votes
0 answers 19 views
GATE2013-19 Video Solution
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices? $\theta(n^2)$ $\theta(n^2\log n)$ $\theta(n^3)$ $\theta(n^3\log n)$
admin asked in Algorithms Apr 18, 2020
by admin
589 points
19 views
0 votes
0 answers 22 views
GATE2011-55 Video Solution
An undirected graph $G(V,E)$ contains $n \: (n>2)$ nodes named $v_1,v_2, \dots, v_n$. Two nodes $v_i, v_j$ are connected if and only if $ 0 < \mid i-j\mid \leq 2$. Each edge $(v_i,v_j)$ is assigned a weight $i+j$. A sample graph with $n=4$ is shown below. The length of the path from $v_5$ to $v_6$ in the MST of previous question with $n=10$ is $11$ $25$ $31$ $41$
admin asked in Algorithms Apr 18, 2020
by admin
589 points
22 views
0 votes
0 answers 17 views
GATE2007-IT-24 Video Solution
A depth-first search is performed on a directed acyclic graph. Let $d[u]$ denote the time at which vertex $u$ is visited for the first time and $f[u]$ the time at which the DFS call to the vertex $u$ terminates. Which of the following statements is always TRUE for all edges $(u, v)$ in the graph ? $d[u] < d[v]$ $d[u] < f[v]$ $f[u] < f[v]$ $f[u] > f[v]$
admin asked in Algorithms Apr 18, 2020
by admin
589 points
17 views
0 votes
0 answers 20 views
GATE2017-1-26 Video Solution
Let $G=\left ( V,E \right )$ be $any$ connected, undirected, edge-weighted graph. The weights of the edges in $E$ are positive and distinct. Consider the following statements: Minimum Spanning Tree of $G$ is always unique. Shortest path between any ... is always unique. Which of the above statements is/are necessarily true? I only II only both I and II neither I nor II
admin asked in Algorithms Apr 18, 2020
by admin
589 points
20 views
0 votes
0 answers 34 views
GATE2006-IT-46 Video Solution
Which of the following is the correct decomposition of the directed graph given below into its strongly connected components? $\left \{ P, Q, R, S \right \}, \left \{ T \right \},\left \{ U \right \}, \left \{ V \right \}$ ... $\left \{ P, Q, R, S, T, U, V \right \}$
admin asked in Algorithms Apr 18, 2020
by admin
589 points
34 views
0 votes
0 answers 29 views
GATE1998-1.21, ISRO2008-16 Video Solution
Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph? Dynamic programming Backtracking Greedy Divide and Conquer
admin asked in Algorithms Apr 18, 2020
by admin
589 points
29 views
0 votes
0 answers 17 views
GATE2004-81 Video Solution
Let $G_1=(V,E_1)$ and $G_2 =(V,E_2)$ be connected graphs on the same vertex set $V$ with more than two vertices. If $G_1 \cap G_2= (V,E_1\cap E_2)$ is not a connected graph, then the graph $G_1\cup G_2=(V,E_1\cup E_2)$ cannot have a cut vertex must have a cycle must have a cut-edge (bridge) has chromatic number strictly greater than those of $G_1$ and $G_2$
admin asked in Algorithms Apr 18, 2020
by admin
589 points
17 views
0 votes
0 answers 20 views
GATE2014-3-13 Video Solution
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.
admin asked in Algorithms Apr 18, 2020
by admin
589 points
20 views
0 votes
0 answers 55 views
GATE2016-2-11 Video Solution
Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex $t$ at a distance four from the root. If $t$ is the $n^{th}$ vertex in this BFS traversal, then the maximum possible value of $n$ is __________
admin asked in Algorithms Apr 18, 2020
by admin
589 points
55 views
0 votes
0 answers 24 views
GATE2001-2.14 Video Solution
Consider an undirected, unweighted graph $G$. Let a breadth-first traversal of $G$ be done starting from a node $r$. Let $d(r,u)$ and $d(r,v)$ be the lengths of the shortest paths from $r$ to $u$ and $v$ respectively in $G$. If $u$ is visited before $v$ during the breadth-first ... correct? $d(r,u) < d(r,v)$ $d(r,u) > d(r,v)$ $d(r,u) \leq d(r,v)$ None of the above
admin asked in Algorithms Apr 18, 2020
by admin
589 points
24 views
0 votes
0 answers 15 views
GATE2005-82a Video Solution
Let $s$ and $t$ be two vertices in a undirected graph $G=(V,E)$ having distinct positive edge weights. Let $[X,Y]$ be a partition of $V$ such that $s \in X$ and $t \in Y$. Consider the edge $e$ having the minimum weight amongst all those edges that ... of $G$ the weighted shortest path from $s$ to $t$ each path from $s$ to $t$ the weighted longest path from $s$ to $t$
admin asked in Algorithms Apr 18, 2020
by admin
589 points
15 views
0 votes
0 answers 17 views
GATE2005-IT-84a Video Solution
A sink in a directed graph is a vertex i such that there is an edge from every vertex $j \neq i$ to $i$ and there is no edge from $i$ to any other vertex. A directed graph $G$ with $n$ vertices is represented by its adjacency matrix $A$, where $A[i] [j] = 1$ if there is an edge ... $E_1:\ !A[i][j]$ and $E_2 : i = j$; $E_1 : A[i][j]$ and $E_2 : i = j + 1$;
admin asked in Algorithms Apr 18, 2020
by admin
589 points
17 views
0 votes
0 answers 28 views
GATE2007-IT-3, UGCNET-June2012-III-34 Video Solution
admin asked in Algorithms Apr 18, 2020
by admin
589 points
28 views
0 votes
0 answers 17 views
GATE2008-7 Video Solution
The most efficient algorithm for finding the number of connected components in an undirected graph on $n$ vertices and $m$ edges has time complexity $\Theta(n)$ $\Theta(m)$ $\Theta(m+n)$ $\Theta(mn)$
admin asked in Algorithms Apr 18, 2020
by admin
589 points
17 views
0 votes
0 answers 18 views
GATE2014-2-14 Video Solution
Consider the tree arcs of a BFS traversal from a source node $W$ in an unweighted, connected, undirected graph. The tree $T$ ... graph. the shortest paths from $W$ to only those nodes that are leaves of $T$. the longest path in the graph.
admin asked in Algorithms Apr 18, 2020
by admin
589 points
18 views
0 votes
0 answers 19 views
GATE1994-1.22 Video Solution
Which of the following statements is false? Optimal binary search tree construction can be performed efficiently using dynamic programming Breadth-first search cannot be used to find connected components of a graph Given the prefix and postfix walks ... binary tree cannot be uniquely constructed. Depth-first search can be used to find connected components of a graph
admin asked in Algorithms Apr 18, 2020
by admin
589 points
19 views
0 votes
0 answers 67 views
GATE2008-IT-45 Video Solution
For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Span­ning Tree? $\text{(a, b), (d, f), (f, c), (g, i), (d, a), (g, h), (c, e), (f, h)}$ ... $\text{(h, g), (g, i), (h, f), (f, c), (f, d), (d, a), (a, b), (c, e)}$
admin asked in Algorithms Apr 18, 2020
by admin
589 points
67 views
0 votes
0 answers 33 views
GATE2004-44 Video Solution
Suppose we run Dijkstra’s single source shortest path algorithm on the following edge-weighted directed graph with vertex $P$ as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized? $P,Q,R,S,T,U$ $P,Q,R,U,S,T$ $P,Q,R,U,T,S$ $P,Q,T,R,U,S$
admin asked in Algorithms Apr 18, 2020
by admin
589 points
33 views
0 votes
0 answers 42 views
GATE2008-19 Video Solution
The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is: $MNOPQR$ $NQMPOR$ $QMNPRO$ $QMNPOR$
admin asked in Algorithms Apr 18, 2020
by admin
589 points
42 views
Page:
Ask a Question
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Developed by Chun