2

与えられた無向グラフ。各頂点の次数が少なくとも p であるグラフの頂点の最大サブセットのサイズを見つける方法。サブセット内の次数は、サブセット内の頂点のみから検索されます。

4

1 に答える 1

1

p 未満の次数の頂点は、解の一部になることはできません。エッジを含めて完全に削除します。新しいグラフを見て、繰り返します。

このプロセスが停止すると、すべての頂点の次数は少なくとも p になります。

次に、そのグラフの連結成分を見て、最大のものを選びます! (Evgeny Kluev が正しく指摘しているように、これはもちろん不必要です。私の頭の中では、残りのサブグラフは接続されているはずですが、もちろん元の問題ではそのような要求はありません。)

于 2013-03-09T10:49:31.970 に答える