The Gateway to Computer Science Excellence
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

in Mathematical Logic by Loyal (7k points) | 190 views
What is complete matching is it Perfect matching. Please explain the terms as well :)

1 Answer

+2 votes
Best answer
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
by Loyal (7.8k points)
selected by
Is Complete Matching , other name of perfect matching?
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.
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
50,737 questions
57,382 answers
105,323 users