FindIndependentEdgeSet

FindIndependentEdgeSet[g]

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

FindIndependentEdgeSet[{vw,…}]

規則 vw を使ってグラフ g を指定する．

詳細とオプション

  • 独立辺集合はマッチングとも呼ばれる．
  • 独立辺集合とは決して同じ頂点に接続しない辺集合のことである．
  • FindIndependentEdgeSetは辺のリストを返す．
  • FindIndependentEdgeSetは，無向グラフ，有向グラフ，重み付きグラフ，多重グラフに使うことができる．

例題

すべて開くすべて閉じる

例  (1)

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

辺集合を示す：

スコープ  (6)

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

有向グラフ：

重み付きグラフ：

多重グラフ：

規則を使ってグラフを指定する：

FindIndependentEdgeSetは大きいグラフに使うことができる：

アプリケーション  (3)

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

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

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

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

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

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

特性と関係  (3)

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

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

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

Wolfram Research (2010), FindIndependentEdgeSet, Wolfram言語関数， https://reference.wolfram.com/language/ref/FindIndependentEdgeSet.html （2015年に更新）.

テキスト

Wolfram Research (2010), FindIndependentEdgeSet, Wolfram言語関数， https://reference.wolfram.com/language/ref/FindIndependentEdgeSet.html （2015年に更新）.

CMS

Wolfram Language. 2010. "FindIndependentEdgeSet." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/FindIndependentEdgeSet.html.

APA

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

BibTeX

@misc{reference.wolfram_2024_findindependentedgeset, author="Wolfram Research", title="{FindIndependentEdgeSet}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindIndependentEdgeSet.html}", note=[Accessed: 18-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_findindependentedgeset, organization={Wolfram Research}, title={FindIndependentEdgeSet}, year={2015}, url={https://reference.wolfram.com/language/ref/FindIndependentEdgeSet.html}, note=[Accessed: 18-November-2024 ]}