此为 Mathematica 7 文档,内容基于更早版本的 Wolfram 语言
查看最新文档(版本11.2)

MaximalBipartiteMatching

MaximalBipartiteMatching[g]
gives the maximal matching of the bipartite graph g.
  • MaximalBipartiteMatching gives a maximal set of non-adjacent 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 iElementR and jElementC 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 iElementR and jElementC 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.
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]=