エッジがなくなるまで頂点を削除します
Aug 16 2020
無向グラフG(V、E)が与えられた場合、グラフのエッジセットが空になるように、削除する頂点の最小数を見つけます。
つまり、1つの頂点を削除すると、その頂点に接続されているすべてのエッジとともにその頂点が削除されます。削除する頂点の最小数を見つけて、削除後にGにエッジが残らないようにします。
回答
3 PålGD Aug 17 2020 at 14:20
自分で答えを見つけたようです。頂点被覆を説明しています。頂点被覆は多くの点で独立集合に非常に似ており、どちらの問題もNP完全です。
独立集合との関係はグラフのそれです $G = (V,E)$、 セット $S$ 最小の頂点被覆であるのは、 $V \setminus S$ 最大の独立集合です。
独立集合がNP完全であることがわかっている場合は、頂点被覆もNP完全であるということになります。
言い換えれば、あなたは最大の独立集合も探しています。
頂点被覆。与えられたグラフ$G = (V,E)$ と整数 $k$、セットはありますか $S \subseteq V$ せいぜいサイズの $k$ のすべてのエッジが $G$ の頂点に入射します $S$?
独立集合。与えられたグラフ$G = (V,E)$ と整数 $k$、セットはありますか $S \subseteq V$ 少なくともサイズの $k$その結果、誘発グラフ $G[S]$ エッジがありませんか?