GraphUtilities`
GraphUtilities`

MaximalBipartiteMatching

As of Version 10, all the functionality of the GraphUtilities package is built into the Wolfram System. »

MaximalBipartiteMatching[g]

gives the maximal matching of the bipartite graph g.

Details and Options

  • MaximalBipartiteMatching functionality is now available in the built-in Wolfram Language function FindIndependentEdgeSet.
  • To use MaximalBipartiteMatching, you first need to load the Graph Utilities Package using Needs["GraphUtilities`"].
  • MaximalBipartiteMatching gives a maximal set of nonadjacent edges between the two vertex sets of the bipartite graph.
  • The bipartite graph represented by an m×n matrix consists of the row and column vertex sets R={1,2,…,m} and C={1,2,…,n}, with a vertex i∈R and j∈C connected if the matrix element gij≠0.
  • The bipartite graph represented by a rule list {i1->j1,i2->j2,…} consists of vertex sets R=Union[{i1,i2,…}] and C=Union[{j1,j2,…}], with a vertex i∈R and j∈C connected if the rule i->j is included in the rule list.
  • MaximalBipartiteMatching returns a list of index pairs {{i1,j1},…,{ik,jk}}, where the number of pairs k is not larger than either vertex set.

Examples

open allclose all

Basic Examples  (2)

A bipartite graph describing acceptable drinks for four people:

The drink each person should have, if no two people are to have the same drink:

MaximalBipartiteMatching has been superseded by FindIndependentEdgeSet:

Applications  (1)

This defines a random 30×40 sparse matrix with approximately 4% of the elements nonzero:

This finds rows and columns that are matched:

This finds unmatched rows and columns:

This orders the matrix by permuting matched rows and columns to the principal diagonal block first:

Wolfram Research (2007), MaximalBipartiteMatching, Wolfram Language function, https://reference.wolfram.com/language/GraphUtilities/ref/MaximalBipartiteMatching.html.

Text

Wolfram Research (2007), MaximalBipartiteMatching, Wolfram Language function, https://reference.wolfram.com/language/GraphUtilities/ref/MaximalBipartiteMatching.html.

CMS

Wolfram Language. 2007. "MaximalBipartiteMatching." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/GraphUtilities/ref/MaximalBipartiteMatching.html.

APA

Wolfram Language. (2007). MaximalBipartiteMatching. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/GraphUtilities/ref/MaximalBipartiteMatching.html

BibTeX

@misc{reference.wolfram_2024_maximalbipartitematching, author="Wolfram Research", title="{MaximalBipartiteMatching}", year="2007", howpublished="\url{https://reference.wolfram.com/language/GraphUtilities/ref/MaximalBipartiteMatching.html}", note=[Accessed: 21-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_maximalbipartitematching, organization={Wolfram Research}, title={MaximalBipartiteMatching}, year={2007}, url={https://reference.wolfram.com/language/GraphUtilities/ref/MaximalBipartiteMatching.html}, note=[Accessed: 21-November-2024 ]}