入力：頂点のリストと隣接リスト。Undirected Graphの最大サブセットを見つける
出力：良好な頂点の最大サブセット。
（それはそのサブセットに少なくとも2つの隣接する頂点と、少なくとも2の非隣接頂点を持っている場合我々は、「良好な頂点」とサブセット内の頂点を言う。）
例1：
Vertexes: [1, 2, 3, 4, 5]
Relations: [(1,2), (1,3), (3,4), (3,5), (4,5)]
output: []
例2：
output: [1,2,3,4,5,6]
出力の各頂点には、少なくとも2つの頂点が接続され、少なくとも2つの頂点が接続されていないためです。
少なくとも2つのネイバーと少なくとも2つの非ネイバーがグラフにある場合、「OK」という頂点を呼び出します。出力には頂点がある必要があります。
グラフからOKではない頂点をすべて削除します。これを行うと、以前は大丈夫だった頂点は、近隣または非隣接のものを使い果たしてしまうので、大丈夫です。これらの頂点も出力には存在しないので、他の頂点以外の頂点と同じように扱い、それらを削除することもできます。残っている頂点がすべて大丈夫になるまで続けてください。
残りの頂点のセットを出力します。
どのようにして頂点が正常でないかチェックしますか？頂点に少なくとも2つの非隣接があることを確認することはあまり効果的ではないが、複雑さは非常に高い。 –
@YanhuiZhou：非隣接ノードの数は、ノード自体の数をカウントしないため、ノードの数からノードの次数から1を引いた数です。 – user2357112
ありがとう、それは良い考えです。 –
隣人が2つ未満の頂点を削除します。
左の頂点の補完エッジ（リレーション）を構築します。補集合は、元の関係集合では同じ関係を持たないが、他の関係を有する。原点のリレーションセットと補数を組み合わせると、左の頂点との完全な関係であるリレーションセットになります。
補数の隣に2つより少ない頂点を削除します。結果の頂点が出力です。
ステップ1とステップ3の削除プロセスは再帰的プロセスです。誰も削除できなくなるまで、頂点を削除する必要があります。
[2,4,5]も大丈夫ですか？隣接する2つの頂点と隣接しない2つの頂点はどういう意味ですか？ –
@ YanhuiZhou申し訳ありませんが、例では、空のサブセットを返します。後で別のものを入れます。 – Deqing