At first, we define several terms for using hereinafter.2-1. Factor Experiment
At first, we define several terms for using hereinafter.
Def.2-1.1 Hamiltonian tie
An elementary circuit passing all the points of graph is a Hamiltonian tie.
Def.2-1.2 Hamiltonian path
An elementary path passing all the points of graph G is a Hamiltonian path.
Def.2-1.3 Hamiltonian graph
A graph having Hamiltonian ties is a Hamiltonian graph.
Def.2-1.4 non-Hamiltonian graph
A graph having no Hamiltonian tie is a non-Hamiltonian graph. Every graph is either a Hamiltonian graph or a non-Hamiltonian graph.
Def.2-1.5 complete Hamiltonian graph
a graph having Hamiltonian ties passing an arbitrary branch is a complete Hamiltonian graph.
Def.2-1.6 contradictory branch, obstacle branch, established branch
A branch not contained by any Hamiltonian tie is a contradictory branch of the graph. That is, a contradictory branch of G means a branch not included in the total solution of Hamiltonian ties of graph G. A branch not contained by some Hamiltonian tie of graph G is an obstacle branch of the tie. An obstacle branch of G means a branch not included in some particular solution of Hamiltonian ties of graph G. On the other hand, a branch included in all of particular solutions is called an established branch of Hamiltonian ties.
Def.2-1.7 determinative paths (determined branches set), determination
We call A branches set assumed as branches of a Hamiltonian tie of graph G in some stage of Hamiltonian experiments and distinguished from other branches set by determinative paths or a determined branches set. As determinative paths comprise plural branches or series branches lists, they are not necessarily "a continuous path". And further, we say an operation to select and add a branch to the determinative paths as determination.
Def.2-1.8 Hamiltonian tie postulate, perfect experiment, full experiment
We define rules below as the criterion for subgraph G' of G to be a Hamiltonian tie of G and call them Hamiltonian tie postulate. We prove a theorem that the Hamiltonian tie postulate is necessary and sufficient as rules for Hamiltonian experiments.
(1) 2-factor rule: G' is a spanning 2-factor subgraph of G.
(2) 1-circuit rule: G' has not elementary circuits more than two.
We call an experimentation to detect offenses against the 2-factor
rule by perfect experiments and an experimentation to detect offenses against both
of 2-factor rule and 1-circuit rule by full experiments.
Def.2-1.9 deadlock, shutdown, lockout
We say that such a state is a deadlock, that an offense happened against the postulate with the cause of some branch operations. We call such a state by shutdown, that deadlocks have inevitably happened ahead experimenting every branches of a point. And further, we call such a state by lockout, that a graph should be decided to be a non-Hamiltonian graph, for example, in the case that shutdowns have happened at all points.
Theorem 2-1.1. Hamiltonian tie postulate
Graph G' of spanning 2-factor subgraph of graph G not having elementary circuits more than two is a polygon with edges of branches of a Hamiltonian tie of graph G. And also, the contrary holds.
Proof.
If G' is connected, since numbers of branches of all of the points of G' are even, G' has an Eulerian circuit passing all the branches. Since this circuit never passes twice a same point, it is an elementary circuit passing all the points of G'. Hence G' has a Hamiltonian tie and since G' is a spanning subgraph of G, this Hamiltonian tie is a Hamiltonian tie of G.
If G' is not connected, G' can be separated into connected components. Since there exist elementary circuits passing all the points of these connected components respectively, G' has more than 2 elementary circuits and this contradicts to the premise.
Hence G' is connected and has a Hamiltonian tie of G and has no other element than that, therefore graph G' is a polygon with edges of Hamiltonian tie of G.
Let G' be a polygon with edges of Hamiltonian tieof G. Since
Lemma 2-1.1. disconnected graph
A disconnected graph is a non-Hamiltonian graph.
Proof:
In disconnected graph G, there exist such two points that there is no path from one point to another. Let be these points P and Q. A Hamiltonian tie passing point P must pass point Q, nevertheless, there is no path from point P to point Q. Hence graph G has no Hamiltonian tie.
Lemma 2-1.2. strongly connected graph
A directed graph not strongly connected is a non-Hamiltonian graph.
Proof.
In non-strongly-connected directed graph G, there exist such two points P and Q that there is no path from point P to point Q or else that there is a path from point P to point Q but there is no path from point Q to point P. A directed Hamiltonian tie passing point P must pass point Q, therefore, it is necessary to be a path from point P to point Q and a path from point Q to point P. Nevertheless, there are not such paths, hence graph G has no Hamiltonian tie.
Lemma 2-1.3. 2-connected graph
A non-2-connected graph is a non-Hamiltonian graph.
Proof.
Suppose graph G is not connected. Then graph G is a non-Hamiltonian graph by Lemma. 1. Hence we may assume that graph G is connected. Since graph G is not 2-connected then it is separable to two (not necessarily connected) components by disjointing a point of G. Let the point P. Let a point of one component A and let a point of other component B. Then a Hamiltonian tie of G must pass through both of a path from point A to point B and another path from point B to point A. However, both of a path from point A to point B and a path from point B to point A must pass through point P, then the Hamiltonian tie pass the point P twice and a contradiction. Hence graph G has not a Hamiltonian tie.
Because
Hamiltonian Circuit Problem includes non-determinability which we call Omega-Problem, it
is inevitable that Hamiltonian experimentation comes to include procedures searching in
trial and error. Factor experiment method is the most basic experiment method comprising
operations to select branches arbitrarily and to add them to determinative paths and as it
proceeds to the experiment principally paying attention to numbers of branches connected
to points on determinative paths, therefore it is called factor experiment.
Hamiltonian
tie postulate is a set of rules for experiments but it can be considered as constraint
conditions for selecting some branches and determining them. In other words, when we
select a branch arbitrarily and add it to determinative paths, we are required to select
such a branch as satisfies the postulate. Moreover, when we determine a branch, there is
such a case that a branch is decided automatically to be surely added to determinative
paths due to the constraint conditions to be satisfied.
Accordingly, there comes two kinds of operation to determine a branch,
one case to select and determine arbitrarily (this is called arbitrary selection) and
another case to be determined automatically (this is called auto-determination). We call a
phase of arbitrary selection by stage or arbitrary selection phase. One stage includes one
arbitrary selection and plural auto-determinations. We call a phase to add one branch to
determinative paths including both of the case of an arbitrary selection and an auto
determination by step.
Factor experiment is an experiment method for directed graphs. In the
case that given graph is an undirected graph, we experiment replacing 1 undirected branch
with 2 directed branches confronting. And further, on the state that a point has only one
input branch or output branch, we call such a branch by singular branch and call such a
point by singular point. An operation for determination (one step) in factor experiment
comprises the following procedure.
(1) Add a branch to the determinative paths.
(2) If the number of the points of the determinative paths equal to N, halt.
(3) If there is such a branch as closes a branches list on the determinative paths as a
circuit, remove it.
(4) Remove input branches of input point and output branches of output point for the
determined branch.
An arbitrary selection phase (one stage) in factor experiment
comprises the following procedure.
(1) Select a branch arbitrarily and determine it.
(2) If there is an input point without input branch or an output point without output
branch, halt.
(3) If there is a point adjacent to plural singular points, halt.
(4) if there is a singular point, determine its singular branch.
(5) Repeat from (2) until there is no singular point.
As factor experiment comprises plural arbitrary selection phases, an
arbitrary selection phase comprises plural operations of determination and an operation of
determination comprises plural operations of removal of branches, in conclusion, factor
experiment is realized as operations repeating an operation to remove a branch from the
graph and finally obtaining a subgraph contains only branches of Hamiltonian tie. When
determinative paths includes all the point of the graph, the paths come to be a
Hamiltonian path and if there exists a branch conjoining the end point and start point of
the path, this graph is a Hamiltonian graph.
Removal of input branch of input point or output branch of output
point is an operation regarding the 2-factor rule of Hamiltonian postulate and removal of
a branch closing a branches list on determinative paths as a circuit regards the 1-circuit
rule. All the branches of Hamiltonian graph G are branches on a Hamiltonian tie, or else
surely those branches closing a branches list on determinative paths as a circuit. (Since
a Hamiltonian tie is a spanning path, both terminal points of any branches on G are surely
on the Hamiltonian tie.) Therefore, That 1-circuit rule was applied on a peculiar branch
merely means that it happened occasionally in practice, and the rule ultimately regulates
all branches which are not on the Hamiltonian tie.
In arbitrary selection phases, we say that both of such state are
deadlocks, as (1)a state that either an input point without input branch or an output
point without output branch has occurred, (2)a state that a point adjacent to plural
singular points has occurred. That a deadlock has occurred represents either that the
graph is a non-Hamiltonian graph or that contradictory branches or obstacle branches have
mingled in the determinative paths. We call an input point without input branch and an
output point without output branch by lost point. Furthermore, let us call a point
adjacent to plural singular points by cloven point. A cloven point is a convergent point
or else a divergent point on determinative paths. A lost point occurs due to an offense
against 2-factor rule of Hamiltonian postulate. A cloven point offends against 1-circuit
rule.
A deadlock occurs associated with an operation to select arbitrarily
some branch in arbitrary selection phases in factor experiment, furthermore a deadlock
probably happens in the initial phase (in the case that the length of the determinative
paths is 0). If there exists a less than 2-factor point, the graph is a non-Hamiltonian
graph. This is only one possible judgment with non-retrial in factor experiment and it is
able to detect a part of disconnected graphs as non-Hamiltonian graphs. Factor experiment
cannot separate a disconnected graph with 2-connected components, but it is able to be
separated finally when a deadlock occurs due to a removal of branch closing a branches
list on the determinative paths as a circuit.
The judgment with non-retrial of factor experiment cannot separate a
strongly connected graph, but there exists polynomial time algorithms to separate a graph
into strongly connected components and so they are able to be executed independently as
strongly connected graph experiments. Non-2-connected graph is separable as
non-Hamiltonian graph with IO-division experiment in the next section.
