高温処理済みコースケスマートフォン用の表示で見る高温処理済みコースケ2016-11-30最大クリーク問題まだうまく証明できていないかもしれないけど、これで解けてると思う解けていないです。別の実装を考えたのでコードを消しました。kousuke.hatenablog.combelongs_max_cliqueではある頂点を含む極大クリークのサイズを返していて、それを全点に対して行いその最大のものを出力している。belongs_max_cliqueは任意の1頂点(v)とそれに隣接する頂点集合をUとすると、誘導部分グラフG[U]に対し、その次数をまず計算する。Uの次数の少ないものから、順に切断していくと最終的に他の全ての点と同じ次数になるので、その時残っているグラフがvを含む最大クリークとなる。(証明)最大クリークはそのグラフの頂点のどれかを含んでいる(自明)ある頂点を選んでその頂点を含む極大クリークがわかれば、それを全点でおこなうことで最大クリークがわかる。(問題ないとおもう)G[U]はvとvに隣接する頂点集合からなる誘導部分グラフであるので、vを含むクリークはすべて含まれる。(多分、自明)G[U]はvとvに隣接する頂点集合からなる誘導部分グラフであるので、vの次数は必ず他の頂点の次数以上である。(Uの頂点数がnならG[U]の頂点の次数はn-1より大きくなることはなく、vの次数はn-1)G[U]が完全グラフ(Kn)のとき、その全ての頂点の次数はn-1となり、頂点数はnとなり、停止条件となる。(n-正則グラフの場合があり、判定できてない)G[U]からvの次数未満の最小の次数をもつ頂点を1点切断した頂点集合をU'とするとG[U']も必ずvを含む極大クリークが含まれる。(問題あり)U'をUとして5に戻っても矛盾はない。(問題ないとおもう)以上より、このアルゴリズムは停止条件をもち、有限時間内に停止する。その時、このグラフに含まれる極大クリークのうち、最大のサイズを示す。