私は試験の準備をしており、アルゴリズム コースでは NP の完全性をカバーする必要がありましたが、それらの実際のチュートリアルはなく、試験の「練習問題」の山が与えられました。私は最後を除いてすべてに取り組みましたが、それを解決する方法が本当にわかりません（これまでにインターネットに尋ねると、私が理解できない公開された論文が返されました）。
前の 2 つの質問は、ハミルトン パス問題がクラス NP にあることを示しており、ハミルトン サイクル問題がそれに帰着することを示すことによって、それが NP 完全であることを示していました。
これは、私が前進できないように見える3番目の質問につながります。
グラフの次数制約スパニング ツリーは、一定の k に対して最大次数 k のスパニング ツリーです (ツリーの各頂点は、最大で k 個のエッジに隣接します)。グラフ G に次数が k = 2 で制約されたスパニング ツリーが含まれているかどうかを判断するのがハミルトニアン パス問題です。これは、先ほど示した NP 完全問題です。一般的な k に対して、次数が k で制約される全域木がグラフ G に含まれているかどうかを判断することも NP 完全問題であることを示します。
これに答える私の現在の試みは、次のようなものです。
k = 2 の場合、任意の頂点 V について、頂点 V のみを共有し、ハミルトニアン パスに対して true を返す 2 つの異なるサブグラフにグラフを分割できます。つまり、k=3 の場合、頂点 V があり、グラフをすべてハミルトニアン パスを持つ 3 つの異なるサブグラフに分割できます。
これが正しくないことはわかっていますが、正しい道に沿っていると感じていますが、最終目標に到達する方法がまったくわかりません。どんな助けでも大歓迎です。