２－２－１．ｋ端子分割検定

２－２－１．ｋ端子分割検定

■グラフをｋ端子セットによって分割検定する手順は次のようなものとなる．

(1) 分割された部分グラフの枝数ないし点数の少ない方のグラフを右部分グラフと仮定する．端子点同士を連結する枝は，左部分グラフに属するものとする．

(2) まず，右部分グラフの検定を行なう．このとき，右部分グラフの接合部に蓋ないし蓋枝集合と呼ばれる枝集合の枝を追加する．このようにして右部分グラフから得られる作業用グラフを蓋付き部分グラフと呼ぶ．ここで，蓋ないし蓋枝集合とは端子点セットの各点を相互に連結する枝の集合であり，これは端子点集合の各点を点集合とするクリークの枝集合である．

(3) 右部分グラフの検定は蓋付き右部分グラフのハミルトン閉路を求めることにより行う．ただし，このハミルトン閉路には，端子点集合の点の一部は含まれていなくともよい．これは，そのような点が左部分グラフの閉塞点として救済される可能性があるからである．従って，求めるべきハミルトン閉路は端子点集合の点を偶数個含む右部分グラフの全域閉路であるということになる．

(4)右部分グラフの検定でロックアウトした場合にはこの右部分グラフはｋ端子を接合部とするダイアモンド図形であり，対象グラフは非ハミルトングラフである．

(5) 蓋付き右部分グラフのハミルトン閉路から，蓋の枝を除去して得られる全域部分枝集合をハミルトン通路24と呼ぶ．ハミルトン通路を閉じている蓋の枝集合を左代替枝集合と呼ぶ．左代替枝集合は空であってはならない．もし，左代替枝集合が空でないような右ハミルトン通路を求めることができないとすれば，この右部分グラフは，ｋ端子を接合部とするダイアモンド図形であり，対象グラフは非ハミルトングラフである．

(6) 右ハミルトン通路を代替する蓋の部分枝集合を右代替枝集合と呼ぶ．左部分グラフの検定は，左部分グラフの接合部に右代替枝集合の枝を追加した作業用グラフを求め，このグラフのハミルトン閉路を求めることによって行う．

(7) 左部分グラフの検定に成功すれば，グラフはハミルトングラフであり，左右のハミルトン通路を合併することにより，ハミルトンタイを得ることができる．

(8) 左部分グラフの検定が不成功に終わった場合は，ＩＯ接合部の枝の組み合わせを全数検定しなくてはならない．新たな右ハミルトン通路が得られた場合には，そのインタフェースに合わせて左部分グラフの検定を行なう．

(9) 新たな右ハミルトン通路が得られない場合には，このグラフは非ハミルトングラフである．新たなハミルトン通路とは，右代替枝集合が異なるものであることを意味する．ハミルトン閉路としては異なっていたとしても，右代替枝集合が同一である場合には却下される．

(10) 右ハミルトン通路に対応する左ハミルトン通路を得られれば，グラフはハミルトングラフであり，左右のハミルトン通路を合併することにより，ハミルトンタイを得ることができる．

(11) すべての場合を尽くして右ハミルトン通路に対応する左ハミルトン通路を得ることができない場合は，このグラフは非ハミルトングラフである．

■この検定法では，右部分グラフの検定および，左部分グラフの検定それ自体がハミルトン閉路を求める問題として提示されるから，完全に再起的に実行可能であることは明らかである．いずれにせよ，検定対象となる蓋付き部分グラフのハミルトン閉路から得られる右代替枝集合が空でないこと，つまり蓋枝集合の枝がそのハミルトン閉路に含まれていることが必要である．これは，その部分グラフがダイアモンド図形でないことを意味するものである．

■ここで，ＩＯ接合部の枝の組み合わせを全数検定するということは，右ハミルトン通路に対応したｋ点クリークの１因子部分グラフ，つまり左代替枝集合の族を列挙することに等しい．これは右蓋付きグラフのハミルトン閉路を列挙することに当たる．この部分検定の個数は要素数ｋの集合から偶数個の要素を取り出す組み合わせの個数である．

■グラフのハミルトン閉路を列挙する問題はハミルトン閉路を１個見つけるという我々の問題より計算コストを要することは明らかであるから，右部分グラフのサイズが十分小さくない限り，この検定は成立しない．ｋが十分小さい場合には，場合の数はおのずと制限されたものとなるので，この計算が現実的なものとなる可能性はあると言える．

