DOCUMENTATION CENTER SEARCH
グラフユーティリティパッケージ >
Graph Utilities パッケージ シンボルチュートリアル »|関連項目 »|その他 »

MaximalBipartiteMatching

MaximalBipartiteMatching[g]
二部グラフ g の最大マッチングを返す．
  • MaximalBipartiteMatchingは二部グラフの2つの頂点集合間の非隣接辺の最大集合を与える．
  • m×n 行列により表される二部グラフは行頂点集合R={1, 2, ..., m}と列頂点集合C={1, 2, ..., n}で構成される．ここで行列要素が gij≠0ならば，頂点 iElementRと jElementCは連結される．
  • 規則のリスト{i1->j1, i2->j2, ...}で表される二部グラフは，頂点集合R=Union[{i1, i2, ...}]とC=Union[{j1, j2, ...}]で構成される．ここで規則 i->j が規則のリストに含まれるなら，頂点 iElementRと jElementCは連結される．
  • MaximalBipartiteMatchingは，ペアの数 k がどちらの頂点集合よりも小さくなる頂点ペアのリスト{{i1, j1}, ..., {ik, jk}}を返す．
例題すべて閉じる
例   (1)
Needs["GraphUtilities`"]
4人が飲むことのできる飲み物を記述した二部グラフ：
In[2]:=
Click for copyable input
2人が同じ飲み物を飲まないとした場合に，各人が飲むもの：
In[3]:=
Click for copyable input
Out[3]=
© 2008 Wolfram Research, Inc. japanese.gif
Ask a question about this page  |  Suggest an improvement  |  Leave a message for the team