２−６−１．再検グラフ法

■デッドロックはある枝を任意に選択して確定することによって発生する．このとき，関係する複数の枝が除去され，それによって自動確定される枝が発生し，そのことによって再び枝が除去されるという連鎖反応がグラフ上で時間差をもって複数の方向に伝播することがデッドロックの非決定性の直接の原因である．複数の枝分かれした自動確定の波はグラフ上の複数の地点で衝突し複数のしかも互いに矛盾した例外を発生する．

■しかし，結局においてデッドロックの発生する第１原因は枝の除去という操作にあり，この操作はある意味において枝数の引き算が行われるという以上のものでは有り得ないから，加法性の原理の成立する世界の事象であると考えてよい．つまり，デッドロックの発生する場所は複数あり，その場所は不定であるとしても，その現象を規定する点の枝数の計算に関しては加法性の原理が成り立つから，デッドロックという事象そのものがこれらの計算課程の重ねあわせ，つまり単純な加算によって発生すると見ることができる．これを，デッドロックの重ね合わせの原理と呼ぶ．

■枝数の減算によってある点の枝数が１になると，その枝が確定する．また，その点の枝数が０になるとデッドロックが発生する．デッドロックの重ねあわせの原理の立場に立って考えると，このとき本来ならこの枝数０の点のすべての枝が確定可能であった，ということがわかる．つまり，枝数０になる１ステップ前には枝数１という状態があり，しかもこの枝数１となることに関してその点のすべての枝にはまったく平等の可能性が存在する．

■再検グラフ法では，この本来確定可能であったパスのすべてを延長してゆくことによって，あらゆる可能な場合を含んだデッドロックパスを作成する．再検グラフがデッドロックした確定パスからあらゆる可能な場合を含んだデッドロックパスとデッドロックマップを作成する手順は以下のようなものとなるだろう．以下では，グラフＧは有向でかつ連結であると仮定する．また以下の記述において，すべての点は入力点と出力点の２重の意味を持つものとして定義されそのように操作される．同様にすべての枝は一方から見れば入力枝であり，他方から見れば出力枝として扱われる．

■デッドロックを発生するために十分な枝集合を要因枝セットと呼ぶ．短絡グラフから引き継がれたデッドロックする確定パスはこの意味での要因枝セットである．極小な要因枝セット，つまりあるデッドロックを発生するために必要十分な枝集合を障害枝セットと呼ぶ．障害枝セット⊆要因枝セットである．障害枝セットはその枝集合のうちのどの枝を取り除いてもデッドロックが発現しなくなるような要因枝セットである．ある障害を発生する要因枝セットを与えられたとき，この枝集合から障害枝セットを決定することは可能である29．

(1) グラフＧ上のすべての点の枝数を記録するための枝カウント表を用意する．枝カウントは入力枝と出力枝をそれぞれ独立に管理する．

(2) 確定パス上のすべての継承点の枝を確定する．確定した枝には確定のマークを付ける．除去された枝にも除去のマークを付ける．除去された枝は検定グラフのようにパージされる代わりに，その枝の端点の枝カウントを１減ずる．

(3) （入力枝ないし出力枝の）枝カウントが１となった点の枝は因子検定の場合と同様に自動確定する．枝カウントが１となることは，一度しか発生しない．因子検定では，隣接する複数の点の枝カウントが１となった点，つまり確定パスが分裂しようとしている点（分裂点）があると，デッドロックが発生し，停止する．しかし，再検定ではこのような場合にもそれぞれの枝カウント１の枝について確定を実行する．

(4) 枝カウントが０になった脱落点があるときは，その点のすべての枝を確定する．

(5) 一旦確定された枝が再び確定されることは無い．また，一旦除去された枝が再び除去されることも無い．これは重ね合わせの原理から言って当然のことである．但し，ある枝を確定する操作と除去する操作はまったく独立したものとして扱われる．

(6) すべての脱落点の全枝確定が完了するまで，これを繰り返す．

