この問題は、ハミルトニアン サイクル Hcycle(V,E) 関数を 1 回使用して、グラフ G にハミルトン パスが含まれているかどうかをテストします。この関数は、G にハミルトン サイクルが含まれているかどうかにかかわらず、true または false の出力を返します。
多項式の時間計算量を持つプログラムを作成する必要があります。このプログラムは、この問題に出力を与える必要がある 1 つのハミルトニアン サイクル関数を使用して、無向グラフ G に少なくとも 1 つのハミルトニアン パスが含まれているかどうかを判断する必要があります。
また、逆の問題を持つプログラムを作成する必要があります。(Hpath 関数を使用して、グラフに Hemiltonian Cycle が含まれているかどうかを調べます)。
この問題の解決策が見つかりません。Hcycle と Hpath の両方を一度しか使用できません。
関数 Hcycle と Hpath は線形時間計算量で実行されると仮定します。
すべてのハミルトニアン サイクルはハミルトニアン パスであり、どこかでサイクルを壊すだけです。
その逆はなかなかうまくいきません。強引な解決策は次のとおりです。すべてのハミルトニアン パス p について、p の開始と終了の間にエッジがあるかどうかを確認し、ある場合はサイクルを作成します。ただし、HPath一部のパスのみを返す場合、それからサイクルを作成する方法はありません(推測します)。
ウィキペディアをチェック
Hcycle(V,E) によるパス:他のすべての頂点に接続されている 1 つの頂点を追加することによって作成されたグラフで Hcycle() を呼び出します。新しいグラフにそのサイクルから新しいノードを削除するよりもサイクルがある場合、元のグラフのパスを取得します。
Cycle by Hpath(V,E): 1 つの頂点を追加し、それを 1 つの既存の頂点と同じ近傍に接続することによって作成されたグラフで Hpath() を呼び出します。これは、これら 2 つの頂点が同じ隣人を持つことを意味します。新しいグラフにパスがある場合、少なくとも 1 つのパスの端がこれら 2 つの頂点上にあります。他の頂点が終点でない場合は、パスの 3 番目の位置にあり、パスを並べ替えることで、両方の頂点をパスの終点に設定できます。これらの 2 つの頂点をマージすると (隣接する頂点が同じであるため)、元のグラフに循環が得られます。
Path by Hcycle(V,E):グラフにパスがあるよりもサイクルがある場合。v1接続されていない頂点の各ペア ( 、 )よりもグラフにサイクルがない場合はv2、それらの間にエッジを追加し、 でサイクルがあるかどうかを確認しHcycle(V,E+(v1,v2))ます。元のグラフにv1との間にパスがあるよりもサイクルがある場合。v2Hcycle は最大|V|^2時間と呼ばれます。
Cycle by Hpath(V,E):考えられるのは、パスが既知の頂点を持つように強制することです。これは、2 つの頂点の次数が 1 であるグラフを作成することで実行できます。N(v)の隣人としましょうv。エッジ(v1,v2)とn1fromN(v1)-v2およびn2fromの場合、 to を除く からすべてのエッジを削除し、to を除く からN(v2)-v1すべてのエッジを削除して、グラフを作成します。そのグラフにパスがある場合、その端はとであり、元のグラフには円があります。Hpath は max times と呼ばれます。v1n1v2n2v1v2|E|*|V|^2