２−１．因子検定

■まず，以下で使用するいくつかの用語を定義する．

定義2-1.1: ハミルトンタイ

グラフＧのすべての点を通る初等的閉路をハミルトンタイと呼ぶ．

定義2-1.2: ハミルトンパス

グラフＧのすべての点を通る初等的な路をハミルトンパスと呼ぶ．

定義2-1.3: ハミルトングラフ

ハミルトンタイを持っているグラフをハミルトングラフと呼ぶ．

定義2-1.4: 非ハミルトングラフ

ハミルトンタイを持たないグラフを非ハミルトングラフと呼ぶ．すべてのグラフは，ハミルトングラフでなければ非ハミルトングラフである．

定義2-1.5: 完全ハミルトングラフ

任意の枝を通るハミルトンタイを持つグラフを完全ハミルトングラフと呼ぶ．

定義2-1.6: 矛盾枝，障害枝，既定枝

グラフＧのどのハミルトンタイにも含まれない枝をそのグラフの矛盾枝と呼ぶ．つまり，Ｇの矛盾枝とはグラフＧのハミルトンタイの一般解に含まれない枝を言う．グラフＧのあるハミルトンタイに含まれない枝をそのタイの障害枝と呼ぶ．Ｇの障害枝とはグラフＧのハミルトンタイのある特殊解に含まれない枝である．これに対し，Ｇのハミルトンタイのすべての特殊解に含まれる枝はハミルトンタイの既定枝と呼ばれる．

定義2-1.7: 確定パス（確定枝集合）

ハミルトン検定のある段階でグラフＧのあるハミルトンタイの枝と仮定され，他の枝集合と区分された枝集合を確定パスないし確定枝集合と呼ぶ．確定パスは複数の枝ないし直列の枝リストとして構成されるから，必ずしも連続した路であるとは限らない．また，ある枝を選択して確定パスに追加する操作を確定と呼ぶ．

定義2-1.8: ハミルトンタイ公準，十全な検定，完備な検定

Ｇの部分グラフＧ' がＧのハミルトンタイであるための条件として以下の規則を定め，ハミルトンタイ公準と呼ぶ．ハミルトンタイ公準がハミルトン検定のための規則として必要かつ十分であることを定理として証明する．

(1) ２因子規則：Ｇ' はＧの全域２因子部分グラフである．
(2) １閉路規則：Ｇ' は２つ以上の初等閉路を持たない．

２因子規則の違反を検出可能な検定法を十全な検定と呼び，２因子規則と１閉路規則の違反をともに検出可能な検定法を完備な検定と呼ぶ．

定義2-1.9: デッドロック，シャットダウン，ロックアウト

ある枝操作を原因とするハミルトンタイ公準違反が発生した状況をデッドロックと言う．ある点におけるすべての枝を検定してその前方で必ずデッドロックが発生するような状況をシャットダウンと呼ぶ．すべての点においてシャットダウンが発生する場合のように，あるグラフが非ハミルトングラフであることが確定するような状況をロックアウトと呼ぶ．

定理2-1.1: ハミルトンタイ公準

グラフＧの全域２因子部分グラフで２つ以上の初等的閉路を持たないグラフＧ' はグラフＧのハミルトンタイの枝を各辺とする多角形グラフ20である．この逆も成立する．

証明：

もしＧ' が連結ならば，Ｇ' のすべての点の枝数は偶数だからすべての枝を通るオイラー閉路を持っている．この閉路は同じ点を２回通過することはないからＧ' のすべての点を通る初等的な閉路であり，よってＧ' はハミルトンタイを持ち，かつＧ' はＧの全域部分グラフであるから，このハミルトンタイはＧのハミルトンタイである．

もしＧ' が連結でないとすると，Ｇ' を連結成分に分離することができる．これらの連結成分のすべての点を通る初等的な閉路が存在するから，Ｇ' は２つ以上の初等的閉路を持つことになり，仮定と矛盾する．

