Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Search results for graph
60
votes
10
answers
1
GATE CSE 2003 | Question: 36
How many perfect matching are there in a complete graph of $6$ vertices? $15$ $24$ $30$ $60$
How many perfect matching are there in a complete graph of $6$ vertices?$15$$24$$30$$60$
Kathleen
50.5k
views
Kathleen
asked
Sep 16, 2014
Graph Theory
gatecse-2003
graph-theory
graph-matching
normal
+
–
113
votes
9
answers
2
GATE CSE 2012 | Question: 38
Let $G$ be a complete undirected graph on $6$ vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length $4$ in $G$ is equal to $15$ $30$ $90$ $360$
Let $G$ be a complete undirected graph on $6$ vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length $4$ in $G$ is equal to$15$$30$$90$$36...
gatecse
35.1k
views
gatecse
asked
Sep 12, 2014
Graph Theory
gatecse-2012
graph-theory
normal
marks-to-all
counting
+
–
78
votes
12
answers
3
GATE CSE 1994 | Question: 1.6, ISRO2008-29
The number of distinct simple graphs with up to three nodes is $15$ $10$ $7$ $9$
The number of distinct simple graphs with up to three nodes is$15$$10$$7$$9$
Kathleen
34.9k
views
Kathleen
asked
Oct 4, 2014
Graph Theory
gate1994
graph-theory
graph-connectivity
combinatory
normal
isro2008
counting
+
–
31
votes
6
answers
4
GATE CSE 2008 | Question: 19
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: $\text{MNOPQR}$ $\text{NQMPOR}$ $\text{QMNPRO}$ $\text{QMNPOR}$
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:$\text{MNOPQR}$...
Kathleen
35.8k
views
Kathleen
asked
Sep 11, 2014
Algorithms
gatecse-2008
normal
algorithms
graph-algorithms
graph-search
+
–
101
votes
10
answers
5
GATE CSE 2014 Set 1 | Question: 51
Consider an undirected graph $G$ where self-loops are not allowed. The vertex set of $G$ is $\{(i,j) \mid1 \leq i \leq 12, 1 \leq j \leq 12\}$. There is an edge between $(a,b)$ and $(c,d)$ if $|a-c| \leq 1$ and $|b-d| \leq 1$. The number of edges in this graph is______.
Consider an undirected graph $G$ where self-loops are not allowed. The vertex set of $G$ is $\{(i,j) \mid1 \leq i \leq 12, 1 \leq j \leq 12\}$. There is an edge between $...
go_editor
26.9k
views
go_editor
asked
Sep 28, 2014
Graph Theory
gatecse-2014-set1
graph-theory
numerical-answers
normal
graph-connectivity
+
–
59
votes
7
answers
6
GATE CSE 2006 | Question: 12
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
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:QueueStackHeapB-Tree
Rucha Shelke
31.7k
views
Rucha Shelke
asked
Sep 16, 2014
Algorithms
gatecse-2006
algorithms
graph-algorithms
easy
+
–
66
votes
9
answers
7
GATE CSE 2012 | Question: 40
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 ... a strictly shorter path to $v$ is discovered. $\text{SDT}$ $\text{SBDT}$ $\text{SACDT}$ $\text{SACET}$
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...
gatecse
26.9k
views
gatecse
asked
Sep 26, 2014
Algorithms
gatecse-2012
algorithms
graph-algorithms
normal
+
–
63
votes
11
answers
8
GATE CSE 2008 | Question: 45
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
Dijkstra's single source shortest path algorithm when run from vertex $a$ in the above graph, computes the correct shortest path distance toonly vertex $a$only vertices $...
Kathleen
27.7k
views
Kathleen
asked
Sep 12, 2014
Algorithms
gatecse-2008
algorithms
graph-algorithms
normal
+
–
67
votes
4
answers
9
GATE CSE 2014 Set 3 | Question: 34
Consider the basic block given below. a = b + c c = a + d d = b + c e = d - b a = e + b The minimum number of nodes and edges present in the DAG representation of the above basic block respectively are $6$ and $6$ $8$ and $10$ $9$ and $12$ $4$ and $4$
Consider the basic block given below. a = b + c c = a + d d = b + c e = d - b a = e + b The minimum number of nodes and edges present in the DAG representation of the abo...
go_editor
35.3k
views
go_editor
asked
Sep 28, 2014
Compiler Design
gatecse-2014-set3
compiler-design
code-optimization
directed-acyclic-graph
normal
+
–
61
votes
5
answers
10
GATE CSE 2016 Set 1 | Question: 11
Consider the following directed graph: The number of different topological orderings of the vertices of the graph is _____________.
Consider the following directed graph:The number of different topological orderings of the vertices of the graph is _____________.
Sandeep Singh
28.6k
views
Sandeep Singh
asked
Feb 12, 2016
Algorithms
gatecse-2016-set1
algorithms
graph-algorithms
normal
numerical-answers
topological-sort
+
–
39
votes
9
answers
11
GATE CSE 2014 Set 2 | Question: 3
The maximum number of edges in a bipartite graph on $12$ vertices is____
The maximum number of edges in a bipartite graph on $12$ vertices is____
go_editor
27.2k
views
go_editor
asked
Sep 28, 2014
Graph Theory
gatecse-2014-set2
graph-theory
graph-connectivity
numerical-answers
normal
+
–
65
votes
9
answers
12
GATE CSE 2016 Set 1 | Question: 38
Consider the weighted undirected graph with $4$ vertices, where the weight of edge $\{i,j\}$ is given by the entry $W_{ij}$ in the matrix $W$ ... integer value of $x$, for which at least one shortest path between some pair of vertices will contain the edge with weight $x$ is ___________.
Consider the weighted undirected graph with $4$ vertices, where the weight of edge $\{i,j\}$ is given by the entry $W_{ij}$ in the matrix $W$. W=$\begin{bmatrix} 0&2 &8 &...
Sandeep Singh
24.1k
views
Sandeep Singh
asked
Feb 12, 2016
DS
gatecse-2016-set1
data-structures
graph-theory
normal
numerical-answers
+
–
33
votes
14
answers
13
GATE CSE 2019 | Question: 12
Let $G$ be an undirected complete graph on $n$ vertices, where $n > 2$. Then, the number of different Hamiltonian cycles in $G$ is equal to $n!$ $(n-1)!$ $1$ $\frac{(n-1)!}{2}$
Let $G$ be an undirected complete graph on $n$ vertices, where $n 2$. Then, the number of different Hamiltonian cycles in $G$ is equal to$n!$$(n-1)!$$1$$\frac{(n-1)!}{2}...
Arjun
21.4k
views
Arjun
asked
Feb 7, 2019
Graph Theory
gatecse-2019
engineering-mathematics
discrete-mathematics
graph-theory
graph-connectivity
1-mark
+
–
38
votes
5
answers
14
GATE CSE 2020 | Question: 31
Let $G = (V, E)$ be a weighted undirected graph and let $T$ be a Minimum Spanning Tree (MST) of $G$ maintained using adjacency lists. Suppose a new weighed edge $(u, v) \in V \times V$ is added to $G$. The worst case time complexity of determining if $T$ is still an MST ... $\Theta (\mid E \mid \mid V \mid) \\$ $\Theta(E \mid \log \mid V \mid) \\$ $\Theta( \mid V \mid)$
Let $G = (V, E)$ be a weighted undirected graph and let $T$ be a Minimum Spanning Tree (MST) of $G$ maintained using adjacency lists. Suppose a new weighed edge $(u, v) ...
Arjun
19.1k
views
Arjun
asked
Feb 12, 2020
Algorithms
gatecse-2020
algorithms
minimum-spanning-tree
graph-algorithms
2-marks
+
–
33
votes
9
answers
15
GATE CSE 2015 Set 1 | Question: 54
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.
makhdoom ghaya
24.7k
views
makhdoom ghaya
asked
Feb 13, 2015
Graph Theory
gatecse-2015-set1
graph-theory
graph-connectivity
normal
graph-planarity
numerical-answers
+
–
90
votes
12
answers
16
GATE CSE 2006 | Question: 48
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$
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 $...
Rucha Shelke
21.2k
views
Rucha Shelke
asked
Sep 26, 2014
Algorithms
gatecse-2006
algorithms
graph-algorithms
normal
+
–
89
votes
6
answers
17
GATE CSE 2006 | Question: 72
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements. The maximum degree of a vertex in $G$ is: $\binom{\frac{n}{2}}{2}.2^{\frac{n}{2}}$ $2^{n-2}$ $2^{n-3}\times 3$ $2^{n-1}$
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets...
go_editor
17.9k
views
go_editor
asked
Apr 24, 2016
Graph Theory
gatecse-2006
graph-theory
normal
degree-of-graph
+
–
65
votes
12
answers
18
GATE IT 2005 | Question: 14
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$
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$
Ishrat Jahan
17.9k
views
Ishrat Jahan
asked
Nov 3, 2014
Algorithms
gateit-2005
algorithms
graph-algorithms
normal
graph-search
+
–
86
votes
5
answers
19
GATE CSE 2003 | Question: 67
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
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_...
Kathleen
20.2k
views
Kathleen
asked
Sep 17, 2014
Algorithms
gatecse-2003
algorithms
graph-algorithms
normal
+
–
39
votes
6
answers
20
GATE CSE 2020 | Question: 40
Let $G = (V,E)$ be a directed, weighted graph with weight function $w: E \rightarrow \mathbb{R}$. For some function $f: V \rightarrow \mathbb{R}$, for each edge$(u,v)\in E$, define ${w}'(u,v)$ as $w(u,v)+f(u)-f(v)$. Which one of the ... from $s$ to $u$ in the graph obtained by adding a new vertex $s$ to $G$ and edges of zero weight from $s$ to every vertex of $G$
Let $G = (V,E)$ be a directed, weighted graph with weight function $w: E \rightarrow \mathbb{R}$. For some function $f: V \rightarrow \mathbb{R}$, for each edge$(u,v)\in ...
Arjun
18.2k
views
Arjun
asked
Feb 12, 2020
Algorithms
gatecse-2020
algorithms
graph-algorithms
2-marks
+
–
Page:
1
2
3
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register