The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged graphs
0
votes
1
answer
1
Virtual Gate Test Series: Algorithms  Graphs
asked
Jan 13
in
Algorithms
by
SameekshaGupta
Junior
(
859
points)

61
views
algorithms
graphs
virtualgatetestseries
0
votes
0
answers
2
self doubt
If A = {1,2,3 …. n} then how many multisets of size 4 are possible ,such that atleast of the elements appears twice.
asked
Jan 2
in
Mathematical Logic
by
manisha11
Active
(
2.3k
points)

39
views
graphs
+1
vote
0
answers
3
Cormen 3rd edition chapter 22 question: 22.4.4
Prove or disprove: If a directed graph G contains cycles, then TOPOLOGICAL SORT $(G)$ produces a vertex ordering that minimizes the number of “bad” edges that are inconsistent with the ordering produced.
asked
Jul 4, 2018
in
Algorithms
by
Abhilash Mishra
(
91
points)

112
views
algorithms
graphtheory
graphalgorithms
topologicalsort
graphs
+1
vote
1
answer
4
Graph Book
The maximum number of edges in a nnode undirected graph WITH selfloops is?
asked
Apr 7, 2018
in
Algorithms
by
targate2018
Active
(
1.7k
points)

126
views
algorithms
graphs
+5
votes
2
answers
5
True/False
Which of the following statements related to graphs are True? Minimum Spanning Tree has ALWAYS Minimum weight edge included in it. Minimum Spanning Tree MIGHT have Maximum weight edge weight included in it. Maximum Spanning Tree has ALWAYS Maximum weight edge included ... edge included in it. Longest path from source to destination MAY OR MAY NOT have Maximum weight edge included in it.
asked
Jan 27, 2018
in
Graph Theory
by
Balaji Jegan
Active
(
4.9k
points)

208
views
graphs
graphalgorithms
algorithms
+1
vote
0
answers
6
Self Doubt on Polygraphs
If the precedence graph has a cycle,then will the polygraph also have a cycle? Why or Why not?
asked
Jan 26, 2018
in
Databases
by
Balaji Jegan
Active
(
4.9k
points)

41
views
databases
graphs
+1
vote
0
answers
7
Ace Test series: Programming & DS  Graphs
asked
Jan 6, 2018
in
Programming
by
Kuldeep Pal
Active
(
1.4k
points)

29
views
acetestseries
datastructure
graphs
0
votes
2
answers
8
MadeEasy Test Series: Programming & DS  Graphs
Consider the following graph: The minimum size of queue required when performing BFS on above graph is ________. (Size of queue is represented by maximum number of element at any time).
asked
Dec 9, 2017
in
Programming
by
rahul sharma 5
Boss
(
24.9k
points)

220
views
madeeasytestseries
datastructure
graphs
0
votes
2
answers
9
MadeEasy Test Series: Programming & DS  Graphs
In DFS traversal every vertex of the graph is visited exactly once. True / False?
asked
Dec 9, 2017
in
Programming
by
rahul sharma 5
Boss
(
24.9k
points)

118
views
madeeasytestseries
datastructure
graphs
0
votes
0
answers
10
GATE Graph Theory
Let G = (V, E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G? ( A ) G1 = (V, E1) where E1 = {(u, v)  (u, v) ∉ E} ( B ) G2 ... D ) G4 = (V4, E) where V4 is the set of vertices in G which are not isolated Can anyone give a detailed answer to this question, please? :)
asked
May 12, 2017
in
Graph Theory
by
Bongbirdie
Junior
(
697
points)

205
views
graphtheory
graphs
graphconnectivity
0
votes
1
answer
11
Testbook
I am not getting how statement 3 is false and statement 4 is true. Statement 3: If the weights are unique, ho can there be multiple second best spanning trees? Statement 4: If the graph is triangle, wont there be any spanning tree?
asked
Jan 23, 2017
in
Programming
by
Sushant Gokhale
Boss
(
18.3k
points)

68
views
graphs
+3
votes
3
answers
12
Testbook Test Series: Programming & DS  Graphs
asked
Jan 11, 2017
in
Programming
by
focus _GATE
Boss
(
19.9k
points)