(7) 確定のマークのついたすべての枝からなる枝集合をデッドロックパスと呼ぶ．デッドロックパスには，すべての継承点と分裂点，脱落点および自動確定されたその他の確定点が乗っている．

(8) グラフＧの枝のうち，確定のマークも除去のマークも付いていない枝をすべてパージして，残った枝集合の枝セクショングラフを再検グラフＲとする．
再検グラフＲはデッドロックマップとも呼ばれる．デッドロックマップの枝集合はデッドロックパスの枝とデッドロックパスの確定操作によって除去された枝から構成される．この枝集合の中には明らかに矛盾の原因となった枝が含まれている．しかし，その枝を特定したとしても，その矛盾を解くことはできない．求められているのは，このデッドロックマップから矛盾しない代替パスを編成することである．次のような手順でこれを行なうことができる．

(1) デッドロックパス上のある矛盾点の任意の枝を復活確定する．矛盾点には枝カウント０になった脱落点と，枝カウント１の枝を複数持った分裂点がある．これらの点のいずれかでシャットダウンすれば，このグラフは非ハミルトングラフである．

(2) 同様にしてデッドロックパス上のすべての矛盾点の任意の枝を復活確定する．すべての矛盾点の枝を確定することができなければ，このグラフは非ハミルトングラフである．矛盾点の枝がその前の操作によって既に確定している場合，既に除去されている場合が有り得る．これらの場合はそれを受け入れる．

(3) デッドロックパス上のデッドロックしていない点の枝を確定する．デッドロックしていない点はデッドロックパス上に枝を１本だけ持っているからその枝を確定する．これらの点の枝が既に確定している場合，既に除去されている場合はそれを受け入れる．

(4) これをデッドロックパス上のすべてのデッドロックしていない点について行なう．このようにして確定された枝からなる枝集合が再検グラフの返す代替パスである．

■この手順で重要なことは，すべての矛盾点の枝を任意に確定した後は，もはやデッドロックは決して発生しないということである．なぜならデッドロックマップにはすべての可能な場合が含まれているから，矛盾点でない点が枝カウント０になるということは起り得ないし，また一旦確定された矛盾点がもう一度デッドロックするということも有り得ないからである．（矛盾点の枝は既に確定されているから，もはや枝カウントが０になるということも枝カウント１の枝を２本持つことも起り得ない）

■また，この代替パスには継承点，つまり確定パスのすべての点が乗っているということも，次のことから言える．もし，継承点が代替パスの上に無いとしたらその点のすべての枝が除去されているためである．しかし，デッドロックが発生していない以上そのようなことは起っていない．従って，このようにして作成された代替パスは，すべての継承点を含むデッドロックしない枝集合である．この代替パスを，あらゆる可能な場合を含んだデッドロックマップから生成された本来可能であった代替パスと呼ぶ．

■本来可能であった代替パスは確かにすべての継承点を含むデッドロックしない枝集合であるが，残念なことにこれは２重の意味で不可能な再検定となっている．まず，デッドロックパスを生成するプロセスで枝カウント０となる矛盾点自体が連鎖反応的に増殖してしまうため，矛盾点のすべての枝を確定することがコスト的に不可能である．枝カウント０の点の全枝の確定による自動確定の波は周辺の枝をすべて刈り倒す大洪水となり，枝カウント０の点を増殖しながら，全地を覆い尽くすものとなる．

■矛盾点の無際限な増殖はデッドロックマップから代替パスを生成するプロセスの計算コストにも致命的な影響を及ぼすものとなる．矛盾点の個数をｋ，ある点の最大枝数がωであるとすれば，すべての矛盾点を任意に確定するためには最悪ωｋのコストがかかることになる．ｋが巨大数になることを避けられないということから，本来可能であった代替パスの方法は非現実的なものであるという結論が導かれる．

29 ここで定義された障害枝セットは，この後の議論には登場してこない．障害枝セットを特定するということは言ってみれば，事件の犯人を見つけ出すということに等しい．しかし，刑事訴訟法的なアプローチはハミルトン閉路問題を解くためにはあまり有効では無いように思われる．