2をもち、vを除くKn,Kmに含まれる点はそれぞれn-1,m-1の次数をもつ。mのとき、Knの点から順に切断され、最終的にKmだけ残りすべての頂点がm-1の次数をもつ。G[U]が2つの完全グラフ(Kn,Km)を含み、vを除くKn,Km上の点を結ぶ接続がある場合も、上記のケースでの切断する順序に変化があるだけで、同様に最大クリークを返す。G[U]が2つの完全グラフ(Kn,Km)を含み、vを除くKn,Km上の点にすべて接続がある場合、それは完全グラフKn+m-1であり、同様に最大クリークを返す。ありがとうございます。このケースだと現在の実装だと右側を消すとは限らないですね。vを含む極大クリークが返されるとしている部分が間違っていますね。修正してまた挑戦したいとおもいます。2016この状況を把握するのはおそらく無理、右側と左側にリンクがある場合もあるので、フローとかで優先順位を確定できない限り難しい。すると現在の実装でも、それなりに正しいものを出すかもしれないけど、コーナーケースのデータは否定できない。V.each前にsortするかbelongs_max_clique内のsortでabsを使用しているが、これを変えて、全体の順序のなかで順序付けして、整合性が取れるようにする。現在の状況で整合性がとれていることを示す必要がある。1かどうかで判定できるので、そうでない場合はスキップする。この場合も全体のなかで整合性が取れている必要がある。優先順位を変えて再度実施する。完全グラフかどうか頂点数と次数で判定して、正則グラフの場合は-1を返すようにしてみた。全体の整合性がとれるのかというと違う。右側と左側の別の頂点でbelong_max_cliqueは呼ばれるけど、全ての頂点がn-正則グラフと隣接しているというような状況はある。Vacation月別アーカイブはてなブログをはじめよう!tinsep19さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。