2-2-1. kTerminal Division Experiment

Procedure to make division experiment of a graph with k-terminal points set is shown as below.

(1) Assume that the divided subgraph of less branches number or less points number is the right subgraph. Let branches joining terminal points each other belong to the left subgraph.

(2) First, we experiment the right subgraph. Here, add branches of branches set called cap or cap-branches set to the conjunction part of the right subgraph. We call the working graph obtained in this way from right subgraph as capped right subgraph. Hereon cap or cap-branches set is a set of branches joining each points of terminal points mutually and so is a branches set of a complete subgraph of which points set is the terminal points set.

(3) Experiment of right subgraph inquires a Hamiltonian tie of the capped right subgraph. However this Hamiltonian tie may not contain a part of points of the terminal points set. It is because that such points are probable to be released as the blockade points of the left subgraph. Acordingly a Hamiltonian tie to be obtained is a spanning cycle of the right subgraph containing even points of the terminal points set.

(4) If the experiment of right subgraph lockouts, this right subgraph is a diamond figure with a conjunction part of the k-terminal and then the graph is a non-Hamiltonian graph.

(5) We call the spanning branches subset obtained by removing cap-branches from the Hamiltonian tie of the capped right subgraphs as Hamiltonian passage. We call the set of branches of cap closing the Hamiltonian passage as left substitutive branches set. The left substitutive branches set should not be empty. if we cannot obtain right Hamiltonian passage with non-empty left substitutive branches set, this right subgraph is a diamond figure with a conjunction part of the k-terminal and then the graph is a non-Hamiltonian graph.

(6) We call a subset of cap's brahcnes which substitiute for a right Hamiltonian passage as right substitutive branches set. Experiment of left subgraph is performed by getting a working graph added branches of right substitutive branches set at the conjunction part of the left subgraph and searching a Hamiltonian tie of the graph. We call the working graph obtained in this way from left subgraph as capped left subgraph.

(7) If we succeed in the experiment of left subgraph, the graph is a Hamiltonian graph and we obtain a Hamiltonian tie combining left and right Hamiltonian passage.

(8) If we fail in the experiment of left subgraph, we must make thorough experiments with all combinations of branches of the IO-conjunction part. If newer right Hamiltonian passage is obtained, according to the interface proceed to the experiment of left subgraph.

(9) If we fail to obtain newer right Hamiltonian passage, this graph is a non-Hamiltonian graph. Newer Hamiltonian passage means the one with different right substitutive branches set. Even if it is different as Hamiltonian tie but the right substitutive branches set is the same, reject it.

(10) If we obtain a left Hamiltonian passage corresponding with the right Hamiltonian passage, this graph is a Hamiltonian graph and we obtain a Hamiltonian tie combining left and right Hamiltonian passages.

(11) If we fail to obtain a left Hamiltonian passage corresponding with right Hamiltonian passage after examining all the cases, this graph is a non-Hamiltonian graph.

On this method of experimentation, clearly it is able to be completely perfomed with recursive procedure, for experiments of right and left subgraphs represent themselves as a problem inquiring a Hamiltonian tie. Any way, it is needed that a right substitutive branches set is not empty, in other words, branches of capped-branches set are contained in the Hamiltonian tie. It means that the subgraph is not a diamond figure.

Hereupon to make thorough experiments with all combinations of branches of the IO-conjunction part is equal to enumulating one-factor subgraphs of the k points clique correspond with right Hamiltonian paths, that is, a family of left substitutive branches sets. This corresponds to enumalating Hamitonian ties of the right capped right subgraph. The number of the sub-experiments is the number of combinations to take out even elements from a set of k elements.

As it is obvious that a problem to enumulate Hamiltonian tie of a graph requires more calculation costs than our problem of finding out one Hamiltonian tie, this experimentation holds only if the size of right subgraph is small enough. It is said to be probable that this calculation comes realistic if k is small enough, for the number of the cases comes restricted spountaneously.

Calculation to get left Hamiltonian passage adapting to the interface of right Hamiltonian passage is equal to the calculation to get a Hamiltonian tie of the capped left subgraph. Consequently if the left subgraph is large enough it is unavoidable that this calculation itself comes to NP-complete. (Here we do not ask NP=P or not.)

If it is needed that the right subgraph is small enough, it is inevitable that the left subgraph becomes large, then it is presumed that examples aplicable to this calculation comes rather restricted. Supposing k-terminal division experiment is perfomed recursively, it seems that a division which separates the graph almost from the center will be a most rapid converging example, however when N is large enough it is questionable that whether is it able to say that N/2 comes small enough number.

In the case that everytime of sub-experiment a small enough k and a small enough right subgraph can be supplied, as the size of left subgraph will linerly decrease, roughly speaking, we can expect that the calculation ends in the order of k * N * c. (k and N are polinomial formulas of k and N respectively) Hereat we assume that a right subgraph is small enough to be able to complete calculation in the order of constant c and the number of Hamiltonian ties enumulated is in the order of k.

