FindClique

FindClique[g]
グラフ g 中の最大クリークを求める.

FindClique[g,n]
最高で n 個の頂点を持つクリークを求める.

FindClique[g,{n}]
厳密に n 個の頂点を持つクリークを求める.

FindClique[g,{nmin,nmax}]
から までの頂点を持つクリークを求める.

FindClique[g,nspec,s]
最高で s 個のクリークを求める.

FindClique[{g,v},]
頂点 v のみを含むクリークを求める.

詳細詳細

  • クリークとは対応する部分グラフが完全グラフとなる極大頂点集合である.
  • FindCliqueはクリークのリストを返す.
  • クリークが見付からなかった場合,FindCliqueは空のリストを返す.
  • FindClique[,nspec,All]はすべてのクリークを求める.
  • 重み付きグラフの場合,FindCliqueは頂点重みの和が最大になる頂点集合を与える.
  • FindCliqueは,無向グラフ,有向グラフ,重み付きグラフ,多重グラフ,混合グラフに使うことができる.

予備知識
予備知識

  • FindCliqueは,頂点リストのリストとして返されたグラフ内の特定のサイズのクリーク集合を求める.ここでは,クリークは,対応する誘導された部分グラフが完全グラフであるような,頂点の部分集合である.クリークは,投影法の選択,パターンマッチング,金融,ネットワーク分析等に使用される.一般に,FindClique[g,nspec,s]は,グラフ g 内の指定されたサイズ nspecs 個のクリークの集合を求める.
  • FindClique[g]は,単一の最大クリーク(つまり,可能な限り最大サイズのクリーク)を求め,FindClique[g,{Length[FindClique[g][[1]]},All]は,すべての最大クリークを求める.(最大クリークが単にクリークと呼ばれる場合があるので,注意のこと.)最大クリークのサイズはグラフのクリーク数として知られており,指定されたグラフの最大クリークの大きさを求める問題はNP完全になる.
  • 同様に,FindClique[g,Infinity]は単一の極大クリークを求め,FindClique[g,Infinity,All]はそのようなクリークすべてを求める.ここで,極大クリークとは(極大クリークと最大クリークは同一ではない点に注意)隣接頂点をもう一つ加えることで拡大することはできないクリーク,つまり,より大きいクリークの部分集合ではないものである.最大クリーク(つまり,指定されたグラフ中の最大クリーク)は,常に極大であるが,逆は必ずしも真ではない. 極大クリークは,グラフおよび非整数グラフのの色分けを含むグラフ理論の応用において重要である.
  • FindIndependentVertexSetで求めることができるグラフの独立極大頂点集合は,そのGraphComplementの極大クリークに等しい.FindKCliqueFindKClanFindKClubは,部分グラフ中で完全ではない連結を許すクリーク状の構造を求めることができる.
2010年に導入
(8.0)
| 2014年に修正
(10.0)