search
Log In

Recent questions tagged graph-matching

1 vote
1 answer
1
Your college has sent a contingent to take part in a cultural festival at a neighbouring institution. Several team events are part of the programme. Each event takes place through the day with many elimination rounds. Your contingent is multi-talented and each ... is: Find a maximum length simple cycle Find a maximum size independent set Find a maximum matching Find a maximal connected component
asked Sep 13, 2019 in Graph Theory gatecse 232 views
1 vote
0 answers
2
Let G be a graph with no isolated vertices, and let M be a maximum matching of G. For each vertex v not saturated by M, choose an edge incident to v. Let T be the set of all the chosen edges, and let L = M ∪ T. Which of the following option is TRUE? A L is always an edge cover of G. B L is always a minimum edge cover of G. C Both (A) and (B) D Neither (A) nor (B) Can anyone pls help solving this?
asked Jan 30, 2019 in Graph Theory Ashish Goyal 371 views
0 votes
1 answer
5
Consider the Bipartite graph shown. If four edges are chosen at random, what is the probability that they form a complete matching from V1 to V2 ? A. 0.039 B. 0.052 C. 0.071 D. 0.083
asked Oct 13, 2018 in Mathematical Logic Na462 684 views
1 vote
1 answer
6
Number of perfect matching in Wn (n>=4 and n is even) _________.
asked Jul 24, 2018 in Graph Theory abhishek1995_cse 257 views
0 votes
1 answer
7
Perfect matching is a set of edges such that each vertex appears only once and all vertices appear at least once (EXACTLY one appearance). So for n vertices perfect matching will have n/2 edges and there won't be any perfect matching if n is odd. I don't know whether i got it properly or not. Can please anybody explain the Perfect matching in a complete graph with simpler examples ?
asked Jun 10, 2018 in Graph Theory Na462 412 views
1 vote
1 answer
8
1 vote
2 answers
9
2 votes
1 answer
10
2 votes
0 answers
11
Let G be a planar Graph Such that every phase is bordered by exactly 3 edges which of the following can never be value for X(G) a)2 b)3 C)4 d)none of these
asked Nov 11, 2017 in Graph Theory Parshu gate 557 views
2 votes
2 answers
13
Consider a 'reversed Kruskal' Algorithm for computing a MST. Initialize T to be the set of all edges in the graph. Now consider edges from largest to smallest cost. For each edge, delete it from T if that edge belongs to a cycle in T. Assuming all the edge costs are distinct, does this new algorithm correctly compute a MST? a) Yes b) no c) cant say
asked Sep 14, 2017 in Graph Theory Rakshit Gupta 509 views
3 votes
3 answers
14
0 votes
1 answer
15
When matching number and covering number are same then can we say that it is a perfect matching case?Do i need to check the elements of the set( edges in both matching and covering) also if their cardinality is same?If yes,then can someone give me an example where matching number ... number same but still it is not a perfect match?I am not able to find such a case and i think it will not exist.
asked Jun 8, 2017 in Mathematical Logic rahul sharma 5 478 views
0 votes
1 answer
16
In a village there are equal no of boys and girls of marriageable age.Each boy dates a certain no. of girls and each girl dates a certain number of boys,under what condition is it possible that every girl and boy gets married to one of their dates?
asked Feb 27, 2017 in Graph Theory Learner_jai 280 views
2 votes
3 answers
17
Please explain how perfect matching in given tree is 1? Why not 3 with edges ab,ce,df?
asked Aug 10, 2016 in Mathematical Logic gaurav9822 341 views
6 votes
2 answers
19
Given explanation: In the above explanation, it is written that matching number is 4 but I am getting matching number as 3 for this graph(choosing edges 1-2, 3-4 and 6-7). Please check where I am going wrong
asked Jan 19, 2016 in Graph Theory shikharV 1.4k views
14 votes
2 answers
20
Is there a way to find no of perfect matchings in a complete graph Kn where n could be either even or odd..?
asked Dec 2, 2014 in Graph Theory dhingrak 6k views
50 votes
9 answers
21
How many perfect matching are there in a complete graph of $6$ vertices? $15$ $24$ $30$ $60$
asked Sep 16, 2014 in Graph Theory Kathleen 11.2k views
To see more, click for the full list of questions or popular tags.
...