It is considered that in the case that sizes of right subgraphs do not come small enough, concerning that the calculation tree roughly becomes a binary tree of height order N, it is inevitable that the total cost of the calculation tree comes exponential.

As it is obvious that there exist such graphs as disable to obtain small enough k or disable to obtain small enough right subgraph in general graphs, it is impossible that to apply the k terminal division method in general. Accordingly it comes that phases in which k-terminal division or cut-set division should put to practical use are restricted to huristics in factor experiments, doesn't it? Since factor experiment does not contain such rules as even passage points or even passage branches rule, it is able to accelate factor experiments by introducing them.

It will be considerd that if we can experiment on enumulating all k-terminals or cut-sets, we can accomplish complete experimentation of k-terminal division or cut-set division. However, the problem is that there are cases that plural of k-terminal or cut-set divisions jointly own points of terminal points sets or branches of cut-sets. We call such situation as crossing-IO-divisions and the ocurrance of contradiction caused by them as cross-IO contradiction. We think that a judgement with non-retrial which detects absolute cross-IO contradiction (unavoidable cross-IO contradiction) has not been developped so far.

By definition a cut-set dividing a connected graph always divides the graph into two connected components. Because if this cut-set separates more connected components than two, necessasrily there exists a branch connecting any two of those components and we can obtain smaller cut-set by removing the branch from the cut-set. That is, since the cut-set comes to contain a smaller cut-set as it's proper subset, it is not a cut-set by definition.

On the contrary a k-terminal division is probable to separate a graph into three or more connected components by the case. However since in our k-terminal division experiment, we can treat those connected components as two subgraphs collecting them in two groups, it is sufficient if we can prove that a k-terminal division experiment which separates a graph into two (not necessarily connected) components is right. Theorems below give assurance and justification to cut-set experiment and k-terminal division experiment.

def.2-2-1.1: semi-points graph

Divide every points of directed N points graph G into input semi-point and output semi-point. However input semi-point without input branch or output semi-point without output branch are never generated. We call graph G', |G'|<=2N derived from G in this manner by semi-points graph of graph G. On semi-points graph, points number comes twice of G but branches number is the same.

As a path on a semi-points graph everytime turns over the direction of branches alternately like output-semi-point->input-semi-point<-output-semi-point, semi-points graph is a kind of alternative graph. A circuit on the directed graph G is oriented then it comes to be 1-factor on the semi-points graph.

def.2-2-1.2: cut-set passage branch

We call branches owned jointly by an elementary circuit and arbitrary cut-set of connected graph G as cut-set passage branches of the circuit. By theorem 2-2-1.1 number of passage branches is even.

def.2-2-1.3: k-terminal passage point

Within points owned by an elementary circuit C and arbitrary k-terminal points set K of connected graph G, we call such point that two branches of C incident with the point are contained respectively in both of left and right subgraph separated by K as k-terminal passage point of the circuit. By theorem 2-2-1.2 number of passage points is even.

Theorem 2-2-1.1. even passage branches rule

With respect to a cut-set S dividing a directed graph G into two connected components, a simple circuit C of G owns jointly even number of branches with S.

Proof:

Let semi-points graph of G be G'. Paint semi-points black when the point of circuit C belongs to right connected component and paint them white when it belongs to left connected component. Every passage branch has a white and black semi-point on G'.

Since a path of circuit C entered into the right connected component through a branch of S with white input semi-point and black output semi-point must return to the left connected component through a branch of S with black input semi-point and white outpout semi-point, then it can be said that those white-black and black-white two passage branches make a pair. Hence passage branches are even.

Theorem 2-2-1.2. even passage points rule

With respect to a k-terminal points set K separating a directed graph G into two subgraphs, within points owned jointly by an elementary circuit C and K, the number of points incident with such two branches of circuit C that contained in both of left and right subgraph respectively is even. Hereon providing that branches joining terminal points mutualy belong to either of left or right subgraph.

Proof:

Let semi-points graph of G be G'. Paint semi-points black when the branch of circuit C belongs to right subgraph and paint them white when it belongs to left subgraph. Every passage point has a white and black semi-point on G'.

Since a path of circuit C entered into the right subgraph through a point of K with white input semi-point and black output semi-point must return to the left subgraph through a point of K with black input semi-point and white outpout semi-point, then it can be said that those white-black and black-white two passage points make a pair. Hence passage points are even.

In the case of undirected graph, we can prove similarly above by meas of giving arvitrary orientation to the branches of circuit C.

It should be cautioned that there are two following arbitrariness in the formation of k-terminal division. (1)It is arbitrary which does a branch joining terminal points belong. (2)In the case that the graph is divided into 3 or more conected components, how to separate the graph into 2 subgraphs has arbitrariness.

