The relevance to research the complexity of resolving Graph Theory problems is caused by its numerous applications. In the given paper this problem is investigated in terms of space complexity of data structures that represent analyzed graphs, orgraphs, and directed graphs. The following two non-trivial the simplest sets of problems of Graph Theory are investigated in detail. The rst set consists of the problems that can be resolved by some algorithm with space complexity linear relative to the size of the data structure that represents the analyzed graphs. The second set consists of the following problems, such that the size of the solution signi cantly exceeds the size of the input data. To resolve the problem some algorithm that operates on space linear relative to the size of the data structure that represents the analyzed graphs can be applied. Besides, this algorithm uses some memory of the same size for sequential generation, one fragment after another, the solution of the problem. Some model problems that are not in these two sets of problems are considered brie y.
At present nite graphs (i.e. ordinary graphs, orgraphs, and directed graphs) are used as mathematical models in resolving a wide class of theoretic and applied problems. Rather new areas for application of Graph Theory models are computer and social networks, agent-based technologies, and transition systems used for veri cation of the developed software. Therefore, analysis of the complexity for algorithms on graphs is an actual problem from the theoretic and applied point of view. In Algorithms Theory, the main attention is paid to the analysis of time complexity, while many questions for space complexity remain obscure.
The aim of the given paper is to investigate the classi cation of Graph Theory problems in terms of the memory size necessary to represent the analyzed graphs by basic data structures. These data structures are vertices-adjacency matrices, edges-adjacency matrices, vertices-adjacency lists, and edges-adjacency lists. The main ratios for the complexity of these data structures are established in terms "for almost all" and "on average".
Two sets of Graph Theory problems are investigated in detail.
The rst set consists of the problems that can be resolved by some algorithm with space complexity linear relative to the size of data structure that represents the analyzed graphs. For these problems, the memory size necessary to represent the solution is also bounded above by some linear function of the memory size necessary to represent the input data.
The second set consists of the problems that satisfy the following three conditions.
Firstly, the memory size necessary to represent the solution signi cantly exceeds the memory size necessary to represent the input data.
Secondly, to resolve the problem some algorithm that operates on space linear relative to the size of data structure that represents the analyzed graphs can be applied.
Thirdly, this algorithm uses some memory of the same size to generate sequentially, one fragment after another, the solution of the problem in the explicit form.
Some problems of Discrete Mathematics and its applications that can be naturally reformulated in Graph Theory terms, and that are not in the investigated two sets of problems are brie y considered.
The basic concepts used in the given paper are the same as in [1-3]. 2
In the given Section the basic concepts and de nitions necessary for the presentation of the main results are introduced. 2.1
It is well-known that the main data structures used for representations of graphs are matrices of adjacency (either vertices or edges), incidence matrices, and lists of adjacency (either vertices or edges). We denote R any of these data structures.
Let G(n; m), !G or(n; m), and !G dir(n; m) be the set of all graphs, orgraphs and directed graphs G = (V; E) such that V = f1; : : : ; ng and jEj = m, R(G) be the representation of G 2 X(n; m) (X 2 fG; !G or; !G dirg) by the data structure R, and v(R(G)) be the size of memory necessary for the representation R(G). We set v(R; X; n; m) =
max G2X(n;m)
V (R(G)) (X 2 fG; !G or; !G dirg):
Due to the traditional approach in the Algorithms Theory, we will deal with asymptotic space complexity V (R; X; n; m) of v(R; X; n; m).
It is well-known that for all X 2 fG; !G or; !G dirg: V (R; X; n; m) = O(n2) (n ! 1), if R is the vertices-adjacency matrix; V (R; X; n; m) = O(m2) (m; n ! 1), if R is the edges-adjacency matrix; V (R; X; n; m) = O(mn) (m; n ! 1), if R is the incidence matrix; V (R; X; n; m) = O(maxfm; ng) (m; n ! 1), if R are the vertices-adjacency lists;
V (R; X; n; m) = O(m adjacency lists.
maxf1; minfm; ngg) (m; n ! 1), if R are the edgesSince X is a dummy variable in V (R; X; n; m), we will write V (R; n; m).
Let vA(R; X; G) (X 2 fG; !G or; !G dirg) be the size of memory necessary for an algorithm A to carry out the given processing of the data structure R(G) (G 2 X(n; m)) and
vA(R; X; n; m) = G2mX(anx;m) vA(R; X; G):
In what follows, we will deal with asymptotic space complexity VA(R; X; n; m) of vA(R; X; n; m). 2.2
Let's distinguish the following set of algorithms on graphs.
De nition 1. An algorithm A is called a local algorithm on the set X(n; m) (X 2 fG; !G or; !G dirg) and the data structure R, if
VA(R; X; n; m) = V (R; n; m) (n ! 1; m ! 1):
(
It is evident that the validity of equality (
For any xed positive integer n we set and where union and maximum are over all admissible values of m.
On the base of formulae (
X(n) = [ X(n; m);
m VA(R; X; n) = max VA(R; X; n; m);
m
V (R; n) = max V (R; n; m);
m
(
VA(R; X; n) = V (R; n) (n ! 1): Example 2. Let X = G. It can be proved that following three statements are true:
1. Let R be the representation of a graph G 2 G(n; m) either by the verticesadjacency matrix, or by the vertices-adjacency lists. Then the problem of checking the validity of the property "the given two graphs are isomorphic" can be solved by some algorithm that is a local algorithm for any admissible law of the growth m ! 1.
2. Let R be the representation of a graph G 2 G(n; m) either by the verticesadjacency matrix, or by the edges-adjacency matrix. Then the problem of checking the validity of the property "some sub-graphs of the given graph are the triangles" can be solved by some algorithm that is a local algorithm for any admissible law of the growth m ! 1.
3. Let R be the representation of a graph G 2 G(n; m) by the verticesadjacency matrix. Then the problem of checking the validity of the property "to be a bipartite graph", and each of the problems of computing for the given graph G 2 G(n; m) the radius, the diameter, the center, and the connected components can be solved by some algorithm that is a local algorithm for any admissible law of the growth m ! 1.
On the base of De nition 2, we can distinguish the following set of Graph Theory problems.
De nition 3. The set Lcl(R; X) (X 2 fG; !G or; !G dirg) is the set of all Graph Theory problems P , such that the problem P can be resolved by some local algorithm on the set X(n) and the data structure R for any admissible law of the growth m ! 1.
Example 3. 1. Let An (n = 1; 2; : : :) be the algebraic system with the basic set the set of operations and the set of relations
G(n) = [ G(n:m); FoApn = fn; [; \; ; :g;
FrAenl = f=; g: It can be proved that in the algebraic system An the problems of implementation of any operation f 2 FoApn and checking the validity of any relation 2 FrAenl are elements of the set Lcl(R; G) for any data structure R.
2. Let B be the algebraic system with the basic set
Remark 1. The operations _ and ^ are often used in the design and analysis of algorithms. In particular, for parallel and concurrent computing. Indeed, let the graphs G1; G2 2 T be the models of the two given sub-problems. The vertices present the separate stages of solving these problems, and the edges specify what stages are the neighbors.
The graph G1 ^ G2 describes the situation when only simultaneous advance on stages of both sub-problems is admissible.
The graph G1 _ G2 describes the situation when advance on stages at least of one of the sub-problems is admissible.
For a wide class of Graph Theory problems the size of the solution signi cantly exceeds the size of the input data. Due to this situation, it is reasonable to distinguish the following set of Graph Theory problems.
De nition 4. The set P-Work-Space(R; X) (X 2 fG; !G or; !G dirg) is the set of all Graph Theory problems P , such that the problem P can be resolved on the set X(n) and the data structure R for any admissible law of the growth m ! 1 by some algorithm A that satis es to the following two conditions: Condition 1. The algorithm A operates on the memory size V (R; n) (n ! 1).
Condition 2. The algorithm A explores as an output channel some additional memory of the size that is a polynomial of V (R; n) to generate the solution sequentially, one fragment after another.
We denote Work-Lcl(R; X) the set of all problems P 2 P-Work-Space(R; X), such that the size of additional memory, pointed in Condition 2 of De nition 4 is a linear polynomial of V (R; n). It can be proved that for any X 2 fG; !G or; !G dirg and any data structure R the following strict inclusions hold
Lcl(R; X)
Example 4. It can be proved that the following three statements are true: 1. Let R be the representation either by the vertices-adjacency matrix, or by the vertices-adjacency lists. Then the problem of the design of the edge-to-vertex dual graph is an element of the set Work-Lcl(R; G)nLcl(R; G).
2. The problem of the design of some the longest path between the two given vertices in a graph G 2 G(n), and consequently, the problem of the design of the set of all longest paths between the two given vertices in a graph G 2 G(n), are elements of the set Work-Lcl(R; X)nLcl(R; X) for any data structure R.
3. In the algebraic system B (see example 3.2), the problem of implementation of any operation f 2 f ; ; ^; _g is an element of the set Work-Lcl(R; G)nLcl(R; G) for any data structure R. 3
Similarly to the algebraic systems An (n = 1; 2; : : :) and B (see example 3), there can be de ned the algebraic system !A onr (n = 1; 2; : : :) with the basic set !G or(n), the algebraic system !B or with the basic set the algebraic system algebraic system !B dir with the basic set !A dnir (n = 1; 2; : : :) with the basic set !G dir(n), and the !T or = 1 [ !G or(n); n=1 !T dir = 1 [ !G dir(n): n=1
In Subsection 2.2, when we were speaking about complexity, we meant "complexity in the worst case". From the theoretic and applied point of view, both, a signi cant role also play "the average-case complexity" and "complexity for almost all input data".
The following factors form the strong base for the application of this approach for the detailed analysis of complexity for problems formulated in terms of the algebraic systems Yn (Y 2 fA; !A or; !A dirg) and Z (Z 2 fB; !B or; !B dirg).
On the base of standard methods used for computing the mathematical expectation of the random variable de ned on a nite set, the following theorem can be proved. Proposition 1. Let the elements of the basic set X(n) (X 2 fG; !G or; !G dirg) be chosen randomly. Then in the relevant algebraic system Yn (Y 2 fA; !A or; !A dirg) the average time for the implementation of any operation, as well as the average time for checking validity of any relation, is asymptotically the same for representations of elements of the basic set X(n) by the vertices-adjacency lists and by the vertices-adjacency matrices.
Proposition 2. Let the elements of the basic set X(n) (X 2 fG; !G or; !G dirg) be chosen randomly. Then in the relevant algebraic system Yn (Y 2 fA; !A or; !A dirg) the average time for the implementation of any operation, as well as the average time for checking validity of any relation, for representations of elements of the basic set X(n) by the edge-adjacency lists is less asymptotically than the appropriate time for representations of elements of the basic set X(n) by the edges-adjacency matrices.
On the base of standard methods used for computing the variance of the random variable de ned on a nite set, and using Chebyshev's inequality, the following theorem can be proved.
Theorem 2. Let X 2 fG; !G or; !G dirg. For almost all elements of the set X(n) (n ! 1) the number m of edges satisfy to the following asymptotic equality m =
(n2) (n ! 1):
Proceeding from this theorem, the following two propositions can be proved. Proposition 3. In the algebraic system Yn (Y 2 fA; !A or; !A dirg) for almost all elements of the relevant basic set X(n) (X 2 fG; !G or; !G dirg) the time for the implementation of any operation, as well as the time for checking validity of any relation, is asymptotically the same for representations of elements of the basic set X(n) by the vertices-adjacency lists and by the vertices-adjacency matrices. Proposition 4. In the algebraic system Yn (Y 2 fA; !A or; !A dirg) for almost all elements of the relevant basic set X(n) (X 2 fG; !G or; !G dirg) the time for the implementation of any operation, as well as the time checking validity of any relation, for representations of elements of the basic set X(n) by the edge-adjacency lists is asymptotically less than the appropriate time for representations of elements of the basic set X(n) by the edges-adjacency matrices.
Some Remark About the Set Work-Lcl(R; X)nLcl(R; X) One of the main reason owing to which the considerable number of problems of Graph Theory are elements of the set Work-Lcl(R; X)nLcl(R; X) is based on the following factor. The problem of the design of any object is an element of the set Lcl(R; X), but the number of objects, which are required to be designed as the solution of the analysed problem, is an exponent or some sub-exponent of n and m. This situation can be illustrated as follows.
Example 5. It can be proved that for all X 2 fG; !G or; !G dirg and for all data structures R the following problems are elements of the set Lcl(R; X): 1. The problem of the design of some the shortest path between the given two vertices in G 2 X(n).
2. The problem of the design of some Hamiltonian path between the given two vertices in G 2 X(n).
3. The problem of the design of some Hamiltonian cycle in G 2 X(n). 4. The problem of the design of some cycle that visits the given vertex in G 2 X(n).
5. The problem of the design of some spanning tree in G 2 X(n). 6. The problem of the design of some minimum spanning tree in G 2 X(n).
On the base of estimation the number of objects which can be designed in each of listed above case, it can be proved that for all X 2 fG; !G or; !G dirg and for all data structures R the following problems are elements of the set Work-Lcl(R; X)nLcl(R; X):
1. The problem of the design of the set of all shortest paths between the two given vertices in G 2 X(n).
2. The problem of the design of the set of all Hamiltonian path between the given two vertices in G 2 X(n).
3. The problem of the design of the set of all Hamiltonian cycles in G 2 X(n). 4. The problem of the design of the set of all cycles that visit the given vertex in G 2 X(n).
5. The problem of the design of the set of all spanning trees in G 2 X(n). 6. The problem of the design of the set of all minimum spanning trees in G 2 X(n). 5
Analysis of problems pointed in the Section 4, show that each of them can be solved by backtracking with linear space complexity. Unfortunately, there is a wide class of problems of Discrete Mathematics and its applications, such that the following two conditions hold: 1. Searching is the only known method of the solution of the given problem. 2. At implementation of searching there is an essential growth of lengths and the number of the designed and analyzed sequences of objects, both (just this factor results in exponential space complexity of searching).
All these problems formulated in terms of Graph Theory are the problems that are out of the set Work-Lcl(R; X).
An important non-trivial subset of the above-pointed problems of Discrete Mathematics consists of the problems that can be reduced to the design of some strategy for walks of special type on some graph. This subset includes in itself the problems, at least, of the following three types:
1. The problems that can be reduced to the design some unconditional, adaptive or cooperative strategy for some walk on the given graph, intended to identify the vertices covered by blots. In particular, to these problems can be reduced problems of identi cation of states for nite automata. Interpretation of these adaptive and cooperative strategies in terms of automata-experimenters demonstrates high complexity for computing the values of predicates de ned on graphs by some nite automaton or some interacting group of nite automata.
2. The problems that are connected with the design of the supervisor intended to carry out adaptive control for discrete events systems presented by nite automata models.
3. The problems connected with the design of the winning strategies for considerable number of two persons games on graphs. 6
In the given paper we have analyzed two sets of Graph Theory problems. The rst set consists of all Graph Theory problems that can be resolved by algorithms with linear space complexity. The second set consists of all Graph Theory problems, for which the size of the solution essentially exceeds the size of the input data, but there exists some algorithm that operates on space linear relative to the size of the input data, and this algorithm uses some additional memory of the same size, intended to generate the solution sequentially, one fragment after another.
It has been illustrated that these sets consist of su ciently wide class of Graph Theory problems.
The carried-out analysis of su ciently powerful algebraic systems on graphs gave the possibility to establish a number of estimates in terms "in average" and "for almost all objects".
Presented in the given paper results form some strong base for research of the structure of the set P-Work-Space(R; X), for analysis complexity, accuracy and e ciency of local search strategies on graphs, for investigation problems of design di erent strategies for walks on graphs, etc.