■右ハミルトン通路のインタフェースに合わせて左ハミルトン通路を求める計算は，右代替枝集合の枝を左部分グラフに追加して，そのハミルトン閉路を求める計算に等しい．従ってもし，左部分グラフが十分大きいときには，この計算自体がＮＰ完全となることを避けることはできない．（ここではＮＰ＝Ｐであるか否かを問うているのではない）

■もし，右部分グラフが十分小さいものであることが必要であるとすると，左部分グラフが大きなものとなることは避けられないから，この計算が適用できる例題はかなり限られたものになると推定される．ｋ端子分割検定が再帰的に実行されるものであるとすると，グラフをほぼ中央で分割するような分割がもっとも高速に収束する例題になるように思われるが，Ｎが十分大きいとき，Ｎ÷２が十分小さい数になると言えるかどうかは疑問である．

■部分検定において，つねに十分小さいｋと十分小さい右部分グラフが供給可能な場合には，左部分グラフのサイズは線形に減少してゆくことになるので，大雑把に言って，ｋ×Ｎ ×ｃのオーダーで計算が完了することが期待できる．（ｋ，Ｎはそれぞれｋ，Ｎの多項式関数，ｃは定数）ここで右部分グラフは，そのすべてのハミルトン通路を列挙しても，つねに定数ｃのオーダーで計算完了可能な程度に小さいものであり，列挙されるハミルトン通路の個数はｋのオーダーであると前提する．

■右部分グラフのサイズが十分小さいものとならない場合，計算木は大雑把に高さがＮのオーダーの２分木になると考えられるので，計算木全体のコストが指数的になることは避けられないと考えられる．

■一般のグラフの中には，十分小さなｋを得ることのできないグラフないし，十分小さい右部分グラフを得ることのできないグラフが存在していることは明らかだから，ｋ端子分割の方法を一般に適用することは不可能である．従って，ｋ端子分割ないしカットセット分割が応用されるべき局面は，因子検定におけるヒューリスティックスに限定されることになるのではないだろうか？因子検定には通路点や通路枝の偶数規則のようなものは含まれていないので，これらを導入することによって，因子検定を加速することは可能である．

■すべてのｋ端子ないしカットセットを列挙して検定することができれば，完全なｋ端子分割検定ないしカットセット検定を実現することができると考えられるが，問題は，複数のｋ端子分割ないしカットセットが端子点ないしカットセットの枝を共有する場合があるというところにある．我々はこれをクロスするＩＯ分割と呼び，それに起因する矛盾の発生をクロスＩＯ矛盾と呼んでいる．我々は現在までのところ，絶対クロスＩＯ矛盾（回避不可能なクロスＩＯ矛盾）を検出する無試行判定法は開発されていないと考えている．

■連結なグラフを分割するカットセットは定義によりつねにグラフを２つの連結成分に分割する．なぜなら，もしこのカットセットが２個よりも多い連結成分を分離するとすれば，カットセットの枝の中には，これらの成分のうちのいずれか２つを連結する枝が必ず存在するはずであるから，その枝をカットセットから除去することにより，より小さいカットセットを得ることができる．つまり，このカットセットはより小さいカットセットをその真部分集合として含むことになるので，定義により，カットセットではない

■ｋ端子分割はこれに対し，グラフＧを３個以上の連結成分に分離する場合が有り得る．しかし，我々のｋ端子分割検定では，これらの連結成分を２つのグループに集約して２つの部分グラフとして扱うことが可能であるから，グラフＧを２つの（必ずしも連結でない）成分に分割するようなｋ端子分割が正当なものであることを証明できれば十分である．以下の定理はカットセット検定とｋ端子分割検定の正当性を保証するものである．

定義2-2-1.1：半点グラフ

Ｎ点有向グラフＧの点を分割して，一方を入力半点，他方を出力半点とする．但し，入力枝を持たない入力半点および，出力枝を持たない出力半点は生成されない．これによってグラフＧから派生するグラフＧ' |Ｇ'|≦２ＮをグラフＧの半点グラフと呼ぶ．半点グラフでは，点数はＧの２倍になるが，枝数は同じである．

半点グラフ上のパスは出力半点→入力半点←出力半点のように，つねに枝の向きが交互に反転するので，半点グラフは一種の交代グラフである．有向グラフＧ上の閉路Ｃは定向であるから，半点グラフ上では１因子部分グラフとなる．

定義2-2-1.2：カットセット通路枝

連結なグラフＧの初等的な閉路と任意のカットセットが共有する枝をその閉路のカットセット通路枝と呼ぶ．定理2-2-1.1により，通路枝の個数は偶数である．

定義2-2-1.3：ｋ端子通路点

