Enable JavaScript to interact with content and submit forms on Wolfram websites. Learn how

Wolfram Language & System Documentation Center

MaximalBipartiteMatching

GraphUtilities`

GraphUtilities`

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}で構成される．ここで行列要素が g_ij≠0ならば，頂点 i∈Rと j∈Cは連結されている．
規則のリスト{i₁->j₁,i₂->j₂,…}で表される二部グラフは，頂点集合R=Union[{i₁,i₂,…}]とC=Union[{j₁,j₂,…}]で構成される．ここで規則 i->j が規則のリストに含まれるなら，頂点 i∈Rと j∈Cは連結されている．
MaximalBipartiteMatchingは，ペアの数 k がどちらの頂点集合よりも小さくなる頂点ペアのリスト{{i₁,j₁},…,{i_k,j_k}}を返す．

例題

すべて開くすべて閉じる

例 (2)

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

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

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

アプリケーション (1)

以下で，要素のほぼ4%が非零であるような乱数の30×40疎行列を定義する：

マッチする行と列を見付ける：

マッチしない行と列を見付ける：

マッチする行と列を最初に主対角ブロックに置換することで，行列に順序を付ける：

Top