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
Questions by ashutoshsharma
User ashutoshsharma
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
User ashutoshsharma
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
0
votes
0
answers
1
discrete
Let G be a connected 3  regular graph. Each edge of G lies on some cycle. Let S⊆V and C1,C2,…,Cm,m=Codd(G−S), be the odd component of G−S. Let eG(Ci,S) denote the number of edges with one end in Ci and the other in S. Then ∑(i=1 to m) eG(Ci−S) is (1) ≤m (2) ≥5m (3) ≥3m
asked
Sep 27, 2017
in
Revision

51
views
0
votes
0
answers
2
discrete
Consider the preferences given in this Problem Student 1 2 3 4 University 1 2 3 4 A d a b c a C D B A B c b a d b D C A B C c b a d c A C B D D d a b c d B D A C The University  oriented stable matching obtained using GaleShapely Algorithm is (1) {aD,bc,cA,dB} (2) {aC,bD,cA,dB} (3) None of the above
asked
Sep 27, 2017
in
Revision

25
views
0
votes
0
answers
3
discrete
Student 1 2 3 4 University 1 2 3 4 A d a b c a C D B A B c b a d b D C A B C c b a d c A C B D D d a b c d B D A C The Student  oriented stable matching obtained using Gale  Shapely Algorithm is (1) {Aa,Bb,Cc,Dd} (2) {Ac,Ba,Cb,Dd} (3) {Ac,Bd,Cb,Da} (4) None of the above
asked
Sep 27, 2017
in
Revision

23
views
0
votes
0
answers
4
discrete
Consider the preferences Student 1 2 3 4 University 1 2 3 4 A d a b c a C D B A B c b a d b D C A B C c b a d c A C B D D d a b c d B D A C Is the matching M= {Ab,Ba,Cc,Dd} stable? (A) Yes (B) No
asked
Sep 27, 2017
in
Revision

36
views
0
votes
0
answers
5
DISCRETE
Let G be a connected 3  regular graph. Each edge of G lies on some cycle. Let S⊆V and C1,C2,…,Cm,m=Codd(G−S), be the odd component of G−S. Let eG(Ci,S) denote the number of edges with one end in Ci and the other in S. Then eG(Ci,S) is (A) Even (B) Odd (C) Cannot say
asked
Sep 21, 2017
in
Revision

116
views
0
votes
0
answers
6
DISCRETE
Determine whether the graph below has a perfect matching: (A) Yes (B) No
asked
Sep 21, 2017
in
Revision

71
views
0
votes
1
answer
7
DISCRETE
Determine whether the graph below has a perfect matching: (A) Yes (B) No
asked
Sep 21, 2017
in
Revision

52
views
0
votes
0
answers
8
Discrete
What is the size of minimum vertex cover for the graph G
asked
Sep 21, 2017
in
Revision

31
views
0
votes
1
answer
9
Discrete
In the above graph, find a maximum matching M. Then M is
asked
Sep 21, 2017
in
Revision

61
views
0
votes
0
answers
10
DISCRETE
Let T be a tree with n vertices and k be the maximum size of an independent set in T. Then the size of maximum matching in T is (A) k (B) n−k (C) (n−1)/2
asked
Sep 21, 2017
in
Revision

31
views
0
votes
1
answer
11
DISCRETE
The size of minimum vertex cover can be  (A) Smaller than the size of maximum matching (B) No smaller than the size of maximum matching (C) Cannot say
asked
Sep 21, 2017
in
Revision

52
views
0
votes
0
answers
12
DISCRETE
In a class of 4 students, four committees are formed ( see the table below). Is it possible to choose a president for each committee so that no student is a president of more than one committee? Committee Members C1 Amit, Bimal, Dipak C2 Bimal, Dipak C3 Bimal, Chandan C4 Amit, Bimal, Chandan Yes No
asked
Sep 21, 2017
in
Revision

48
views
+1
vote
1
answer
13
discrete
Given a maximum matching M, if we pick one endpoint of each edge in M, this form a valid vertex cover. TRUE FALSE
asked
Sep 21, 2017
in
Revision

162
views
0
votes
0
answers
14
discrete mathematics
Let T be an n  vertex tree having one vertex of degree i for i=2,3,…,k and the remaining n−k+1 vertices are of degree 1 each. Determine n in terms of k.
asked
Sep 14, 2017
in
Revision

75
views
50,737
questions
57,275
answers
198,154
comments
104,821
users