よって，Ｇ' は連結でＧのハミルトンタイを持ち，かつそれ以外の要素を持たないから，グラフＧ' はＧのハミルトンタイを辺とする多角形グラフである．

Ｇ' がグラフＧのハミルトンタイΠを辺とする多角形グラフであるとすると，ΠはグラフＧのすべての点を通る初等的な閉路であるから，Ｇ' はＧの全域部分グラフであり，Ｇ' のすべての点は２本の枝を持つから２因子グラフである．Ｇ' の任意の点はＧ' の閉路を通って元の点に戻ってくるために他のすべての点を経由しなくてはならないから，この閉路はＧ' の唯１つの初等的閉路である．

補題2-1.1: 非連結グラフ

連結21でないグラフは非ハミルトングラフである．

証明：

連結でないグラフＧに，ある点から他の点へ至る路のない２つの点がある．これらをＰ，Ｑとするとき，点Ｐを通るハミルトンタイは点Ｑを通らなくてはならないが，点Ｐから点Ｑへ至る路がないのだから，グラフＧはハミルトンタイを持たない．

補題2-1.2: 非強連結グラフ

強連結22でない有向グラフは非ハミルトングラフである．

証明：

強連結でない有向グラフには，点Ｐから点Ｑへの路が存在しないか，点Ｐから点Ｑへの路は存在するが，点Ｑから点Ｐへの路が存在しない２点が存在する．点Ｐを通る有向ハミルトンタイは点Ｑを通らなくてはならないが，このためには点Ｐから点Ｑに至る路と点Ｑから点Ｐに至る路が必要である．これらの路が存在しないのだからグラフＧはハミルトンタイを持たない．

補題2-1.3: 非２連結グラフ

２連結23でないグラフは非ハミルトングラフである．

証明：

グラフＧが連結でないときには，補題2-1.1によりグラフＧは非ハミルトングラフである．よって，グラフＧは連結であると仮定する．グラフＧは２連結でないから，Ｇのある点を除去してグラフを２つの（必ずしも連結でない）成分に分離することができる．この点をＰとする．一方の成分のある点をＡ，他方の成分のある点をＢとしたとき，グラフＧのハミルトンタイは点Ａから点Ｂに至る路とそれと異なる点Ｂから点Ａに至る路を通らなくてはならない．ところが，点Ａから点Ｂに至る路も点Ｂから点Ａに至る路も点Ｐを通らなくてはならないから，ハミルトンタイは点Ｐを２回通ることになり，矛盾する．よってグラフＧはハミルトンタイを持たない．

■ハミルトン閉路問題には，我々が問題オメガと呼んでいる非決定性が含まれているので，ハミルトン検定法の中に，試行錯誤的な探索手順が含まれるようになることは不可避である．因子検定法は任意に枝を選択して確定パスに追加する操作から構成されるもっとも基本的な検定法であり．主に確定パス上の点に接続する枝数に注目して検定を進めるところから，因子検定と呼ばれる．

■ハミルトンタイ公準は検定のための規則であるが，操作的にはある枝を選択して確定するときの制約条件であると考えることもできる．つまり，任意に枝を選択して確定パスに追加しようとするときには，公準を満たすような枝を選択することが要求される．また，ある枝を確定したとき，この公準を満たすという制約条件から自動的に必ず確定パスに追加されなくてはならない枝が決定される場合がある．従って，枝の確定操作には，任意に選択して確定する場合（これを任意選択と呼ぶ）と自動的に確定する場合（これを自動確定と呼ぶ）の２種があることになる．任意選択の１段階をステージないし任意選択局面と呼ぶ．１ステージの中には１個の任意選択と複数の自動確定が含まれることになる．任意選択と自動確定の両方の場合を含めて，１本の枝を確定パスに追加する１段階をステップと呼ぶことにする．

■因子検定は有向グラフを対象とする検定法である．与えられたグラフが無向グラフである場合は，１本の無向枝を２本の対向する有向枝に置き換えて検定する．また，ある点の入力枝ないし出力枝が１本だけの状態のとき，この枝を単独枝と呼び，このような点を単枝点と呼ぶ．因子検定における確定操作（１ステップ）は以下のような手順から構成される．

