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[{vw,},]
規則 を使ってグラフ g を指定する.

詳細詳細

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

予備知識
予備知識

  • FindCliqueは,頂点リストのリストとして返されたグラフ内の特定のサイズの最大クリーク集合を求める.ここでは,クリークは,対応する誘導された部分グラフが完全グラフであるような,頂点の部分集合である.クリークは,投影法の選択,パターンマッチング,金融,ネットワーク分析等に使用される.一般に,FindClique[g,nspec,s]は,グラフ g 内の指定されたサイズ nspecs 個の最大クリークの集合を求める.
  • クリークには,最大と極大という重要な2つのタイプがある.両者は等しくない点に注意が必要である.最大クリークは,指定されたグラフの可能な最大数の頂点を含むクリークである.極大クリーク集合は,隣接頂点を1つ余計に含むことで拡大することができないクリーク,つまりより大きいクリークの部分集合ではないクリークのことである.したがって,(すでに最大サイズであれば拡張できないことは明らかなので)最大クリークは常に極大であるのに対し,逆は必ずしも真ではない.用語をさらに混同させるように,最大クリークを単に「クリーク」とする者もある.
  • FindCliqueはさまざまなサイズの極大クリークを求めることができる.FindCliqueは指定されたサイズの単一の極大クリーク,指定された数のクリーク,あるいはそのようなクリークすべてを求めることもできる.
  • FindClique[g]は,グラフ g の単一の最大クリークを求め,FindClique[g,Length/@FindClique[g],s]は最大 s 個の,FindClique[g,{Length[FindClique[g][[1]]},All]は,そのようなクリークすべてを求める.グラフ g の最大クリークのサイズはそのクリーク数として知られており,指定されたグラフの最大クリークの大きさを求める問題はNP完全,つまり計算が指数的に遅くなることになる.
  • FindClique[g,Infinity]はグラフ g の単一の極大クリークを求め,FindClique[g,Infinity,s]は最大 s 個の,FindClique[g,Infinity,All]はそのようなクリークすべてを求める.極大クリークは,グラフの色分けや非整数グラフのの色分けを含むグラフ理論の応用において重要である.
  • 必ずしも極大ではないクリークはFindCliqueを使って直接求めることはできないが,すべての極大クリークのすべての部分集合の集合の和集合を取ることで単純化して列挙することができる.
  • グラフの(FindIndependentVertexSetで求めることができる)極大独立頂点集合は,そのGraphComplementの極大クリークに等しい.グラフ g の頂点の集合 vlist は,CompleteGraphQ[g,vlist]を使って(極大でもあるという条件なしに)クリークかどうかを調べることができる.FindKCliqueFindKClanFindKClubは,部分グラフ中で完全ではない連結を許すクリーク状の構造を求めることができる.
2010年に導入
(8.0)
| 2015年に修正
(10.3)
Translate this page: