２−６−３．復活木による再生変換

■グラフＧのデッドロックする確定パスを与えられとき，無時間検定の方法によってグラフＧの初発的なデッドロックの要因枝集合であるデッドロックパスとデッドロックマップを生成することができる．このデッドロックマップ上でデッドロックパスのすべての枝を確定するとその最初のセコンドにおいて初発的なデッドロックが発生する．このとき，デッドロックマップ上には，枝カウント０の脱落点と枝カウント１の分裂枝を複数持った分裂点が存在する．分裂枝からはそれと同数の脱落点を生じるから，結局において再生変換の開始図式上には，脱落点の総数＝脱落点の個数＋Σ分裂点の分裂枝数の脱落点が存在することになる．

■ｎ点有向グラフＵのすべての点を入力点と出力点に分割してグラフの点数をｎ×２とすることによって得られるグラフを半点グラフＵ' とする．分割されて２個となったそれぞれの点は場合によっては半点と呼ばれる．Ｕの枝は点に接続する向きに従って，それぞれＵ' の新しい点（半点）に繋ぎかえる．（枝を持たない半点は生成されないとしてもよい）．

■デッドロックパスは任意確定された枝とそれに付随して自動確定した枝から構成される枝集合であるから，必ずしも連結ではない．再検グラフＲはデッドロックパスおよびデッドロックパスの枝に隣接する除去枝集合からなる有向グラフＧの部分グラフであるから，同様に必ずしも連結なグラフではない．有向グラフＧの無時間検定によって生成された再検グラフＲの半点グラフをＲ' とする．Ｒ' は必ずしも連結でない有向グラフである．

�@ 半点グラフＲ' の点には極性が定義される．出力点の極性を＋，入力点の極性を−とする．

�A Ｒ' の枝は入力枝と出力枝を区別されるが，ある枝はつねに入力枝であり，同時に出力枝でもあるから，入力枝，出力枝の区分は枝の属性値ではない．

�B Ｒ' の枝は再検グラフＲの確定枝か，除去枝か，ないしは分裂枝である．

�C 確定枝を持たない点を頂点と呼ぶ．分裂点，脱落点，未検定点は頂点である．（Ｒ' 上ではすべての点は半点であることに注意する）

�D 確定枝を持つ点を確定半点と呼ぶ．

�E 枝の向きの等しい２本以上の確定枝を持つ確定半点は存在しない．

■脱落点Ｐの復活木Ｔは以下のようなＲ' の部分木として構成される．

�@ 復活木Ｔは脱落点Ｐを根とする有向木である．脱落点Ｐを復活木Ｔの出発頂点と呼ぶ．

�A Ｔの復活経路は枝の向きが交互に反転する交代路である．また，この交代路にはひとつ置きに確定枝が現れる．復活経路は単純な有向路である．

�B Ｔの復活経路上では点の極性が交互に反転する．

�C Ｔの復活経路は確定枝によって分岐することも，合流することもない．

�D Ｔには復活経路が合流する枝を含まない．（余分な枝は捨てる）

�E Ｔは出発頂点Ｐを出発点とするすべての復活経路の枝を含む半点グラフＲ' の枝セクション連結部分グラフである．

■半点グラフＲ' 上に，再検グラフＲのすべての脱落点の復活木を含む森 (forest) となるようなＲ' の部分グラフを考え，これを再生マップRと呼ぶことにする．Rは以下のような特徴を持つ必ずしも連結でない有向グラフである．

�@ RはＲ' のすべての脱落点を出発頂点とする復活木を含む．また，Ｒ' の未検定頂点をRの解決頂点と呼ぶ．

�A RはＲ' のすべての分裂点を頂点として含み，その分裂枝によって脱落点に接続する．

�B 分裂頂点から脱落点を通る路は，分裂枝→除去枝となり，確定枝が現れていないから復活経路ではない．分裂頂点の分裂枝のうちの任意の１本を確定枝とし，他の枝を除去することによって，分裂頂点は解決半点となる．また，確定枝となった分裂枝に接続する脱落点も解決半点となり，除去枝となった分裂枝に接続する脱落点は出発頂点となる．

■ハミルトン検定の初期局面（任意選択がまだ行われていない段階）において原グラフにもともと存在していた直列枝の自動確定のみが実行された段階の短絡グラフを初期確定グラフと呼ぶことにする．復活木の再生変換による無時間検定は，この初期確定グラフをベースに進めることにする．初期確定グラフは初期局面で確定したパスを短絡縮約して得られる短絡グラフである．初期確定グラフで確定された枝はすべて既定枝であるから，デッドロックの障害枝となることはあり得ないので，無時間検定を原グラフまで戻ることなく初期確定グラフの段階で実行しても得られる結果は同じである．

■このような前提のもとで，無時間検定の再検グラフＲからすべての脱落点の復活木を含む再生マップを，以下のように再検グラフの半点グラフとして生成し，これから再検グラフＲ上でデッドロックしない再生パスを求める．

(1) 無時間検定は原グラフではなく，初期確定グラフの段階で実行されるものとする．原グラフの直列枝は短絡縮約されているので，初期確定グラフ上には存在しない．生成された再検グラフＲでは，そのすべての枝が確定枝，除去枝，分裂枝に区分されているとする．またすべての点は確定点，分裂点，脱落点，未検定点のいずれかに区分されている．

(2) 再検グラフＲの半点グラフを再生マップRとする．

(3) 確定枝に接続する点を確定半点とする．

(4) 複数の分裂枝に接続する点を分裂頂点とする．分裂頂点に接続する任意の分裂枝を確定枝に変更する．その他の分裂枝を除去枝とする．この操作によって分裂頂点に接続する脱落点のうちのひとつは確定半点に変わる．したがって，Rには出発頂点数＝脱落点の個数＋Σ（分裂頂点の分裂枝数−１）の出発頂点が存在することになる．

