グラフ理論の問題を出し合うスレ

[0050 名無しさん＠お腹いっぱい。 2008/07/24(木) 18:58:47 ID:v/qcIfE90]

ハミルトン路が1個で頂点被覆できるかという問題がNP困難らしいから、
最少のハミルトン路で頂点被覆するという問題もNP困難だろう。
近似解でいいのか？