巡回セールスマン問題では、任意の２つのノード間を移動して良い。（数学では「完全グラフ」と言います。）ですから、「最短経路」という条件が無ければ、とにかくこれまで通っていないノードをどれでも良いから通り、最後に出発点に戻ればハミルトン閉路になります。アホみたいに簡単。
ご質問の問題では、ノード間で移動できるものが限られている。これが制約なので、全然性質の違う問題です。
さて、回答。
文字数をnとします。n=2とn=3の時はちょっと例外的な扱いになります。
●n=2:ab
abの２文字からなる場合を考えましょう。互換は{1,2}しかありません。そして
ab{1,2}=ba, ba{1,2}=ab
で元に戻るループができます。これがハミルトン閉路。これを略して
ab{1,2}ba{1,2}ab
あるいはさらに手抜きして
{1,2}{1,2}
と書くことにします。
互換を{}の集合の記号で書くのは
{x,y}={y,x}
だからです。{}内に入れる数の順序は関係ない。またx=yであってはならない。だから要素を２個含む集合として表すとちょうど良い、というだけのことです。原則として{x,y}はx＜yとなるように書くことにしましょう。
さて、ハミルトン閉路
{1,2}{1,2}
において、出発点がabであってもbaであっても、いやそれどころかazであっても同じ事です。これは重要な点です。
●n=3:abc
abcの３文字からなる場合。この互換は{1,2}, {1,3}, {2,3}があります。ここで、
同じ互換pを二つ並べるとn≧3では必ず失敗する。p={1,2}なら
ppつまり{1,2}{1,2}
で閉路ができてしまい、全部の順列を網羅しません。
さて、同じ互換を続けて繰り返さない、というルールさえ守れば、どれでも良いというわけじゃありませんよ。閉路として、最後に元に戻ることを要求する。するとハミルトン閉路は
(1) {1,2}{1,3}{1,2}{1,3}{1,2}{1,3}
(2) {1,2}{2,3}{1,2}{2,3}{1,2}{2,3}
(3) {1,2}{2,3}{1,3}{1,2}{2,3}{1,3}
(4) {1,3}{2,3}{1,2}{1,3}{2,3}{1,2}
(5) {1,3}{2,3}{1,3}{2,3}{1,3}{2,3}
(6) {1,3}{1,2}{1,3}{1,2}{1,3}{1,2}
(7) {2,3}{1,2}{2,3}{1,2}{2,3}{1,2}
(8) {2,3}{1,3}{1,2}{2,3}{1,3}{1,2}
(9) {2,3}{1,2}{1,3}{2,3}{1,2}{1,3}
とこれだけあります。
しかしよく見ると、
(3)と(4)は逆順になっているだけ。つまり逆回り。
(1)と(6), (5)と(8), (3)と(9)と(5)はループの出発点がずれているだけ。
こういうものは同じ閉路と考えて構わないでしょう。だから、本質的に違うのは
(1) {1,2}{1,3}{1,2}{1,3}{1,2}{1,3}
(2) {1,2}{2,3}{1,2}{2,3}{1,2}{2,3}
(3) {1,2}{2,3}{1,3}{1,2}{2,3}{1,3}
(5) {1,3}{2,3}{1,3}{2,3}{1,3}{2,3}
この４つだけです。
この中で、３種類の互換が全部出てくるのは(3)だけです。
後で説明する理由により、可能な互換が全部出てくるのは望ましい性質なんです。
一方で、(1)(2)(5)は{1,2}が交互に現れてますね。つまり、３文字目を変えないで{1,2}の互換をやる。そして、３文字目を変更する。この繰り返しをやっている。たとえば、
(1) abc{1,2}bac{1,3}cab{1,2}acb{1,3}bca{1,2}cba{1,3}abc
という訳です。３文字目がcの場合をまず尽くし、次にbの場合、次にaの場合、という風になっている。これもまた、大変結構な性質である。で、この後で出てくる理屈によれば、(1)を採用するのが話が綺麗になります。（いや、(1)～(9)のどれを使っても、勿論構わないし、それなりにやりようはあるんですがね。）
でも、
(3-1) {1,2}{1,3}{1,2}{1,3}{1,2}{1,3}
これに決めちゃいます。
●n=4:abcd
まともに数え上げると大変な数のハミルトン閉路が存在します。しかし、
4文字目がdの場合の順列(3!通り)をまず尽くし、次に４文字目がcの場合、....という風にやることにします。
しかも次の形に決めてしまう。
(4-1) [1,2]{3,4}[1,3]{3,4}[1,3]{2,4}[1,3]{1,4}
さて、ここで新しい記号[x,y]を導入しました。これは何かと言いますと、今n=4を検討している訳ですけど、「n=3のハミルトン閉路を一カ所切ったもの」をここに嵌め込む、ということを示している。どういうことかと言いますと、[1,2]というのはn=3におけるハミルトン閉路
(3-1) {1,2}{1,3}{1,2}{1,3}{1,2}{1,3}
のうち、{1,2}を一つ切り取ってひもを作れ、という命令を意味しているんです。この場合、３つある{1,2}のどれでも良いですから除いて、ループを「ひも」に変換しますと3!-1の長さの互換の列
[1,2]＝{1,3}{1,2}{1,3}{1,2}{1,3}
ができる。これを嵌め込むんです。同様に[1,3]というのは
[1,3]={1,2}{1,3}{1,2}{1,3}{1,2}
を嵌め込むことを示しています。本当に嵌め込んでみると
(4-1) {1,3}{1,2}{1,3}{1,2}{1,3}{3,4}{1,2}{1,3}{1,2}{1,3}{1,2}{3,4}{1,2}{1,3}{1,2}{1,3}{1,2}{2,4}{1,2}{1,3}{1,2}{1,3}{1,2}{1,4}
ということになります。[]の記法によって、長さn!の互換の列を2n個の記号で表現できるのでとても便利なのです。
(4-1)がハミルトン閉路になっていることはご自分で確かめて戴くとして、ここで重要なのは
「[1,2]や[1,3]の部分では4文字目は変化しない。」ということ。ですから、
(4-1) [1,2]{3,4}[1,3]{3,4}[1,3]{2,4}[1,3]{1,4}
の最初の[1,2]では4文字目がdに固定、次の[1,3]では４文字目がcに固定。次の[1,3]では４文字目がbに固定、最後の[1,3]では４文字目がaに固定されています。このようにして、当初の方針が実現されている。さらに、
・(4-1)の閉路には{x,4}の形の互換の可能な3通りが（{1,4}, {2,4}, {3,4}）全部現れている。
これが重要なポイントになります。
●n=5:abcde
これも5文字目がeの場合の順列(3!通り)をまず尽くし、次に....という風にやります。いろんなハミルトン閉路のうちから、
(5-1) [1,2]{4,5}[3,4]{4,5}[1,3]{3,5}[1,3]{2,5}[1,3]{1,5}
に限ってしまいましょう。[]で表されるひもとしては、
[1,2], [3,4],[1,3]
が使われています。（これらはn=4におけるハミルトン閉路から作るひも（4!-1個の互換からなる）であって、n=3でのひもじゃないですからご注意下さい。）これらのひも[x,y]は常に作れます。なぜなら{x,y}が(4-1)には必ず含まれていますから、その部分でチョン切ってひもを作ることができます。
さて実は、[x,4]という形のひもを使うときにxに何を持ってきてもn=4におけるハミルトン閉路に含まれているようにするために、n=4の場合に「・(4-1)の閉路には{x,4}の形の互換の可能な3通りが（{1,4}, {2,4}, {3,4}）全部現れている。」という性質を要求したんです。
こうやって作ったn=5のハミルトン閉路もまた、
・(5-1)の閉路には{x,5}の形の互換の可能な4通りが全部現れている。
という性質を満たしています。
●n≧4
たとえばn=8ではどうでしょう。
(8-1) [1,2]{7,8}[6,7]{7,8}[5,6]{6,8}[4,5]{5,8}[3,4]{4,8}[1,3]{3,8}[1,3]{2,8}[1,3]{1,8}
これがハミルトン閉路のひとつです。（[]はn=7におけるひもを表しています。）もう規則性はお分かりでしょう。
[1,2]{7,8} ：[1,2] {n-1,n} ... 最初はこれに決まり。
[6,7]{7,8} ：[n-2,n-1] {n-1,n} ... {n-1,n}がもう一回出てきます。ここからは規則的。
[5,6]{6,8} ：[n-3,n-2] {n-2,n}
[4,5]{5,8} ：[n-4,n-3] {n-3,n}
[3,4]{4,8} ：[n-5,n-4] {n-4,n}
[1,3]{3,8} ：[1,3] {3,n} .... ここから[ ]の方が変則的になります。
[1,3]{2,8} ：[1,3] {2,n}
[1,3]{1,8} ：[1,3] {1,n}
ここで、[2,3]は一度も必要とされてません。ですから、n=3のときに{2,3}を含まないハミルトン閉路を採用しちゃっても構わなかった訳です。
・(8-1)の閉路には{x,8}の形の互換の可能な7通りが全部現れている。
という性質もちゃんと満たしています。
n=10でやってみると、
[1,2]{9,10}[8,9]{9,10}[7,8]{8,10}[6,7]{7,10}[5,6]{6,10}[4,5]{5,10}[3,4]{4,10}[1,3]{3,10}[1,3]{2,10}[1,3]{1,10}
これも同じ規則でできていることがわかりますね。どのように順列が変化していくかというと、
abcdefghij
[1,2]bacdefghij
{9,10}bacdefghji
[8,9]bacdefgjhi
{9,10}bacdefgjih
[7,8]bacdefjgih
{8,10}bacdefjhig
[6,7]bacdejfhig
{7,10}bacdejghif
[5,6]bacdjeghif
{6,10}bacdjfghie
[4,5]bacjdfghie
{5,10}bacjefghid
[3,4]bajcefghid
{4,10}bajdefghic
[1,3]jabdefghic
{3,10}jacdefghib
[1,3]cajdefghib
{2,10}cbjdefghia
[1,3]jbcdefghia
{1,10}abcdefghij
こうなります。
勿論、出発点がabcdefghijでなくても、任意の順列から出発して構わない訳です。
以上、
・互換だけによって、
・探索（trial and errorによる後戻り）なしに、
・n文字からなる順列を全部ちょうど１回づつ発生させ、
・しかも最後に元に戻ってくる
というハミルトン閉路生成システムが一つ構成できました。（無論、他にも解はいろいろあり得ます。）
これをどうプログラムするか、についてはお任せいたしましょう。
お礼
回答ありがとうございます。 はじめて回答を見たときはあまりの量の多さにビックリ仰天してしまいました。 しかし読んでみると具体例を用いた手とり足とりの詳しい解説で,苦もなく (ホントはちょっと苦労しました)読めました。 プログラムの方も何とか書けそうです。 >さて、ここで新しい記号[x,y]を導入しました。これは何かと言いますと、 >今n=4を検討している訳ですけど、「n=3のハミルトン閉路を一カ所切った >もの」をここに嵌め込む、ということを示している。 最初はエッずいぶんトリッキーなことをするなあと、思ったのですが 読んでいく内に,いやいやこれは結構自然な記号の導入なのかもと思ったり。 いろいろ感心させられました。 数学的センスのある方、御教示おねがいします。といって質問したわけですが、 僕が期待していた以上のセンスの持ち主の目に止まったようで,有難いです。 親切な回答ありがとうございました。