(5) これにより，グラフRの点は確定半点，出発頂点，解決頂点の３種となり，枝は確定枝，除去枝の２種となる．

(6) Rにはすべての出発頂点の復活木が含まれていることは明らかである．

(7) 初期確定グラフ上には直列枝は存在しないから，すべての確定半点には必ず少なくとも１本の除去枝が接続しているので，どの確定半点もその点を含む復活木の端点となることはあり得ない．従って，R上の復活木の端点となる点は，出発頂点かないし解決頂点のみである．２点以上の点を持つ木は少なくとも２個の端点を持っているから，すべての復活木は少なくとも２個の端点を持ち，そのうちの１個は解決頂点である．

(8) ある復活木の出発頂点から解決頂点に至る復活経路は存在するから，すべての脱落点はその解決を与える復活経路をR上に持っている．

(9) すべての復活木において選択された復活径路上のすべての確定枝を除去し，除去枝を確定することによってデッドロックしない再生パスを得ることができる．

■再生マップRにはすべての出発頂点の復活木が含まれているが，これらの木が点ないし，枝を共有する場合がある．つまり，複数の復活木が交叉している場合２つの出発頂点の復活経路を分離できない可能性がある．以下ではこのような場合について検討する．

■２つの復活木がある点を共有するとき，すべての点は入力点であるか出力点であるかのいずれかであるから，その点に接続する枝の極性が異なるということはあり得ない．出発点の極性が等しい場合でも，復活径路が交差する点に確定枝で接続する場合と除去枝で接続する場合があり得る．出発点の極性が異なる場合には，交叉する点に接続する枝種は互いに異なるものとなるが，３つ以上の復活径路が交叉する場合には少なくともそのうちの２つの出発点の極性が等しいという状況が起る．よって複数の復活木の復活径路が交叉する場合を以下の４種に区分してその状況を観察する．

�@ 出発点の極性が等しく，共有点に確定枝で接続する場合
�A 出発点の極性が等しく，共有点に除去枝で接続する場合
�B 出発点の極性が反対の場合
�C ３つ以上の復活径路が交差する場合

�@ 出発点の極性が等しく，共有点に確定枝で接続する場合

出発点の極性が等しく，共有点に確定枝で接続しているとしたら，その共有点は分裂点である．分裂点には隣接して脱落点が存在している．これは，３つ以上の復活径路が交叉する場合も同じである．無時間検定の初発的デッドロック状態では，このような図式はあり得ない．

�A 出発点の極性が等しく，共有点に除去枝で接続する場合

■出発点の極性の等しい復活経路が交叉する場合には，共有点で競合が発生する．いずれかの脱落点が路を譲らなくてはならない．もし競合を解消できるような資源が不足する場合には，ロックアウトする．これは，３つ以上の復活径路が交叉する場合も同じである．

�B 出発点の極性が反対の場合

■出発点の極性の異なる２つの復活径路が交叉する場合には，一方の枝は確定枝であり，他方の枝は除去枝である．このとき，一方の出発点から共有点を通って他方の出発点に至る路は互いに一方を出発点とし，他方を解決点とする復活径路をそれ自身が構成していることになる．

�C 出発点の極性の異なる３つ以上の復活径路が交差する場合

■３つ以上の復活径路が交叉する場合には，これらの復活径路は出発点の極性によって２つのグループに区分できる．このとき，これらの組み合わせによって次の２つの場合が発生する．

▽ 出発極性の等しい復活径路の一方のグループで，共有点に確定枝で接続する場合

■この復活径路の共有点は分裂点である．無時間検定の初発的デッドロック状態では，このような図式はあり得ない．

▽ 出発極性の等しい復活径路の一方のグループで，共有点に除去枝で接続する場合

■もしこのとき，共有点に確定枝で接続する復活径路が２つ以上存在する場合には，この共有点は分裂点である．無時間検定の初発的デッドロック状態では，このような図式はあり得ない．そうでない場合には，共有点に除去枝で接続するグループの復活径路が配分可能であるかどうかを調査する．資源が不足する場合にはロックアウトする．この場合にも，出発点の極性の異なる復活経路は相互に他の解を与えるものとなる．

■結局，極性の異なる２つの脱落点の交叉する復活経路では，もはやその先の経路は不要であり，一方の出発点と他方の出発点を結ぶ経路がそれ自身の解を与える復活経路となっている．極性の等しい交叉する複数の復活経路があった場合には，その経路の交叉する点に接続する枝は互いに競合するものとなるので，資源の配分を考えなくてはならない．もし，この配分が成功しないときは，このグラフは非ハミルトングラフであると推定される．

■これらのことから最終的な結論として，短絡グラフの確定パスを初期確定グラフ上で無時間検定して得られた再検グラフからすべての脱落点の復活木を構成することは可能であり，もしこれらの復活木のすべてにおいて終点が未検定点であるような復活径路があるかないし共有できれば，再生変換は間違いなく成功すると考えてよい．再生マップから復活経路を求める再生変換がロックアウトする場合には，このグラフを非ハミルトングラフであると推定する十分な根拠を有すると言えるだろう．

■再検グラフの復活木が復活径路を持たないときには，そのグラフは非ハミルトングラフであるという推定が正しいとするならば，復活木検定は３種検定を援用するまでもなく，自前の完全な無試行判定法を持っていると言えるだろう．もし，復活木検定が完全な検定であるとしたら，たとえばクロスＩＯ矛盾が復活木上ではどのような表現を得るのかなど，他の検定との対応関係が照合され明らかにされなくてはならない．３種検定におけるロックアウトが復活木ではどのように表現されるのかを見る必要がある．