FindIndependentVertexSet

FindIndependentVertexSet[g]

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

FindIndependentVertexSet[g,n]

最高で n 個の頂点を持つ独立頂点集合を求める．

FindIndependentVertexSet[g,{n}]

厳密に n 個の頂点を持つ独立頂点集合を求める．

FindIndependentVertexSet[g,{nmin,nmax}]

nmin個から nmax個までの頂点を持つ独立頂点集合を求める．

FindIndependentVertexSet[g,nspec,s]

最高で s 個の独立頂点集合を求める．

FindIndependentVertexSet[{g,v},…]

頂点 v のみを含む独立集合を求める．

FindIndependentVertexSet[{vw,…},…]

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

詳細

  • 独立頂点集合は同じ辺には決して接続しない頂点の最大集合である．
  • FindIndependentVertexSetは頂点のリストを返す．
  • 独立頂点集合が存在しない場合，FindIndependentVertexSetは空リストを返す．
  • FindIndependentVertexSet[…,nspec,All]は，すべての独立頂点集合を求める．
  • 重み付きグラフの場合，FindIndependentVertexSetは，頂点重みの合計が最高になる頂点集合を与える．
  • FindIndependentVertexSetは，無向グラフ，有向グラフ，重み付きグラフ，多重グラフ，混合グラフに使うことができる．

予備知識

  • FindIndependentVertexSetは，グラフ中の1つあるいは複数の極大独立頂点集合を求め，それらを頂点リストのリストとして返す．ここで，独立頂点集合は集合中のどの頂点ペアも辺で結ばれていないような頂点集合である．独立頂点集合は，金融，符号化理論，地図のラベル付け，パターン認識，ソーシャルネットワーク，分子生物学，スケジューリング等に応用される．
  • 独立頂点集合には，最大と極大の特に重要な2つのタイプがある．これらは等価ではない点に注意のこと．最大独立頂点集合は，指定されたグラフの可能な最大数の頂点を含む頂点集合のことである．これに対し，極大独立頂点集合は，もう1つの隣接頂点を含むことで拡張することができない，つまり，より大きい独立頂点集合の部分集合ではない独立頂点集合のことである．最大独立頂点集合は，したがって，常に極大であるが，逆は必ずしも真ではない．
  • FindIndependentVertexSetは，異なるサイズの極大独立頂点集合を求めることができる．FindIndependentVertexSetは，指定されたサイズの単一の極大独立頂点集合，指定された数の極大独立頂点集合，あるいはそのようなすべての集合も求めることができる．
  • FindIndependentVertexSet[g]は，グラフ g の単一の最大独立頂点集合を，FindIndependentVertexSet[g,Length/@FindIndependentVertexSet[g],s]は最高で s 個の，FindIndependentVertexSet[g,Length/@FindIndependentVertexSet[g],All]はそのようなすべての集合を求める．グラフ g の最大独立頂点集合の大きさは，その（頂点）独立数として知られている．指定されたグラフの最大独立頂点集合（したがって独立数）を求める問題は，NP完全である．つまり，計算が指数的に遅くなる．
  • FindIndependentVertexSet[g,Infinity]は，グラフ g の単一の極大独立頂点集合を求め，FindIndependentVertexSet[g,Infinity,s]は最高で s 個，FindIndependentVertexSet[g,Infinity,All]はそのような集合をすべて求める．
  • 必ずしも最大ではない独立頂点集合は，FindIndependentVertexSetを使って直接求めることはできないが，すべての最大独立頂点集合の部分集合の集合の和集合を取ることで，単純化して列挙することができる．
  • IndependentVertexSetQを使い，頂点集合が独立かどうかを（それが極大であるという条件なしに）調べることができる．独立頂点集合は，頂点被覆（FindVertexCoverを参照のこと）の補集合に対応する．グラフの極大頂点集合は，GraphComplement上の極大クリークに等しい（FindCliqueを参照のこと）．FindIndependentEdgeSetはFindIndependentVertexSetと同じ概念を辺に適用する．結果の独立辺集合もまた「マッチング」として知られている．

例題

すべて開くすべて閉じる

例  (2)

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

頂点集合を示す：

すべての独立集合を求める：

スコープ  (14)

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

有向グラフ：

重み付きグラフ：

多重グラフ：

混合グラフ：

最大の独立頂点集合を求める：

厳密に3個の頂点を含む独立頂点集合：

最高で2個の頂点を含む独立頂点集合：

3個から5個までの頂点を含む独立頂点集合：

指定された頂点を含む最大の独立頂点集合：

グラフ中のすべての独立頂点集合を求める：

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

独立頂点集合が存在しない場合，FindIndependentVertexSetは空リストを返す：

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

アプリケーション  (3)

グラフ中のすべての独立頂点集合をハイライトする：

フランチャイズ店のサービスネットワークで，頂点は店舗の位置を表し，2つの店舗が近過ぎて互いの売上げに影響が出る場合は頂点が連結されている．NorthPointに店舗があるとして，新たな店舗の候補地を求める：

新たな店舗の候補地：

利益があまり相関していないダウ・ジョーンズ工業株平均の成員を求める：

まず，年頭からの利益相関を計算する：

相関係数が選択した theta より上の株の間に辺を引いたグラフを作成する：

高度な相関関係がない株式の最大群：

特性と関係  (4)

頂点集合が独立頂点集合かどうかIndependentVertexSetQを使って調べる：

独立頂点集合の補集合は頂点被覆である：

独立頂点集合によって与えられた補集合の部分グラフは完全グラフである：

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

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

テキスト

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

CMS

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

APA

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

BibTeX

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

BibLaTeX

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