0 votes 0 votes 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 Mathematical Logic graph-matching graph-theory discrete-mathematics + – Na462 asked Oct 13, 2018 Na462 1.7k views answer comment Share Follow See 1 comment See all 1 1 comment reply Na462 commented Oct 13, 2018 reply Follow Share What is complete matching is it Perfect matching. Please explain the terms as well :) 0 votes 0 votes Please log in or register to add a comment.
Best answer 2 votes 2 votes 5 complete matchings are possible! for C we have to fix T otherwise we won't get a complete matching. For( A,B,D) following 5 matchings are possible: (P,S,Q) (P,S,R) (Q P,R) (Q,P,S) (Q,S,R). Hence P= 5/ 8C4= 5/70=0.071 Utkarsh Joshi answered Oct 13, 2018 selected Oct 18, 2018 by Na462 Utkarsh Joshi comment Share Follow See all 5 Comments See all 5 5 Comments reply Sweta Shaw commented Dec 3, 2018 reply Follow Share Is Complete Matching , other name of perfect matching? 0 votes 0 votes rahulgargnov4 commented Jan 18, 2019 reply Follow Share In this graph their are odd number of vertices, how can we have complete matching in this in Question when we can not select all the vertices. 1 votes 1 votes mohan123 commented Sep 9, 2019 reply Follow Share @Bikram 0 votes 0 votes Bikram commented Sep 10, 2019 reply Follow Share https://courses.cit.cornell.edu/info204_2007sp/matching.pdf https://gateoverflow.in/926/gate2003-36 1 votes 1 votes Bikram commented Sep 10, 2019 reply Follow Share https://mathoverflow.net/questions/279690/graph-to-bipartite-conversion-preserving-number-of-perfect-matchings https://www.whitman.edu/mathematics/cgt_online/book/section04.05.html 1 votes 1 votes Please log in or register to add a comment.