(1) 枝を確定パスに追加する．
(2) 確定パスの点数がＮであるときは停止する．
(3) 確定パス上の枝リストを閉路として閉じる枝があるときは，除去する．
(4) 確定した枝の入力点の入力枝，出力点の出力枝を除去する．

■因子検定における任意選択局面（１ステージ）は次のような手順から構成される．

(1) 任意に枝を選択して，確定する．
(2) 入力枝を持たない入力点，出力枝を持たない出力点があれば停止する．
(3) 複数の単枝点に隣接する点があれば停止する．
(4) 単枝点があれば，その単独枝を確定する．
(5) 単枝点が無くなるまで(2)から繰り返す．

■因子検定は複数の任意選択局面から構成され，任意選択手順は複数の確定操作からなり，確定操作は複数の枝の除去操作からなっているから，結局において因子検定はグラフから枝を除去する操作を反復して最終的にハミルトンタイの枝のみからなる部分グラフを求める操作として実現される．確定パスがグラフのすべての点を含むとき，そのパスはハミルトンパスであり，パスの終点と始点を接続する枝が存在すればこのグラフはハミルトングラフである．

■入力点の入力枝，出力点の出力枝の除去はハミルトンタイ公準の２因子規則に関る操作であり，確定パス上の枝リストを閉路として閉じる枝の除去は，１閉路規則に関るものである．ハミルトングラフＧのすべての枝は，あるハミルトンタイ上の枝でなければ必ずこのハミルトンタイ上のあるパスを閉路として閉じる枝である．（ハミルトンタイは全域パスであるから，Ｇの任意の枝の両端点は必ずハミルトンタイの上にある）従って，１閉路規則がある特定の枝に適用されたということは，たまたま運用上そのようになったというだけのことであって，最終的にはハミルトンタイの上に無いすべての枝を規制するものである．

■任意選択局面で�@入力枝を持たない入力点，出力枝を持たない出力点が発生した状況，�A複数の単枝点に隣接する点が発生した状況をデッドロックと言う．デッドロックが発生したということは，そのグラフが非ハミルトングラフであるか，ないし確定パスに矛盾枝ないし障害枝が混入していることを示すものである．入力枝を持たない入力点，出力枝を持たない出力点を脱落点と呼ぶ．また，複数の単枝点に隣接する点を分裂点と呼ぶことにする．分裂点は確定パス上の合流点であるか分岐点であるかのいずれかである．脱落点はハミルトン公準の２因子規則の違反によって発生する．分裂点は１閉路規則に違反するものである．

■デッドロックは因子検定の任意選択局面においてある枝を任意選択する操作に関って発生するが，初期局面（確定パスの長さが０の場合）においてデッドロックが発生する場合も有り得る．初期局面において１因子以下の点が存在すれば，グラフは非ハミルトングラフである．これは因子検定において可能な唯一の無試行判定であり，連結でないグラフの一部を非ハミルトングラフとして検出することができる．因子検定では連結成分が２連結であるような非連結グラフを無試行判定によって分離することはできないが，確定パス上の枝リストを閉路として閉じる枝の除去によってデッドロックが発生するので，最終的には分離可能である．

■因子検定の無試行判定では，強連結グラフを分離することはできないが，グラフを強連結成分に分割する多項式時間アルゴリズムは存在するので，強連結検定として独立に実行することは可能である．２連結でないグラフは次節のＩＯ分割検定で非ハミルトングラフとして分離できる．

20 それ自身がひとつの初等的閉路であるようなグラフ．

21 無向グラフの任意の２点を結ぶ路が存在するとき，このグラフは連結であるという．

22 有向グラフの任意の２点ａ，ｂにおいて，点ａから点ｂに至る路と点ｂから点ａに至る路が存在するとき，強連結であるという．

23 任意の異なる２本の枝を通る初等的な閉路が存在するとき，２連結である，または非可分であるという．