WOLFRAM

Wolfram Language & System Documentation Center

MaximalBipartiteMatching[g]

gives the maximal matching of the bipartite graph g.

Details and Options
Details and Options Details and Options
Examples  
Basic Examples  
Applications  
See Also
Tech Notes
Related Guides
Cite this Page
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 all close all

Basic Examples  (2)

Wolfram Language code: Needs["GraphUtilities`"]

A bipartite graph describing acceptable drinks for four people:

Wolfram Language code: g = {Tom -> Coke, Tom -> Coffee, Rob -> Coke, Rob -> Tea, Adam -> Tea, Adam -> Juice, Anton -> Juice};

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

Wolfram Language code: MaximalBipartiteMatching[g]

MaximalBipartiteMatching has been superseded by FindIndependentEdgeSet:

Wolfram Language code: g = Graph[{Tom -> Coke, Tom -> Coffee, Rob -> Coke, Rob -> Tea, Adam -> Tea, Adam -> Juice, Anton -> Juice}];
Wolfram Language code: FindIndependentEdgeSet[g]
Wolfram Language code: List@@@%

Applications  (1)

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

Wolfram Language code: Needs["GraphUtilities`"]
Wolfram Language code: m = SparseArray[Floor[RandomReal[{0, 1} + .04, {30, 40}]]]
Wolfram Language code: MatrixPlot[m]

This finds rows and columns that are matched:

Wolfram Language code: matched = MaximalBipartiteMatching[m]
Wolfram Language code: r = matched[[All, 1]]
Wolfram Language code: c = matched[[All, 2]]

This finds unmatched rows and columns:

Wolfram Language code: r2 = Complement[Range[Dimensions[m][[1]]], r]; c2 = Complement[Range[Dimensions[m][[2]]], c];

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

Wolfram Language code: MatrixPlot[m[[Join[r, r2], Join[c, c2]]]]
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_2026_maximalbipartitematching, author="Wolfram Research", title="{MaximalBipartiteMatching}", year="2007", howpublished="\url{https://reference.wolfram.com/language/GraphUtilities/ref/MaximalBipartiteMatching.html}", note=[Accessed: 13-June-2026]}

BibLaTeX

@online{reference.wolfram_2026_maximalbipartitematching, organization={Wolfram Research}, title={MaximalBipartiteMatching}, year={2007}, url={https://reference.wolfram.com/language/GraphUtilities/ref/MaximalBipartiteMatching.html}, note=[Accessed: 13-June-2026]}