MaximalBipartiteMatching[g]
gives the maximal matching of the bipartite graph g.


MaximalBipartiteMatching
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 all close allBasic 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:
Tech Notes
Related Guides
-
▪
- Graph Utilities Package ▪
- Graphs & Networks ▪
- Graph Visualization ▪
- Computation on Graphs ▪
- Graph Construction & Representation ▪
- Graphs and Matrices ▪
- Graph Properties & Measurements ▪
- Graph Operations and Modifications ▪
- Statistical Analysis ▪
- Social Network Analysis ▪
- Graph Properties ▪
- Mathematical Data Formats ▪
- Discrete Mathematics
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_2025_maximalbipartitematching, author="Wolfram Research", title="{MaximalBipartiteMatching}", year="2007", howpublished="\url{https://reference.wolfram.com/language/GraphUtilities/ref/MaximalBipartiteMatching.html}", note=[Accessed: 25-August-2025]}
BibLaTeX
@online{reference.wolfram_2025_maximalbipartitematching, organization={Wolfram Research}, title={MaximalBipartiteMatching}, year={2007}, url={https://reference.wolfram.com/language/GraphUtilities/ref/MaximalBipartiteMatching.html}, note=[Accessed: 25-August-2025]}