128
views
testbooktestseries
testseries
datastructure
dfs
graphs
0
votes
2
answers
13
UGCNETJune2010II4
$S_{1}$ : I teach algorithms and maths. $S_{2}$ : My professor teaches maths, electronics and computer science. $S_{3}$ : I have a student of maths. $S_{4}$ : Algorithm is a part of computer science. $S_{5}$ : Maths students know computer science. ... relationships amongst the entities/actors as expressed in the sentences $S_{1}$ to $S_{5}$ above ? $2$ $3$ $4$ None of these
asked
Sep 15, 2016
in
DS
by
makhdoom ghaya
Boss
(
29.7k
points)

275
views
ugcnetjune2010ii
datastructure
graphs
+3
votes
1
answer
14
UGCNETJune2012III31
The upper bound of computing time of m colouring decision problem is $O(nm)$ $O(n^m)$ $O(nm^n)$ $O(n^mm^n)$
asked
Jul 7, 2016
in
Programming
by
jothee
Veteran
(
103k
points)

416
views
ugcnetjune2012iii
graphs
graphcoloring
+31
votes
7
answers
15
GATE2016138
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$ ... possible integer value of $x$, for which at least one shortest path between some pair of vertices will contain the edge with weight $x$ is ___________.
asked
Feb 12, 2016
in
DS
by
Sandeep Singh
Loyal
(
7.1k
points)

7.5k
views
gate20161
datastructure
graphs
normal
numericalanswers
+32
votes
4
answers
16
GATE2008IT4
What is the size of the smallest MIS (Maximal Independent Set) of a chain of nine nodes? $5$ $4$ $3$ $2$
asked
Oct 28, 2014
in
DS
by
Ishrat Jahan
Boss
(
16.3k
points)

3.8k
views
gate2008it
datastructure
normal
graphs
+28
votes
4
answers
17
GATE19976.2
Let $G$ be the graph with $100$ vertices numbered $1$ to $100$. Two vertices $i$ and $j$ are adjacent if $\vert ij \vert =8$ or $\vert ij \vert=12$. The number of connected components in $G$ is $8$ $4$ $12$ $25$
asked
Sep 29, 2014
in
DS
by
Kathleen
Veteran
(
52.1k
points)

2.4k
views
gate1997
datastructure
normal
graphs
+34
votes
5
answers
18
GATE200842
$G$ is a graph on $n$ vertices and $2n2$ edges. The edges of $G$ can be partitioned into two edgedisjoint spanning trees. Which of the following is NOT true for $G$? For every subset of $k$ ... are at least $2$ edgedisjoint paths between every pair of vertices. There are at least $2$ vertexdisjoint paths between every pair of vertices.
asked
Sep 27, 2014
in
DS
by
Akshay Jindal
(
385
points)

7.2k
views
gate2008
datastructure
graphs
normal
+32
votes
2
answers
19
GATE201413
Let $G=(V,E)$ be a directed graph where $V$ is the set of vertices and $E$ the set of edges. Then which one of the following graphs has the same strongly connected components as $G$ ? $G_1$ = $(V,E_1)$ where $E_1 = \left\{(u,v) \mid (u,v) \notin E\right\}$ $G_2$ ... $\leq2$ from $u$ to $v$ in $E\}$ $G_4$ = $(V_4,E)$ where $V_4$ is the set of vertices in $G$ which are not isolated
asked
Sep 26, 2014
in
DS
by
jothee
Veteran
(
103k
points)

4.1k
views
gate20141
datastructure
graphs
ambiguous
+19
votes
3
answers
20
GATE199203,iii
How many edges can there be in a forest with $p$ components having $n$ vertices in all?
asked
Sep 13, 2014
in
DS
by
Kathleen
Veteran
(
52.1k
points)

1.4k
views
gate1992
datastructure
graphs
easy
To see more, click for the
full list of questions
or
popular tags
.
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
Recent Posts
Recruitment to the post of Scientist/Engineer 'SC' (Electronics, Mechanical and Computer Science)
Standard Videos for Calculus
Standard Videos for Linear Algebra
Standard Videos for Graph Theory
Standard Videos for Combinatory
Follow @csegate
Recent questions tagged graphs
Recent Blog Comments
Exam date is 1212020.
Where is this mentioned?
Nope :(
is it for final year student or not??
12Jan2020 exam date
50,309
questions
55,731
answers
192,186
comments
90,355
users