連結なグラフＧの初等的な閉路Ｃと任意のｋ端子点集合Ｋが共有する点のうち，その点に接続する閉路Ｃの２本の枝がＫによって分割された左右部分グラフの両方にそれぞれ含まれるような点を，その閉路のｋ端子通路点と呼ぶ．通路点の個数は定理2-2-1.2により偶数である．

定理2-2-1.1: 偶数通路枝規則

有向グラフＧを２つ連結成分に分割するカットセットＳにおいて，Ｇの単純閉路25ＣはＳと偶数個の枝を共有する．

証明：

グラフＧの半点グラフをＧ'とし，閉路Ｃの点が右連結成分に属するときにはその半点を黒で塗り，左連結成分に属するときには白で塗ることにする．閉路ＣとカットセットＳが共有する枝はすべて，Ｇ'上で白と黒の半点を持っている．

入力半点白，出力半点黒のＳの枝で右連結成分に入った閉路Ｃのパスは入力半点黒，出力半点白のＳの枝で左連結成分に戻らなくてはならないから，これら，白黒，黒白の２個の通路枝はつねに対をなしていると見ることができる．よって通路枝の個数は偶数である．

定理2-2-1.2: 偶数通路点規則

有向グラフＧを２つの部分グラフに分離するｋ端子分割Ｋにおいて，初等的な閉路ＣとＫが共有する点のうち，その点に接続する閉路Ｃの２本の枝が左右部分グラフの両方に含まれるような点の個数は偶数である．ただし，端子点同士を連結する枝は左右部分グラフのいずれかに属するものとする．

証明：

グラフＧの半点グラフをＧ'とし，閉路Ｃの枝が右部分グラフに属するときにはその両端の半点を黒で塗り，左部分グラフに属するときには白で塗ることにする．

入力半点白，出力半点黒のＫの点で右部分グラフに入った閉路Ｃのパスは入力半点黒，出力半点白のＫの点で左部分グラフに戻らなくてはならないから，これら，白黒，黒白の２個の通路点はつねに対をなしていると見ることができる．よって通路点の個数は偶数である．

■偶数通路枝および偶数通路点の２つの定理はカットセットおよび，ｋ端子分割が必ずしも極小な枝集合ないし点集合でない場合にも成立する．また，無向グラフの場合も，閉路Ｃの枝に適当な向きを与えることにより，上記と同様に証明することができる．

■ｋ端子分割の構成には次のような２つの任意性があることに注意する必要がある．①端子点同士を連結する枝の所属は任意である．②グラフが３以上の連結成分に分割される場合，グラフを２つの部分グラフに分離する方法には任意性がある．

■①の場合，端子点を連結する枝の所属の如何によって，通路点の位置は変化する．（この変化は名義的なものである）．しかし，通路点の個数が偶数であるという条件は不変である．

■②の場合，２つの部分グラフに分離する連結成分の組み合わせは任意であり，そのそれぞれの場合について通路点が決定されることになるから，これら異なる部分グラフ構成によって得られる通路点を併合して得られる点集合の要素数，つまり全体として見たときの通路点の個数は必ずしも偶数にならない場合がある．

■これらは上記したクロスするＩＯ分割の現象に多少なり類似するものである．これらをもう少し厳密に扱うために，以下の定義を導入する．

定義2-2-1.4：カットセットに接続するｋ端子分割

連結なグラフＧのカットセットＳがＧを２つの連結成分に分割するとき，Ｓの枝の一方の端点は右連結成分に含まれ，他方の端点は左連結成分に含まれる．Ｓの枝の端点のうち，右ないし左連結成分に含まれる点の集合は，明らかに１個のｋ端子分割を構成する．これを，カットセットＳに接続するｋ端子分割と呼ぶ．あるカットセットに接続するｋ端子分割の個数は高々２個である．

定義2-2-1.5：ｋ端子に接続するカットセット

連結なグラフＧのｋ端子分割ＫがＧをｍ個の連結成分に分割するとき，Ｋの端子点に接続する枝は，端子点といずれかの連結成分中の点を連結するもの，端子点同士を連結するものの２種に区分することができる．これらの枝のうち，ある連結成分と端子点を連結する枝の集合は，明らかに１個のカットセットを構成する．これをｋ端子分割Ｋに接続するカットセットと呼ぶ．

あるｋ端子に接続するカットセットの個数は，ｋ端子分割によって分離される連結成分の個数ｍに等しい．Ｋに接続するカットセットＳはＫの端子点同士を連結する枝を含まない．

定理2-2-1.3: ｋ端子分割と連結成分

