MaximalBipartiteMatching

バージョン10で,GraphUtilitiesパッケージの機能すべてがWolframシステムに組み込まれた. >>

MaximalBipartiteMatching[g]
二部グラフ g の最大マッチングを返す.

詳細詳細

  • MaximalBipartiteMatchingの機能はWolfram言語の組込み関数FindIndependentEdgeSetで利用できるようになった.
  • MaximalBipartiteMatchingを使うためには,まずグラフユーティリティパッケージをロードしなくてはならない.それにはNeeds["GraphUtilities`"]を実行する必要がある.
  • MaximalBipartiteMatchingは二部グラフの2つの頂点集合間の非隣接辺の最大集合を与える.
  • m×n 行列により表される二部グラフは行頂点集合R={1,2,,m}と列頂点集合C={1,2,,n}で構成される.ここで行列要素が gij0ならば,頂点 iRjCは連結されている.
  • 規則のリスト{i1->j1,i2->j2,}で表される二部グラフは,頂点集合R=Union[{i1,i2,}]C=Union[{j1,j2,}]で構成される.ここで規則 i->j が規則のリストに含まれるなら,頂点 iRjCは連結されている.
  • MaximalBipartiteMatchingは,ペアの数 k がどちらの頂点集合よりも小さくなる頂点ペアのリスト{{i1,j1},,{ik,jk}}を返す.

例題例題すべて開くすべて閉じる

  (2)  (2)

In[1]:=
Click for copyable input

4人が飲むことのできる飲み物を記述した二部グラフ:

In[2]:=
Click for copyable input

2人が同じ飲み物を飲まないとした場合に,各人が飲むもの:

In[3]:=
Click for copyable input
Out[3]=

MaximalBipartiteMatchingの代わりにFindIndependentEdgeSetが使われるようになった:

In[1]:=
Click for copyable input
In[2]:=
Click for copyable input
Out[2]=
In[3]:=
Click for copyable input
Out[3]=