１．幸運をコントロールする方法
１－１．ハミルトン閉路問題をなぜ始めたか
■ハミルトン閉路問題とは，１９世紀アイルランドの数学者ハミルトン卿 (Sr. William Rowan Hamilton) によって定式化されたグラフ1上の問題であり，「与えられたグラフのすべての点を通る閉路があるかどうか」を問うものである．
■点の数がＮ個2あるグラフの場合，このような閉路の数は最大Ｎ！個3ある．要求を満たす閉路があるかどうかを調べるもっとも簡易な方法はすべての路を総当たりするというものであり，その計算コストはＮ！つまり指数時間アルゴリズムを要する．これよりも能率のよい方法つまり多項式時間アルゴリズムでこの解を得ることができるのか否かが問題である．このように指数時間アルゴリズムはあっても，多項式時間アルゴリズムが存在するか，存在しないかが確定していない一群の問題がありＮＰ完全問題と呼ばれている．ＮＰ完全問題は相互に多項式アルゴリズムによって他の問題に変換できるという特徴がある．従って，ひとつのＮＰ完全問題が解決するということは，他のすべての問題が解を得るということに等しい．
■この問題は，１世紀もの間多くの数学者の挑戦を斥けてきた．それは「あらゆるプロポーズを拒みとおしたかぐや姫のように」と言うにふさわしい．ハミルトン閉路問題はよく知られた問題（つまりは噂の女性）であったから，彼女への求婚者の中には著名な数学者のほとんどが含まれていたと言っても誇張にはならないだろう．
■この研究が開始された当初の目的は，弊社の開発したグラフを操作するためのＮ木ないしノジュールリストと呼ぶ汎用多元木を用いたプログラミング技法になにがしかの理論的裏付けを与えることにあった．筆者が何年か前に日本ソフトウェア科学会に加盟したのも，元々はプログラミングの実務に関るグラフ操作の理論構築を「誰かにやってもらおう」というのがそもそもの動機である．しかし，忙しさにかまけて時間だけが為すこともなく過ぎてゆき，ある日ふと気が付くと何時の間にかそれを自分で始めていた．
■最初は，「グラフ理論を代数化する」ということに目標を置いていた．そのためにまずグラフ上の任意の点にバベジ数と呼ぶある数を割り当てるという方法を考案した．この方法はかなり見込みがあるように思えたので，これを使ってグラフの同型対応問題を解いてみることにした．使い慣れたＮ木をベースにしてバベジ数を点の重みとする加重木をその上に定義し，それをある正準な木に変換することができれば，２つのグラフを正準変換して比較することが可能になると考えた．やってみると中々手強かったかったがなんとか定式化した．
■ついでにハミルトン閉路問題に挑戦した．手書きで問題を解いてみると，これは「グラフの同型対応問題」の単なる応用問題であることが分かった．「Ｎ木をともかくまっすぐにしてやればよい」つまり「直列枝だけからなるグラフと同型になるよう変換すればよい」ということに気付いた．実際に紙の上で試みると，ほとんど２，３０分であっという間に解けた．
■しかし，何でそんなに簡単に解けるのかというプロセスがまるきり分からなかったので，もう一度グラフの同型対応問題に戻ってその解法を吟味することにした．同型対応問題の例題として完全グラフ4を与えてみると，あっという間に破綻した．ほどなく，この破綻を補填するのは生易しいことでは無いということが分かってきた．確かにこの辺りで手を引いていればここまで深入りすることも無かったであろう．しかし既に「グラフ問題を考える」ことがおもしろくなって来ていた．
■グラフの同型対応問題は取り敢えず中断することにして，ハミルトン閉路問題に集中することにした．「グラフ理論の代数化」という手法は非常に魅力があったが，取り扱う数値が実用限界を越えて巨大なものになってしまうという欠陥があり，容易には収束できそうも無かったので，組み合わせ論的手法と呼ばれるグラフ理論の古典的方法に戻って考えることにした．
■紙の上に簡単な図を描いて手書きで解く程度の小規模な問題については，少なくとも１０種類以上の高速な解法を考案して試みた．あるものは満足な解答を与え，中にはかなりインチキなものも含まれていた．この頃には解法は既に１２点の非平面的グラフを数ステージで解ける程度に進化していた.１２点完全グラフのすべての枝を全数検査すると最大479,001,600の場合が発生することから考えるとこれは十分よい成績であるように思われた．
■しかし，ハミルトン閉路を持たないグラフを判定するためにはすべての場合を尽くすしか無かったので，計算コストが指数時間を越えることはどうしても避けられないように思われた．「任意選択局面において，矛盾枝を選択すると必ずその局面内でデッドロックする」という仮定を置くとＮ^4のコストで計算が完了できることが分かった．このようなグラフは現実には存在しないのだが，このような仮定の成立する理想グラフを考えることで問題の骨格が少しづつ見えてきた．
■また，もしグラフが強ハミルトン性という位相的特性を持つことがあるとすれば，問題は完全に解けるだろうということも分かった．強ハミルトン性というのは，グラフのすべての点の枝数が３以上である間は，決してデッドロックしないという性質であり，グラフを操作して観察すると確かにそのようなことが成立しているようにも見えるのだが，実際には有り得ないような架空の性質である．
■Ｎ木は組み合わせ論的方法にうまく適合しなかったので，主に２部グラフを使って問題を考えることにした．間違ったパスを選択したときに発生するデッドロックと呼ぶ現象についても詳細な観察を行い，この現象が非決定的な性質を持っていること，ハミルトン閉路問題の困難の大半はこの非決定性に関るものであるということが段々と見えてきた．デッドロックは同時多発的に複数の場所で発生し，かつその場所は本質的に決定不能である．
■我々は，ハミルトン閉路問題に現れるこのような非決定性を問題オメガと呼ぶことにした．つまりハミルトン閉路問題の中にはこの問題オメガがあり，この問題を解決しない限りどのような解もその場しのぎのものであることがやがて判明する．アルゴリズムの中にこのオメガがある限り，計算コストがＮＰになることは避けられない．オメガは洞窟の奥深くに幽閉されている王女の前にうずくまるドラゴンであった．
■検定グラフという明解なグラフ構成を定式化できた段階で，問題はかなり取り扱い易い形式に変換されるようになった．さらに検定グラフを一歩進めた短絡グラフと呼ぶハミルトン位相同型なグラフを手に入れることができた．短絡グラフの方法は「あるハミルトングラフのハミルトンタイ5の一部に含まれるパスを短絡縮約6して得られるグラフはハミルトングラフである」という原理に基づくものであり，これに関する定理を証明することができたので，短絡グラフの方法は我々のハミルトン検定法に確立した強固な不動点を与えるものとなった．
■小規模な問題に対しては短絡グラフ法はまったく強力な方法である．しかし，グラフが大規模なものになるに従いこの方法では到底歯が立たないということもしだいに分かってきた．短絡グラフ法では，ある枝をハミルトンタイの枝と仮定して確定し，グラフを段階的に縮約してゆくことによって問題を収束させようとするが，例えば１万点のグラフをこの方法で検定しようとすると，9990ステップくらいまでは誤った枝を選択しても何も起らないというまったく話にならない状況が続いてしまう．しかも，この最終局面で発見された誤りを修正するためには，この海のように深い全局面のすべての点を全数展開しなくてはならないことになる．
■このような事態を改善するために，まずｋ端子グラフ分割という方法が導入された．これはグラフを完全に左右２つの部分グラフに分割しそれぞれを個別に検定して，その確定パスを突き合わせるという方法である，もしこの方法がつねに適用できるのであれば当然ハミルトン閉路問題は容易に解を得ることができる．また端子点がつねに偶数個のＩＯを要求するという制約も問題を限定するのに十分な効果をもたらすものであった．しかし，ｋ端子分割法には次の３つの困難があった．①そのように都合のよい分割がつねに存在するわけではない．②端子点数ｋが大きくなると端子点を見つけるためのコストだけで既に過大なものとなってしまう．③端子点数ｋが大きい場合にはそれぞれの確定パスを突き合わせるためのコストが無視できない程度に大きなものとなる．
■すべての端子分割の検査はあきらめて，たとえば２，３端子分割のみを検査するという限定は現実的な妥協の産物だが，目の粗いふるいを使うしかないというのは苦しい選択である．
■ｋ端子グラフ分割と類似した方法としてカットセット分割が提案された．カットセット分割も原理はほとんどｋ端子分割と同じだが，点を基準に分割するのではなく，複数の枝を除去することによってグラフを分割する．カットセット分割とｋ端子分割はほとんど近接しているが，一方で見逃すことになる矛盾を他方で検出できる可能性があるので，併用することが望ましい．カットセット分割の場合もｋ端子分割と同様に十全な検定を行うことはコスト的な理由から不可能であることは明らかだった．
1 この草稿の中では，無向グラフと有向グラフを特に区別しないで単にグラフとしているが，取り扱う対象は主に有向グラフである．
2 この草稿ではグラフの点数をＮ，枝数をＭで表示する．一般の変数には適宜小文字の変数名を当てる．また，グラフの要素を示す用語には点と枝を当てる．文献によっては点を頂点とし，枝を辺と呼ぶ場合もあるが，この草稿では，頂点ないし辺という用語は，ある特殊な意味を持った点ないし枝を示す場合にのみ用いる．
3 循環するパスを同一のものと考えれば，ユニークな閉路の個数は（Ｎ－１）！個である．また，右循環と左循環の違いを無視する場合には，（Ｎ－１）！／２個と言うべきだろう．
4 すべての点を相互に接続する枝のあるグラフ
5 ハミルトン閉路と同じ．以下ハミルトンタイとハミルトン閉路を場合によって使い分ける．ハミルトンタイは一般に「グラフ理論的」な文脈上で用いている．
6 この短絡縮約はグラフ理論で通常，位相同型な変換と呼ばれている２点間の短絡とは多少異なるものである．