MATHEMATICA 組込みシンボル

FindIndependentEdgeSet

FindIndependentEdgeSet[g]
グラフ g で辺の数が最大の独立辺集合を求める．

完全グラフ中の独立辺集合を求める：

有向グラフで求める：

完全グラフ中の独立辺集合を求める：

Out[1]=

Out[2]=

有向グラフで求める：

Out[1]=

Out[2]=

FindIndependentEdgeSetは無向グラフに使うことができる：

有向グラフ：

会社にはいくつもの仕事がある．各社員に適した仕事がある．どの社員も1度に1つの仕事しかできない：

同時に行われる仕事の数を最大化する：

ある女性の集団があると仮定する．それぞれの女性に好みの男性の部分集団がある．好みに合うマッチングだけを使った場合の最大マッチングを求める：

最大マッチングを計算する：

美術史学科で6つのコースが開設される．教授数は8人で，誰もがある特定のコースなら教えても構わないと言っている．どの教授も自分が興味を持つコースだけを教える最大マッチングを求める：

好みとコースをマッチさせる：

辺集合が独立辺集合かどうかIndependentEdgeSetQを使って調べる：

二部グラフには独立辺集合と同じ長さの頂点被覆がある：

孤立した頂点のないグラフの場合，独立辺集合のサイズと辺被覆のサイズの和は頂点数に等しい：