WOLFRAM

Wolfram言語 ＆ システムドキュメントセンター

MaximalBipartiteMatching[g]

二部グラフ g の最大マッチングを返す．

詳細とオプション
Details and Options Details and Options
例題  
例  
アプリケーション  
関連項目
テクニカルノート
関連するガイド
引用書式
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}で構成される．ここで行列要素が gij≠0ならば，頂点 i∈Rと j∈Cは連結されている．
  • 規則のリスト{i1->j1,i2->j2,…}で表される二部グラフは，頂点集合R=Union[{i1,i2,…}]とC=Union[{j1,j2,…}]で構成される．ここで規則 i->j が規則のリストに含まれるなら，頂点 i∈Rと j∈Cは連結されている．
  • MaximalBipartiteMatchingは，ペアの数 k がどちらの頂点集合よりも小さくなる頂点ペアのリスト{{i1,j1},…,{ik,jk}}を返す．

例題

すべて開く すべて閉じる

例  (2)

Wolfram Language code: Needs["GraphUtilities`"]

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

Wolfram Language code: g = {Tom -> Coke, Tom -> Coffee, Rob -> Coke, Rob -> Tea, Adam -> Tea, Adam -> Juice, Anton -> Juice};

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

Wolfram Language code: MaximalBipartiteMatching[g]

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

Wolfram Language code: g = Graph[{Tom -> Coke, Tom -> Coffee, Rob -> Coke, Rob -> Tea, Adam -> Tea, Adam -> Juice, Anton -> Juice}];
Wolfram Language code: FindIndependentEdgeSet[g]
Wolfram Language code: List@@@%

アプリケーション  (1)

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

Wolfram Language code: Needs["GraphUtilities`"]
Wolfram Language code: m = SparseArray[Floor[RandomReal[{0, 1} + .04, {30, 40}]]]
Wolfram Language code: MatrixPlot[m]

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

Wolfram Language code: matched = MaximalBipartiteMatching[m]
Wolfram Language code: r = matched[[All, 1]]
Wolfram Language code: c = matched[[All, 2]]

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

Wolfram Language code: r2 = Complement[Range[Dimensions[m][[1]]], r]; c2 = Complement[Range[Dimensions[m][[2]]], c];

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

Wolfram Language code: MatrixPlot[m[[Join[r, r2], Join[c, c2]]]]
Wolfram Research (2007), MaximalBipartiteMatching, Wolfram言語関数， https://reference.wolfram.com/language/GraphUtilities/ref/MaximalBipartiteMatching.html.

テキスト

Wolfram Research (2007), MaximalBipartiteMatching, Wolfram言語関数， https://reference.wolfram.com/language/GraphUtilities/ref/MaximalBipartiteMatching.html.

CMS

Wolfram Language. 2007. "MaximalBipartiteMatching." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/GraphUtilities/ref/MaximalBipartiteMatching.html.

APA

Wolfram Language. (2007). MaximalBipartiteMatching. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/GraphUtilities/ref/MaximalBipartiteMatching.html

BibTeX

@misc{reference.wolfram_2026_maximalbipartitematching, author="Wolfram Research", title="{MaximalBipartiteMatching}", year="2007", howpublished="\url{https://reference.wolfram.com/language/GraphUtilities/ref/MaximalBipartiteMatching.html}", note=[Accessed: 12-August-2026]}

BibLaTeX

@online{reference.wolfram_2026_maximalbipartitematching, organization={Wolfram Research}, title={MaximalBipartiteMatching}, year={2007}, url={https://reference.wolfram.com/language/GraphUtilities/ref/MaximalBipartiteMatching.html}, note=[Accessed: 12-August-2026]}