2-3. Mesh-diagram Experiment


If IO experiment is a differential method paying attention to the distribution of vectors on a graph division, it might be said that mesh-diagram* experiment is a method to analyze them integrally. In this experiment, we give + or - value to points of graph and classify branches set of the graph into 3 kinds of branches as ++ branch, +- branch, and -- branch according to values of both terminal points of each branch. We call ++ branch by right branch, +- branch or -+ branch by strait branch and -- branch by left branch. While it is possible to implement mesh-diagram experiment in various variations, the most efficient specification in separability is experimentally such a simple method as below**.

(1) Let the independent set (points set having no branches adjacent to each other) of maximum points of graph G be S. If S=then graph G is a complete graph, halt.
(2) Give every point of S point value +1, and other points than S of G point value -1.
(3) Get every branch value of G and classify them into right branch, strait branch and left branch. Branch value is a sum of terminal point's values of the branch and the value is one of +2, 0, and -2. Hereon, since any point having point value +1 is all a point of independent set, then there is no branch to conjoin these point each other then a branch having branch value +2 does not exist. In other words, in this mesh-diagram, every branch is either a strait branch or a left branch.
(4) Total all points of graph G and obtain points score of graph G s, strait branches number d and left branches number e.
(5) If s > 0 then graph G is a non-Hamiltonian graph.
(6) If d < N - |s| then graph G is a non-Hamiltonian graph.
(7) If e < |s| then graph G is a non-Hamiltonian graph.


On the judgment with non-retrial of mesh-diagram experiment, the following non-Hamiltonian graph can be separated.

That these graphs are non-Hamiltonian graphs is induced by the equations holding between branches score of paths and points score. Moreover, From the constraint conditions on points score, branches score and possible number of strait / left branches to assign determinative paths, we can decide branches to be auto-determined or removed.

Let path score on a mesh-diagram be total of point values included in the path. Since a branch value on a path is a sum of values of both terminal points, the following equation holds.

Supposing that circuit score comes putting the end point upon the start point of the path, from equation (1),

Then, score of Hamiltonian tie is score of all points of the graph. Hence

holds. Therefore by checking a branches score of determinative paths, we can judge whether constraint conditions on the mesh-diagram are able to be satisfied or not. In the case of such mesh-diagram depicted above that right branches number = 0, the absolute value of points score |s| represents left branches number necessary on a Hamiltonian tie. Further, when N - |s| strait branches come to be necessary.


Theorem 2-3.1. mesh diagram judgment rule

Let point-section subgraph of independent set of graph G = (V, E) be S. Let subgraph of G be U = V - S. Hereon give each point of S weight (+1), and give each point of U weight (-1). Let total of weights of all the points of G be s, branches number conjoining points of S and points of U be d, branches number of conjoining points of U each other be e, where if one of the following conditions is true then graph G is a non-Hamiltonian graph.

(1) s > 0
(2) d < N - |s|
(3) e < |s|


Proof.

It is almost obvious with above explanation.


Lemma 2-3.1. left mesh graph

If points number of graph G is odd and G is a square mesh graph then G is a non-Hamiltonian graph. Where, a square mesh graph is a planar graph and it has m*n arranged square domains


Proof.

Assign weight of each point of graph G +1 or -1. When the graph is a square mesh graph then we can make such assignments that weights of adjacent points take always different values. Hereon total of weights of every points surely comes to be non-zero number because number of points is odd. Let weight of branch be sum of weights of it's terminal points then every weight of branch is equal to 0. Therefore (total of weights of points of Hamiltonian tie of G) = (total of weights of branches of Hamiltonian tie) / 2 = 0, a contradiction. Hence graph G has no Hamiltonian tie.

* Mesh diagram is not a class of graphs, but we sometimes use the term "mesh graph". Mesh graph is not yet well-defined but certainly is an extension of grid graphs and especially rectangular graphs. Original image of mesh graph is far beyond grid graphs and expected to represent the interconnection of nervous center of human brain under the assumption that cerebral cortex is topologically near planar. This shall be another story on some day. Mesh diagram is something like a partial bipartite graph of which vertices is partitioned into two parts, and for only one part of them vertices are not adjacent to each other. Obviously this approach is too broad/ambitious (and unsuccessful) as any graph has its mesh diagram expression in so many ways. But the situation may change if we concentrate on some narrower graph classes.

** In 1988 A. Itai, C.H. Papadimitriou, and J.L. Szwarcfiter wrote a paper with respect to Hamiltonian paths in grid graphs and showed that the problem determining whether or not an instance (G,s,t) consists of a Hamiltonian path is NP-complete, where G is a grid graph with holes, and s and t are distinct vertices in G. The problem is open for grid graphs without holes and they introduced a polynomial time algorithm for the problem of rectangular graph version. [IPS]