１−４．クロスＩＯ矛盾が発生する

■短絡グラフ法は原理的に「幸運ならハミルトンタイを得られるだろう」という以外のものではあり得ないから，最終的には全数検査を行うことが必要となる．当たり前の方法（総当たりの方法）と短絡グラフ法で異なるところは，短絡グラフ法が「幸運を追いかけることができる」，つまり可能な限り収束を早めるための効果的な戦略を持っているという点にある．もし３種検定が完全なものであれば，�@グラフがハミルトングラフであるときは短絡グラフ法によって高速に解を得ることができる．�Aグラフが非ハミルトングラフであるときは３種検定によってそのことを判定できる，ということになるのだが，実際には３種のいずれの検定法によっても分離することのできない非ハミルトングラフが存在し，かつその範囲は広い．

■グラフＧのある部分グラフＧ' がＧのハミルトンタイであるためには，以下の規則が成立する必要がある．

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

■この２つの規則をハミルトンタイ公準と呼ぶことにしよう．また，グラフのすべての要素に対してある検定を適用したとき，規則１の違反を完全に検出可能な検定を十全な検定，規則１と２の違反を完全に検出可能な検定を完備な検定と呼ぶことにしよう．ｋ端子分割検定，カットセット検定，メッシュ図検定は規則２の違反を検出することができないが，短絡グラフ法と直並列検定は規則２の違反を検出可能である．検定グラフ法（短絡グラフ法）はこの意味で（コストを度外視すれば）完備な検定である．また，ｋ端子分割検定とカットセット検定の２つはもしグラフのすべての分割に対して適用されるならば十全な検定である．

■ｋ端子分割検定，カットセット検定の２つを総称してＩＯ検定とし，ｋ端子分割，カットセット分割をまとめてＩＯ分割と呼ぶことにする．また短絡グラフ法のベースとなる検定は因子検定と呼ばれる．因子検定は完備な検定であり，ＩＯ検定は十全な検定である．因子検定は完備な検定ではあるが，デッドロックを回避することはできないから完全な検定ではない．つまり，デッドロックが発生することによって確定パスに誤りがあることを事後に検出することは可能だが，事前にそれを予防することはできない．これはデッドロックという現象の非決定性にその原因があると考えられる．

■ＩＯ検定が十全な検定を充足するためには，すべてのｋ端子分割，すべてのカットセット分割についての検定を行うことが要求される．しかし，ｋ端子分割検定もカットセット分割も，コスト的な理由からそのすべての要素の検定を行うことはできないから，十全な検定を実施することは実用上不可能である．ところが仮に十全な検定が実施できたとしても，ＩＯ矛盾の発生することを回避できない場合が存在する．つまり，ＩＯ矛盾が発生することによって確定パスに誤りがあることを事後に検出することは可能だが，事前にそれを予防することはできない．これはＩＯ矛盾という現象の中にも非決定性が存在していることを示すものである．この非決定的な障害要因をクロスＩＯ矛盾と呼ぶ．

■複数のｋ端子分割が同一の端子点を共有する場合がある．このようなｋ端子分割をクロスする端子分割と言う．同様にカットセット分割の場合にも複数のカットセットが枝を共有する場合があり，これをクロスするカットセット分割と言う．クロスするＩＯ分割が存在するばあいには，クロスＩＯ矛盾の発生する可能性がある．クロスＩＯ矛盾には絶対不可避の矛盾と相対的な矛盾，つまり選択によっては回避可能な矛盾が存在する．グラフが避けることのできないクロスＩＯ矛盾を持っている場合には，そのグラフは非ハミルトングラフである．現在までのところ，絶対クロスＩＯ矛盾を検出する無試行判定法は開発されていない．

12 全域：spanning 原グラフのすべての点を含む部分グラフについて言う．

13 ２因子：2-factor 枝数が２であるような点を意味する．ｋ因子は通常，すべての点の枝数がｋであるような全域部分グラフを表わすが，この草稿ではｋ因子を枝数がｋであるような個別の点に適用する．

14 初等閉路：elementary circuit 同じ点を２度以上含まないような閉路．