In a bipartite graph, how can we find the total number of ways of getting a maximal matching?

The cardinality of both the sets in the bipartite graph may not be the same. So two matchings are said to be different if they have at least one distinct edge.


closed as unclear what you're asking by D.W., David Richerby, Luke Mathieson, lPlant, Juho Aug 18 '14 at 13:40

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ @Raphael - I think this question should be unmarked as duplicate. The question you've referred to has been recently put on hold as unclear, and it looks like its frustrated author has closed his/her account. Additionally, a similar question has been asked on SO recently, and I have given my answer, but this question has been put on hold as well. It looks like a war against the question! But actually it's a valid combinatorial question in case of complete bigraphs, and also a valid algorithmic question in case of general bigraphs. $\endgroup$ – HEKTO Aug 3 '14 at 17:19
  • $\begingroup$ @HEKTO I think this here question would be closed as unclear for the same reasons as the duplicate. The OP can improve their question at any time. $\endgroup$ – Raphael Aug 3 '14 at 17:23
  • $\begingroup$ @Raphael - The question is formulated in such a way that it's evident the terminology is new to its author - but CS professionals can extract its real meaning, do they? $\endgroup$ – HEKTO Aug 3 '14 at 17:31
  • 1
    $\begingroup$ Your question may or may not be the same as that earlier one… Both questions are unclear. They're clearly about the same topic — the number of maximal matchings in a bipartite graph — but what is your question on this topic? Have you read Wikipedia? $\endgroup$ – Gilles Aug 3 '14 at 23:15
  • 1
    $\begingroup$ What research have you done? Where have you looked? What have you found so far on this topic? On this site, we expect you to make a significant effort on your own before asking, and to tell us in the question what you've tried. (Cc: @HEKTO.) $\endgroup$ – D.W. Aug 14 '14 at 20:48