Mathematica 9 is now available
THIS IS DOCUMENTATION FOR AN OBSOLETE PRODUCT.
SEE THE DOCUMENTATION CENTER FOR THE LATEST INFORMATION.
Wolfram Mathematica Documentation Center
DOCUMENTATION CENTER SEARCH
New to Mathematica? Find your learning path »
Graph Utilities Package >
GRAPH UTILITIES PACKAGE SYMBOLTutorials »|See Also »|More About »

MaximalBipartiteMatching

MaximalBipartiteMatching[g]
gives the maximal matching of the bipartite graph g.
MORE INFORMATION
  • gives a maximal set of non-adjacent edges between the two vertex sets of the bipartite graph.
  • The bipartite graph represented by an matrix consists of the row and column vertex sets and C, with a vertex iR and jC connected if the matrix element .
  • The bipartite graph represented by a rule list consists of vertex sets R=Union[{i1, i2, ...}] and C=Union[{j1, j2, ...}], with a vertex iR and jC connected if the rule is included in the rule list.
  • returns a list of index pairs where the number of pairs k is not larger than either vertex set.
EXAMPLESCLOSE ALL
Basic Examples   (1)
A bipartite graph describing acceptable drinks for 4 people:
The drink each person should have, if no two people are to have the same drink:
Needs["GraphUtilities`"]
A bipartite graph describing acceptable drinks for 4 people:
In[2]:=
Click for copyable input
The drink each person should have, if no two people are to have the same drink:
In[3]:=
Click for copyable input
Out[3]=
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:
Ask a question about this page  |  Suggest an improvement  |  Leave a message for the team
Format:   HTML  |  CDF