In case(1), according to the assignment of the branches joining terminal points, the position of terminal points are altered. (This alteration is just nominal). However the condition that the number of passage points is even is unchangeable.

In case(2), as the combination of connected components partitioning into 2 subgraphs is arbitrary, and the passage points are decided with each case, there may be some cases that the number of elements of points set obtained by mearging passage points obtained from these diffent formation of subgraphs, that is, the number of whole passage points does not come necessarily even.

These are more or less resemble to the phenomina of crossing IO-division mentioned above, but should be considered different. We introduce below definitions to give them a little more rigid disposition.

Def.2-2-1.4: k-terminal points set incident with cut-set

When cut-set S of connected graph G devides G into 2 connected components, one side of end points of a branch of S is contained in right connected component and another side of end points is contained in left connected component. Within end points of branches of S, a set of points contained in right or left connected component aparently makes one k-terminal points division. We call this as k-terminal points division incident with cut-set S. Number of k-terminal points divisions incident with some cut-set is at most two.

Def.2-2-1.5: cut-set incident with k-terminal

When k-terminal division of connected graph G devides G into m connected components, branches incident with terminal points of K are partitioned into two kinds that joins a terminal point and a point of one of connected components, and that joins terminal points mutually. Within these branches, a set of branches joining a connected component and terminal points aparently makes one cut-set. We call this as cut-set incident with k-terminal.

Number of cut-sets incident with some k-terminal is equal to the number m of connected components separated by the k-terminal division. Cut-set S incident with K does not contain branches joining terminal points of K.

Theorem 2-2-1.3: k-terminal division and connected components

Number of connected components separated by arbitrary k-terminal division of connected graph G is equal to the number of cut-sets incident with the k-terminal.

Proof:

Let one of connected components separated by k-terminal division K of graph G be C. Since G is divided into two connected components by removing all branches joining C and K and is not divided unless all these branches are removed, these branches set makes a cut-set of G.

End points set K' in K side of this cut-set S is a subset of the terminal points set of K. Since G is separated by removing all of points of K', if K' is a proper subset of the terminal points set of K, K' is a k-terminal division and K is not by definition, then contradicts. Therefore K' must correspond with K.

Moreover since this cut-set S does not contain branches joining terminal points of K, then S is a cut-set incident with K, and connected components separated by k-terminal division corresponds one-to-one with cut-sets incident with k-terminal. Hence the numbers are the same.

Theorem 2-2-1.4: k-terminal/cut-set conjunction

Let k-terminal division incident with cut-set S of connected graph G be K, S is a cut-set incident with k-terminal division K. And vice versa.

Proof:

Within end points of branches of cut-set S, let a set of points contained in right connected component be K. Since graph G is separated into two subgraphs by removing all points of K and is not separated unless all these points are removed, K is a k-terminal division and incident with the cut-set S in right hand by definition.

When K separates graph G into m connected components, left connected component L of cut-set S is one of these connected component, and one side of end points of every branches of S is in L and another side of end points is a terminal point of K. If S has branches joining terminal points of K, a branches set obtained by removing these branches from S makes a cut-set, then contradicts definition. Therefore S has not branches joining terminal points of K. Hence cut-set S is a cut-set incident with k-terminal division K.

Similarly, when cut-set S is incident with k-terminal division K in left side, from the proof of Theorem 2-2-1.3, right end points set of branches of S corresponds with the terminal points set of K. Hence when S is a cut-set incident with K, K is a k-terminal incident with S.

Def.2-2-1.6: IO-conjunction map

With respect to graph H with a points set consisits of all of k-terminal divisions and cut-sets of connected graph G, when a k-terminal division and a cut-set is incident mutually, H has a branch joining these two points. By Theorem 2-2-1.3 we can define such indirected graph H solely from graph G. We call this graph H as IO-conjunction map of G.

A path on IO-conjunction map H is an alternative path where a point of k-terminal division and a point of cut-set appears alternatively, and then H is a kind of alternative graph. And also number of branches of any cut-set point is ever 2 or less.

When there exists an k-terminal division K, according to some combination of branches of the set of branches incident with terminal points of K, we may ocasionally obtain other cut-sets than cut-sets incident with K. Similarly when there exists an cut-set S, according to some combination of points of the set of end points of both side of branches of S, we may ocasionally obtain other k-terminal divisions than k-terminal divisions incident with S.

That is, there exist rather much arbitrarity of IO-divisions in the neighbourhood of a k-terminal division K or cut-set S. However for these divisions are positioned at another location not incident with K or S on IO-conjunction map, the uniqueness of the IO-conjunction map is guranteed.

We are realy interested in the formation of IO-conjunction map but have not reserched in this district deeply. As it is known that cut-set and circuit have dual pecuriarity called matroid, to research how does k-terminal division relate to them becomes the subject, doesn't it?