１−２．ハミルトン閉路を持たないグラフ

■十全なｋ端子分割とカットセット検定を行うことができれば，ほとんど網の目を塞ぐことができると予想されたが，それはコスト的に不可能であるというジレンマに直面して，事態はほとんど打開不能であるように思われた．しかし，ここでｋ端子部分グラフのＩＯを調べるうち奇妙なことに気がついた．すなわち，「ある特殊な図形のクラスがあり，この図形を埋め込んだグラフは必ず非ハミルトングラフになってしまうということがあり得るのではないか？」という疑問が出てきた．もし，そのような図形があるとしたら，それは悪魔の図形とでも呼ぶしかないだろう．理論的に考えるとそのようなグラフが存在し得る可能性は十分あるように思われた．我々はそのような性質を持った一群の図形を発見し，それにダイアモンド図形という名称を与えた．

■グラフがハミルトン閉路を持つか持たないかというのはグラフの大域的特性に関る問題であり，局所的情報のみから判定することは一般には不可能である．実際，非ハミルトングラフにいくつかの点と枝を付け加えればハミルトングラフになり，さらにいくつかを追加することで非ハミルトングラフに戻すことができる．ところがダイアモンド図形の場合，それを埋め込まれたグラフは例外なく非ハミルトングラフになる．この図形の性質はそれが巨大なグラフ中のけし粒ほどの存在であったとしても，必ずそのグラフ全体を非ハミルトングラフにしてしまうという点で極めて特異なものである7．

■ダイアモンド図形の発見は完全な閉塞状態にあった我々にとって大きな転機となった．これは始めてハミルトン閉路を持たないグラフの実例を具体的に示すものであった．これによって，もしかすると全数検査を行わなくとも「非ハミルトングラフであること」を判定することができるのではないか，という希望が生まれてきた．

■ダイアモンド図形（を埋め込まれたグラフ）の次に発見された典型的な非ハミルトングラフは，左メッシュグラフないし奇数点メッシュグラフと呼ばれるものである．ここでは囲碁の盤面のように方形の升目からなるグラフをメッシュグラフと呼んでいる．囲碁の盤面は１９行×１９列だから３６１点グラフであり，点数が奇数だから左メッシュグラフである8．左メッシュグラフが非ハミルトングラフであることはグラフのカットセットＩＯがつねに偶数でなくてはならないことを用いて簡単に証明することができる．

■左メッシュグラフについての考察から，非ハミルトングラフであることを試行すること無しに判定することのできる初めての方法として，メッシュ図検定法が導入された．メッシュ図検定では点スコアと枝スコアと呼ぶ２種類の数値が計算され，これらの変数の間に成立する制約不等式から，ある範囲のグラフが非ハミルトングラフであることを判定することができる．

■ハミルトン閉路問題に関する基本定理の一つとしてハミルトン閉路の存在定理[1]がある．これは任意の２点の枝数の和がＮ以上のグラフはハミルトングラフであることを示すものである．このようなグラフを過密グラフと呼ぶことにするとすれば，それと対照的なグラフとして過疎グラフを考えることができる．当然に「過疎グラフは非ハミルトングラフである」と予想されるが，実際メッシュ図検定の方法から次のことが帰結される．「極大な独立集合の点数がＮ／２より大きいグラフは非ハミルトングラフである」．ここで独立集合とは互いに隣接しない点の集合であり，これはグラフの半分以上の点が互いに疎遠であるようなグラフは非ハミルトングラフであることを示すものである．

■「非ハミルトングラフであることを試行すること無しに判定する」ことのできるもうひとつの方法として直並列検定法が開発された．直列枝とは隣接した分岐のない２本の枝であり，２本の枝の接続点は２因子点（接続する枝数が２個）になっている．２因子はつねにハミルトンタイ上の枝であるから，直列枝はつねにハミルトンタイに含まれる．グラフの中に存在する直列枝はこの意味でグラフのトポロジーを決定する重要な要素であり，直並列検定はこの事実を利用して非ハミルトングラフの無試行判定を行うものである．

■直並列検定では，直列枝のみのループ9を含むグラフ，３並列直列グラフ（３本の直列枝が１点を共有するグラフ）をともに非ハミルトングラフとして分離することができる．ｋ端子分割ないしカットセット分割も直並列矛盾と類似した非ハミルトングラフを検出する．ｋ端子分割で分割された部分グラフが同一の端子点でさらにｋ端子分割される場合などがこれに当たる．前にも述べたようにダイアモンド図形を含むグラフはｋ端子分割のＩＯ矛盾として検出される．これと同様に，ｋ端子分割およびカットセット分割でＩＯ矛盾を検出したグラフはすべて非ハミルトングラフである．

7 一般にｋ端子分割の片側だけの検定（突き合わせを行なう前の検定）でＩＯ矛盾を発生する部分グラフはダイア図形と同じ性質を持っているから，ダイアモンド図形という呼称はある程度趣味的なものではある．従って，我々がダイアモンド図形と考えている図形はむしろ，ある無試行判定の方法によってこの図形を検出できるというところにその特徴があると言ったほうが正確であるかもしれない．

8 偶数点方形メッシュグラフを右メッシュグラフ，奇数点方形メッシュグラフを左メッシュグラフと呼んでいる．将棋の盤面は１０×１０＝１００点で偶数点だから右メッシュグラフである．右メッシュグラフは完全ハミルトングラフであると考えられる．

9 グラフ理論では閉路と言うべきところだが，プログラミングの世界の慣用に従ってこの草稿ではループという用語を使っている場合がある．グラフ理論では自己参照する枝をループと呼んでいる．