２−３．メッシュ図検定

■ＩＯ検定がある分割におけるベクトルの分布に注目した微分的な方法であるとすれば，メッシュ図検定はそれらを積分的に解析する方法であると言えるかもしれない．この検定ではグラフの点に＋と−のポイントを与え，グラフの枝集合をその端点のポイントによって，＋＋の枝と＋−の枝，および−−の枝の３種に区分する．＋＋の枝を右枝，＋−ないし−＋の枝を直枝，−−の枝を左枝と呼んでいる．メッシュ図検定のインプリメンテーションには色々なバリエーションが考えられるが，以下に一例を提示する．

(1) グラフＧの独立集合（互いに接続する枝を持たない点の集合）をＳとする27．もしＳ＝φならば，グラフＧは完全グラフだから停止する．

■Ｓのすべての点に＋１の点ポイントを与える．

(2) Ｓに属さないＧの残りの点に−１の点ポイントを与える．

(3) Ｇのすべての枝の枝ポイントを求めて，直枝，右枝，左枝に区分する．枝ポイントは枝の端点のポイントの和であり，＋２，０，−２のいずれかである．ところが＋１の点ポイントを持つ点はすべて独立集合の点であるから，これらを相互に接続する枝は存在しないので＋２の枝ポイントを持つ枝は有り得ないことになる．つまり，このメッシュ図の枝はすべて直枝であるか，左枝であるかのいずれかである．

(4) グラフＧのすべての点ポイントを加算してＧの点スコアｓ，直枝の本数ｄと，左枝の本数ｅを求める．

(5) もし，ｓ＞０ならばグラフＧは非ハミルトングラフである．

(6) もし，d＜Ｎ−|ｓ| ならば，グラフＧは非ハミルトングラフである．

(7) もし，ｅ＜|ｓ| ならば，グラフＧは非ハミルトングラフである．

■メッシュ図検定の無試行判定により，次の非ハミルトングラフを分離することが可能である．

�@ 過疎グラフ：互いに疎遠な点の個数が親密な点の個数より多いグラフ

�A 劣疎グラフ：ハミルトンタイで必要な直枝（疎遠な点と親密な点を接続する枝）の本数は（Ｎ＋疎遠な点の個数−親密な点の個数）に等しい．直枝の本数がこの値に足りないグラフは非ハミルトングラフである．

�B 劣密グラフ：ハミルトンタイで必要な左枝（親密な点と親密な点を接続する枝）の本数は（親密な点の個数−疎遠な点の個数）に等しい．左枝の本数がこの値に足りないグラフは非ハミルトングラフである．

■これらのグラフが非ハミルトングラフであることは，パスの枝スコアと点スコアの間に成立する以下の関係式から導かれる．また，点スコアと枝スコアおよび確定パスに割り当て可能な直枝数，左枝数の制約条件から自動確定ないし，除去されるべき枝を決定することができる．

メッシュ図上のパスのスコアをパスに含まれる点ポイントの和であるとすると，パス上の枝のポイントは両端点のポイントの和であるから，以下の式が成立する．

--------- �@

■閉路のスコアはパスの始点と終点が重複したものと考えられるから，�@式より，


■従ってハミルトンタイのスコアはグラフのすべての点のスコアであるから，

が成立する．従って確定パスの枝スコアをチェックすることで，メッシュ図上の制約条件を充足可能であるか否かの判定を行なうことができる．上記のような右枝数＝０となるようなメッシュ図の場合であれば，点スコアの絶対値|ｓ|はハミルトンタイ上で必要となる左枝の本数を示すものである．また，このときＮ−|ｓ|本の直枝が必要となる．

定理2-3.1: メッシュ図判定規則

グラフＧ＝（Ｖ，Ｅ）の独立集合の点セクション部分グラフ28をＳとし，Ｇの部分グラフＵ＝Ｖ−Ｓであるとする．ここでＳの各点に＋１の重みを与え，Ｕの各点に−１の重みを与える．Ｇのすべての点の重みの和をｓ，ＳとＵの点を接続する枝の本数をｄ，Ｕの点同士を接続する枝の本数をｅとしたとき，以下のいずれかであればグラフＧは非ハミルトングラフである．

(1) ｓ＞０

(2) d＜Ｎ−|ｓ|

(3) ｅ＜|ｓ|

証明： 上記の説明により明らかであるとする．

補題2-3.1: 左メッシュグラフ

グラフＧの点数Ｎが奇数で，かつＧが方形メッシュグラフであるならば，Ｇは非ハミルトングラフである．ここで方形メッシュグラフとは平面グラフであって，ｍ×ｎ個の方形な領域を整列したものである．

証明：

グラフＧの各点に＋１と−１の重みを割り当てる．このときグラフは方形メッシュグラフであるから，隣接する点の重みがつねに異なる値を取るように割り当てることができる．このとき，各点の重みの和は点数が奇数であることから必ず非零数となる．ここで，枝の重みを端点の重みの和とすればすべての枝の重みは０である．Ｇのハミルトンタイの点の重みの和＝（ハミルトンタイの枝の重みの和）÷２＝０となり矛盾する．よってグラフＧはハミルトンタイを持たない．

27 メッシュ図検定はあるグラフが非ハミルトングラフであることを無試行判定可能だが，その効果は選択された独立集合に依存する．極大な独立集合が必ずしも最善であるとは言えない．

28 点集合によって定義される部分グラフ．その部分グラフの枝集合が点集合の点を両端とする枝の全体からなるものをいう．