連結なグラフＧの任意のｋ端子分割によって分離される連結成分の個数は，ｋ端子に接続するカットセットの個数に等しい．

証明：

グラフＧのｋ端子分割Ｋによって分離されるひとつの連結成分をＣとする．ＣとＫを連結しているすべての枝を除去することによって，Ｇは２つの連結成分に分割され，またこれらのすべての枝を除去しない限り分割されないから，これらの枝はＧのひとつのカットセットを構成する．

このカットセットＳのＫ側の端点集合Ｋ'はＫの端子点集合の部分集合である．Ｋ'のすべての点を除去することによってＧは２つの部分グラフに分離されるから，もし，Ｋ'がＫの端子点集合の真部分集合であるとすれば，定義により，Ｋ'は１個の端子分割であり，かつ，Ｋは端子分割ではないということになり矛盾する．従ってＫ'はＫに一致しなくてはならない．

また，このカットセットはＫの端子点を連結する枝を含まないから，Ｋに接続するカットセットであり，ｋ端子分割によって分離される連結成分とｋ端子に接続するカットセットは一対一に対応して，その個数は等しい．

定理2-2-1.4: ｋ端子・カットセット接合

連結なグラフＧのカットセットＳに接続するｋ端子分割をＫとするとき，Ｓはｋ端子分割Ｋに接続するカットセットであり，その逆も成り立つ．

証明：

カットセットＳの枝の端点のうち，右連結成分に含まれる点の集合をＫとする．Ｋのすべての点を除去することによって，グラフＧはふたつの部分グラフに分離され，また，これらすべての点を除去しなければ分離されないから，Ｋはｋ端子分割であり，定義によりカットセットＳに右側で接続している．

ＫがグラフＧをｍ個の連結成分に分離するとき，カットセットＳの左連結成分Ｌはこれらの連結成分のうちの１つであり，Ｓのすべての枝の一方の端点はＬにあり，他方の端点はＫの端子点である．もし，ＳがＫの端子点を連結する枝を持っているとすると，Ｓからこれらの枝を除去することによって得られる枝集合もカットセットを構成することになるから，定義に反する．よって，ＳはＫの端子点を連結する枝を持っていない．よって，カットセットＳはｋ端子分割Ｋに接続するカットセットである．

同様にカットセットＳがｋ端子分割Ｋに左側で接続するとき，定理2-2-1.3の証明からＳの枝の右側端点集合はＫの端子点集合に一致する．よってＳがＫに接続するカットセットであるとき，ＫはＳに接続するｋ端子分割である．

定義2-2-1.6：ＩＯ接合マップ

連結なグラフＧのすべてのｋ端子分割とカットセットを点集合とするグラフＨにおいて，あるｋ端子分割とカットセットが互いに接続しているとき，これら２点を結ぶ枝をＨの枝とする．定理2-2-1.3により，このような無向グラフＨをグラフＧによって一意に定めることができる．このグラフＨをＧのＩＯ接合マップと呼ぶ．

ＩＯ接合マップＨ上のパスはｋ端子分割の点とカットセットの点が交互に現れる交代路であり，Ｈは一種の交代グラフである．また，カットセットの点の枝数はつねに２以下である．

■あるｋ端子分割Ｋが存在するとき，Ｋの端子点に接続する枝集合の枝の組み合わせによっては，Ｋに接続するカットセット以外のカットセットを得ることができる場合もある．同様に，あるカットセットＳが存在するとき，Ｓの枝の両端点集合に含まれる点の組み合わせによっては，Ｓに接続するｋ端子分割以外のｋ端子分割が得られる場合もあり得る．

■つまり，端子分割Ｋないし，カットセットＳの周辺に存在するＩＯ分割には，かなりの任意性が存在する．しかしこれらは，ＩＯ接合マップ上ではＫないしＳとは接続しない異なる場所に位置することになるから，ＩＯ接合マップの一意性は保証される．

■ＩＯ接合マップのフォーメーションは非常に興味深いものであるが，我々はまだこの方面における深い探求を行っていない．カットセットと閉路がマトロイドと呼ばれる双対的な特性を持っていることは知られているので，ｋ端子分割がそれらとどのように関わっているのかを探ることが課題になってくるのではないだろうか？

24 ハミルトン通路．初等的な全域パス集合．ここで求めているのはハミルトンタイの右半分を占める確定枝集合である．実際の手続きは右部分グラフの接合部を縫合する枝によって閉じたグラフのハミルトンタイを求める検定として行われる．

25 単純閉路：simple circuit 同じ枝を２度以上含まないような閉路．

26 証明は[1]による．