入力: 頂点のリストと隣接リスト。
出力: 適切な頂点の最大サブセット。
(そのサブセット内に少なくとも 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」と呼びます。頂点は、出力に含まれるのに問題がない必要があります。
グラフからすべての不適切な頂点を削除します。これを行うと、以前は正常だった頂点が、隣接または隣接していない頂点を使い果たすと、正常でなくなる可能性があります。これらの頂点も出力に含めることができないため、他の正常でない頂点と同様に扱い、それらも削除します。残りのすべての頂点が正常になるまで続けます。
残りの頂点のセットを出力します。
隣接する頂点が 2 つ未満の頂点を削除します。
左の頂点の補辺 (関係) を構築します。補集合は元の関係セットに同じ関係を持っていませんが、他の関係があります。原点リレーション セットを補数と組み合わせると、左側の頂点との完全なリレーションであるリレーション セットになります。
補数の隣接点が 2 つ未満の頂点を削除します。結果の頂点が出力です。
ステップ 1 とステップ 3 の削除プロセスは、再帰プロセスです。誰も削除できなくなるまで、頂点を削除する必要があります。