ノート:最小頂点被覆問題

このページのタイトルは「頂点被覆問題」でしたが、内容は「最小頂点被覆問題」の説明だったので移動させてもらいました、最小頂点被覆問題という単語が頂点被覆問題のリダイレクトになっていたので、おそらく頂点被覆問題と最小頂点被覆問題の違いを知らない方が作ったのではないかと思われます。

両者の違いは、

頂点被覆問題

グラフ G(V,E) の各枝 e について端点のいずれか少なくとも一方が、V' に含まれるような V の部分集合 V' のうち、|V'| = k となるものが存在するかを求めよ。

最小頂点被覆問題

グラフ G(V,E) の各枝 e について端点のいずれか少なくとも一方が、V' に含まれるような V の部分集合 V' のうち、|V'|が最小になるものを求めよ。

です。

--U-ichi 2006年8月3日 (木) 05:29 (UTC)

とりあえず、頂点被覆問題のページは新たに作っておきました、こちらでコメントアウトした箇所も含めて載せています。　--U-ichi 2006年8月3日 (木) 05:48 (UTC)