>>224
ハミルトン路問題とハミルトン閉路問題の変換は容易．
以下 G = (V, E) を固定する．

ハミルトン路問題をハミルトン閉路問題に帰着する：

新しい頂点 s を G に追加し，二頂点 u, v ∈ V を取って
辺 (u,s) と (s,v) を張る．G ∪ {s} にハミルトン閉路があれば
G に u-v 間を繋ぐハミルトン路がある．これを任意の u, v
について行えば， G にハミルトン路があるかどうか判定できる．


ハミルトン閉路をハミルトン路に帰着する：

新しい頂点 s, t を G に追加し，隣接する二頂点 u, v ∈ V を取って
辺 (s,u) と (v,t) を張る．G ∪ {s,t} にハミルトン路があれば
それは s を始点にし，t を終点にするものに限る．この路を用いると
u から出て v に行き，u に戻るようなハミルトン閉路が構成できる．
これを任意の u, v について行えば，ハミルトン閉路があるかどうか判定できる．


どっちの構成も図を描けばやりたいことは分かるとおもう．