２−２．ＩＯ分割検定

■ＩＯ分割検定には�@ｋ端子分割検定と�Aカットセット検定の２種がある．いずれもグラフを右部分グラフと左部分グラフに２分割し，２つの部分グラフ間のインタフェースの検査を行うことにより，ハミルトンタイ公準の２因子規則違反を未然に防止することができる．また，分割された部分グラフの接合部をクリークの枝によって閉じた蓋付き部分グラフを対象に検定を再帰的に実行することによって，検定コストの劇的な減少をもたらす効果がある．

定義2-2.1:ｋ端子分割

連結なグラフのある点集合を除去したとき，グラフが２つの部分グラフに分離されるような点集合のうちの極小な点集合を端子点セットとすれば，ｋ端子分割はｋ個の点からなる端子点セットを接合部とするグラフの分割である．

ｋ端子分割ではグラフの枝は分離された２つの部分グラフのいずれかに属するものとする．端子点を連結する枝も任意にいずれかの部分グラフに振り分ける．

定義2-2.2:カットセット分割

同様にカットセット分割は，除去することによって連結なグラフを２つの連結成分に分離するような枝集合のうちの極小な枝集合をカットセットとしたとき，カットセットを接合部とするグラフの分割である．

■ハミルトンタイを１つの還流する水路であると考えると，右部分グラフから流入した水流は必ず左部分グラフから流出しなくてはならないから，グラフ分割の接合部では必ず同数の流入と流出が存在しなくてはならない．このことから，ｋ端子分割検定では以下のような検定を行なうことができる．

(1) もし，端子点が奇数個あるとしたら，少なくともそのうちの１個は閉塞点である．ここで閉塞点とは，接合部を通過する水流の存在しない点を言う．従って，閉塞点に接続する（ハミルトン閉路の）枝は右ないし左部分グラフのいずれか一方にのみ属することになる．

(2) 接合部において，通路点の個数は偶数個でなくてはならない．また，それらの点を通過する水流の向きは左右同数でなくてはならない．通路点とは右ないし左部分グラフの一方に流入枝を持ち，他方に流出枝をもつような端子点を言う．

(3) 端子点に接続する枝が確定ないし，除去されることによってこれらの制約条件がタイトになってくると，その制約に従って該当する枝を自動的に確定ないし除去することができる．

■同様にカットセット検定では以下のような制約条件にもとづいて検定を行なう．

(1) もし，カットセットの枝が奇数本あるとしたら，少なくともそのうちの１本は閉塞枝（矛盾枝ないし障害枝）である．

(2) ハミルトンタイと交わるカットセットの枝数は偶数本でなくてはならない．またこれらの枝は一方の部分グラフから見て流入枝と流出枝の本数が同数でなくてはならない．流入枝と流出枝を合わせて，通路枝と呼ぶ．

(3) カットセットの枝が確定ないし，除去されることによってこれらの制約条件がタイトになってくると，その制約に従って該当する枝を自動的に確定ないし除去することができる．

■通路点ないし通路枝の個数は偶数でなくてはならないという条件は，因子検定の手順における自動確定や除去の規則よりも強い規則であり，因子検定では検出不能な段階にある潜在的矛盾をＩＯ矛盾として未然に検出することができる．ｋ端子分割検定では２連結でないグラフを無試行判定により検出できる．カットセット検定も２連結でないグラフの一部を無試行判定により検出する．

■いずれの分割検定によってもグラフを２分割して部分検定を進めることは可能だが，接合部の要素数から考えるとｋ端子グラフ分割の方が有利であるようにも思われる．