search
Log In

Questions by ashutoshsharma

0 votes
0 answers
1
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 114 views
0 votes
0 answers
2
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 Gale-Shapely Algorithm is (1) {aD,bc,cA,dB} (2) {aC,bD,cA,dB} (3) None of the above
asked Sep 27, 2017 in Revision 41 views
0 votes
0 answers
3
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 33 views
0 votes
0 answers
4
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 45 views
0 votes
0 answers
5
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 130 views
0 votes
0 answers
6
Determine whether the graph below has a perfect matching: (A) Yes (B) No
asked Sep 21, 2017 in Revision 85 views
0 votes
1 answer
7
Determine whether the graph below has a perfect matching: (A) Yes (B) No
asked Sep 21, 2017 in Revision 75 views
0 votes
0 answers
8
What is the size of minimum vertex cover for the graph G
asked Sep 21, 2017 in Revision 42 views
0 votes
1 answer
9
In the above graph, find a maximum matching M. Then |M| is
asked Sep 21, 2017 in Revision 77 views
0 votes
0 answers
10
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 75 views
0 votes
1 answer
11
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 71 views
0 votes
0 answers
12
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 61 views
1 vote
1 answer
13
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 226 views
0 votes
0 answers
14
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 155 views
...