1−3.k端子分割困難なグラフがある
■メッシュ図検定は,無試行判定によって非ハミルトングラフを検出することのできる初めての方法となったが,この方法を開発する直接のきっかけとなったのはk端子分割困難なグラフがあるという事実だった.つまりk端子分割で左右部分グラフの確定パスを突き合わせるためのコストは端子点の個数をkとするとk!になるから,大きなkに対してほとんどそれはN!に近いものとなってしまう.k端子分割は再帰的に実行されるから,あるグラフのk端子分割を行うときはつねにそのグラフの極小なk端子分割を対象とすればよいことになるので,k端子分割困難なグラフとは,グラフの極小なk端子分割を与えるkの値がある定数値,たとえば20を越える10ようなグラフである.
■メッシュグラフはまさにこのようなグラフの実例であった.たとえばm×mメッシュグラフの場合,点数はN=m^2となるからグラフを縦断ないし横断する端子分割ではk=となり,k端子分割困難である.(方形メッシュグラフの場合,メッシュ図の4隅にはより小さいk端子が存在しているからリンゴをかじるように小さいkによる端子分割を進めることも可能だが,メッシュグラフの中にはまったくk端子分割困難なグラフが存在する.)k端子分割検定はきわめて高速に収束する強力な手法であったから,その方略で歯が立たないグラフに対しては,別の戦術を考えるしか方法が無かった.
■グラフのトポログラフィーから見ると,極小なk端子分割を与えるkの値はそのグラフの短径と考えてもよいだろう.つまりk端子分割困難なグラフとはウエスト周りの大きい寸胴肥満型のグラフである.正準な右メッシュグラフ(欠けた枝のない偶数点メッシュグラフ)は完全ハミルトングラフ11である.左メッシュグラフも非ハミルトングラフではあるが,1点を任意に追加ないし削除して偶数点メッシュグラフに変更することで,ハミルトングラフに変えることができる.k端子分割検定から考えると途方もなく困難なグラフであったメッシュグラフも,メッシュ図の上に乗せてみると意外に扱いやすいグラフであることが分かった.
■直並列検定,メッシュ図検定,k端子分割検定の3種類の検定を併用する検定の方法を3種検定と呼ぶ.3種の検定はそれぞれの判定規則によって非ハミルトングラフを分離することができる.あるごく一部のグラフは3種の検定のすべてで非ハミルトングラフであると判定される.あるグラフは2つの検定法から,非ハミルトングラフであるとの判定を受ける.しかし,いずれの検定法によっても分離することのできない非ハミルトングラフも存在する.直並列検定とメッシュ図検定は無試行判定法を持っているから,即時に判定を下すことができる.k端子分割検定は分割されたグラフを再帰的に検定するという方法だから即時判定を行うことは,原理的に不可能である.ダイアモンド図形は即時判定可能であり,これはk端子分割検定で無試行判定が可能となるような例外である.
10 k=20のときk!は,10^18 のオーダーの値になる.これは現在の最高速のコンピュータを使って計算してもおそらく10日以上かかるだろう.
11 任意の枝を通るハミルトン閉路の存在するグラフ