The mathematical method φ-transformation in which large structures are regarded as a set of small and simple substructures. For this, they may have some common parts, that can be identified and amalgamated when constructing or reconstructing an entire structure from a finite number of substructures. Task: To demonstrate the possibilities of this method for the constructing of the set of all nonisomorphic 3-minimal plane simple graphs in which the set of all vertices is located on the boundaries of three 2-cells and constructing the set of all nonisomorphic 2-minimal projective planаг graphs in which the fixed set of points is located on the two boundaries 2-cell or pseudo cells. Based on the method of -transformations of the 3-minimal planar graphs and the 2-minimal projective planar have been established and modified algorithms of producing these graphs have been suggested. The main result: algorithms and lists of the 3-minimal planar graphs and 2-minimal projective planar with genus 0 or 1.
Let's solve the problem of analysis of a complex system synthesized from the studied simpler substructures in general and their application in computer sciences. We offer a graph-theoretical approach as a way of machine thinking or operating with artificial images-structures. It is known that there are mathematical methods by which large systems as structures are considered through a set of small and simple substructures, which may have some common parts that can be identified in the construction or reconstruction of the whole structure from a finite number of substructures.
The main tool is the φ-method of creating a graph model obtained in the form of a pair of finite sets: sets of vertices and sets of edges to determine the relationships between the structure of vertices as objects. An example of this is the transformation of the main problems of system programming into problems of graph theory with the mathematical support of algorithms.
The main idea of the method of φ-transformation can be interpreted as a way of inheriting a certain property of substructures in the whole structure depending on the properties of the connection (identification of given parts of pair of substructures).
Task. To demonstrate the possibilities of this method for the constructing of the set of all nonisomorphic 3-minimal planar graphs in which the set of all vertices is located on the boundaries of three 2-cells and constructing the set of all nonisomorphic 2-minimal projective-planаг graphs in which the fixed set of points is located on the two boundaries 2-cell or pseudosells.
The solution to our task was based on the method of graph transformations, whose founder is M.P.
Khomenko, and the concepts he introduced. The recognition of φ-transformations of graphs was taken
from [
Тhe structural properties of a complex system model presented in the form of a graph model can be studied using a simple graph G with a fixed set of points embedded in the surface on which the edges of the graph will be located, where S is the Euclidean plane or projective plane. The point is either vertex G, or the inner point of the graph of edges G. Let us consider the connected simple graph G , G (G 0 , G1 ) , where G 0 is the set of vertices and G1 is the set of edges without multiple edges and without loops as its 2-cell minimal embedding in the surface S. The property of minimality of the model graph over S will be that the graph G with the edge removed or the edge compressed into a point will have changed the specified numerical measure of the fixed set of points of the graph G. For example, model G such a property outer-planarity of the set of all vertices which located on the boundary of one cell is the presence of subgraphs homeomorphic to K4 or K2,3.
This result will be useful in the systematic analysis of both graph models and their topological aspect which will have common properties at the edges and vertices of the graph model.
The cylindrical graphs were introduced in [
Results: 1) The algorithm and the list of 3-minimal graphs, namely their characterization by the
method of φ-transformation of graphs, was given in [
Application trend. An example of a possible application is the set of points placement problems or automatic control with subsequent access to its points. If we talk about the surface as an almost infinite set of values of the function of several variables on a given finite subset as a set of vertices whose relationship between pairs of elements as a set of edges, we have an almost embedded graph in the surface. If it is possible to set edges as an almost infinite subset of points and in the absence of intersection of edges in infinite vertices of edges, we will have an almost exact embedding of the graph in the surface. If the surface is spherical or resembles some extent a plane without holes, then use the following list of 3-minimal graphs to place on the boundaries of three cells of all vertices of the graph. If the surface is a sphere with a hole or to some extent resembles a plane of holes, then we use the following list of 2-minimal projective planar graphs to place on the boundaries of two cells of a given set of vertices of the graph.
According to [
According to [
Problem. Let us study the identity of non-cylindrical and 3-minimal dense graphs and compare the
graphs from the given lists in figure 1 with the list [
History of the problem. In [
We have the following relation for the planar graphs:
Proposition 1. All graphs from the list [
We consider the modification of algorithm [
Theorem 1.
If the connected planar graph
G has the following condition (u)(u G1 )(tG\u (G 0 ) tG (G 0 ) 1 2) , then one of the following propositions holds: 1) G K 4' . The graph K 4' is a graph K 4 in which each edge is 1-divisible; 2 i1 Gi а) (i,i 1,2)[(Gi K 4' ) ((Gi K 2,3 ) (Gi K 4 ))] ; b) Gi ({yij }nj1 ) CGni1 ( yi1, yin ) - the simple path of the length n 1 of the graph Gi , where yi1 yin , { yij }nj1 Gi0 Gi1 , where i 1,2 , (if n 0 then the simple path is formed into a point yi1 ); c) G({yi }nj1 ) - the simple path of the graph G of length n 1 ( n 0 the simple path is generated to a point y1 ); 3) Existence of -transformation of the graph G0 G3 in the graph G by the following: n (G0 G3 , (Z 0i Z 3 j )) (G,{Z j }nj1 ) , where graph image satisfies the following conditions: j1
2 a) The G0 is an image of graph Gi written as in statement 2) of this theorem; i1 b)
G3 K 2,3 ; G0 ({Z 0 j }nj1) is a cycle of the length n (possibly with diagonals) of the graph (possibly the boundary of the outer boundary of the graph f ( G0 )) ( ), where f | G0 : G0 is the contribution that realizes tG (G00 ) , {Z j0 }nj1 G00 G01 ; c) G3 ({Z3 j }nj1) is a simple cycle of graph G3 , possibly with diagonals. 4) There is a -transformation of the graph defined as follows: 2 Gi into a graph G i1 ( 2 Gi , n ( y1 j y2 j ) ( y 1 j y 2 j )) (G,{ y j }nj1 { y }) and satisfies the following conditions: i1 j1 a) (i,i 1,2)[(Gi K 4' ) ((Gi K 2,3 ) (Gi K 4 ))] ; b) Gi ({yij }nj 1 ) CGni1 ( yi1, yin ) yi1 - simple path length n 1 graph Gi is connected with y i1 the isolated graph Gi point which does not belong to the subgraph Gi ({yij }nj1) CGni1( yi1, yin ) of yi1 yin , { yij }nj1 Gi0 Gi1 , i 1,2 , ( n 0 the simple path is generated in the point yi1 of , at that yi1 yi1 ); c) G({y j }nj1) - simple path of graph G with length n 1 which no include in subgraph Gi ({yij }nj1)) .
Proof. Let simple graph G is the connected planar with all significant edges with respect to the number of reachability of the set of vertices equal t 3, in the operation of removing an arbitrary edge and embedding f , f : G set the attachment that implements tG (G 0 ), tG (G 0 ) t 3 , SG (G 0 ) {si }i31 -set of 2-cells on the border of which all vertices of the graph G . We denote by the M (G) set of all the different subgraphs H of the graph G constructed for each pair (si s j ) , where i j , of 2-cells from the set SG (G 0 ) as the smallest part of the graph G that satisfies the ratio: G 0 dsi H i0j H i0j ds j dsi G 0 ds j H i0j H i0j dsi ds j (Hij K4) (Hij K2,3))] (*).
Denote by M ' (G) - the least included a subset of the set M (G) , consisting of the smallest included subgraphs H ij of the graph G , or parts of these subgraphs that satisfy the following conditions: a) G 0 ( H ' )0 ;
H 'M (G ) b) If the subgraph H ij (or its part) is homeomorphic to the graph which, or all the edges of the graph are 1-subdivided or no edge of the graph K 4 is 1-subdivided. In the future, if no reservations are made, we will assume that, with respect to the elements of the set M ' and the term "subgraph" of the graph G , does not preclude the fact that this element may be part of the graph. distinguish two sets Si {sij }3j1 , i 1,2 , namely а) ds11 {1,2,7,8}, ds12 {2,3,7,8}, ds13 {4,5,6,7}; б) ds21 {1,2,7,8}, ds22 {1,2,3,4,5,6,7}, ds23 ds13 . For each of them we construct a set
M i , M i M (G) , H102 {1,2,3,7,8} , H 21 {1,2,7,8}, H 203 H 302 ; (H103 )' {1,2,6,7,8} , (H103 )'' {1,2,4,7,8} , ( H103 )''' {1,2,5,7,8} , H103 {( H103 )' , (H103 )'' , (H103 )'''}, H 302 {3,4,5,6,7} , H 301 {1,4,5,6,7} , H102 {1,2,7,8,3}, H103 {1,2,8,7,6,4,3} , H 201 H102 , H 203 {1,2,3,4,5,7,6} , H 302 {4,5,6,7,3} , M (G) {H12 , H13 , H 23 , H32}.
It is easy to see that the above sets a) and b) exhaust all nonisomorphic sets SG (G 0 ) , and as a result M ' (G) {H12 , H 32}.
We prove Proposition 1). Since the graph K 4' is a graph K 4 with all 1-subdivisions edges and will have the property: (u)(u (K 4' )1 )[(tK 4' \u ((K 4' )0 ) 2) (t ' ((K 4' )0 ) 3)], then we will have the K4 inclusion K 4' G . On the other hand, if K 4' G , then there is an edge u , u G \ K 4' . Proposition 1) is proved.
Let the graph G be nonisomorphic to the graph K 4' . The following two cases are possible: m), chains, the third in a simple cycle. We prove Proposition 2). We have the following two options of the φ- transformation of two subgraphs from the set M: 1) two simple chains, 2) two different pairs of 2 n simple chains. That is, we have the following relationship: G[ H i ] CGn j (a j , b j ) i1 j1 (b1), where n 0 , (possibly n j 0 , then a simple chain degenerates into a point a j ). Since, G K 4' the where CHnik (ak1, ak (ni 1) ) is a simple chain of a subgraph H k of length ni with finite vertices aki1 , aki (ni 1) , where i 1(1)n , k 1,2 . Note that the set {akij }nji11 consists of the vertices of the graph
H k and the inner points of its edges, {a*ij }nji11 - the set of vertices of a simple chain n CGi (a*i1, a*i(ni 1) ) of graphs G with finite set of vertices a * , a*i(ni 1) , such that (a1ij a2ij ) a*ij i1 , j 1(1)ni , i 1(1)n. For n 1 option 1) and statement 2) in this case is proved. For n 2 we have the left-hand side is trivial. To do this, use the method of proving the opposite. 2 where L L( H i , G ) and the inequality holds: p1 (L) 1 . Then the graph L will have at least two i1 simple circles. Each of this circles will mean the execution of the 2) - transformations at points on at least three different pairs of simple chains without common points. The first elements of each pair will belong to a simple cycle z of graph H1 . The second elements of each pair will belong to a simple cycle z ' of the graph H 2 . As a result, at least three new 2-cells s with boundaries simple cycles, which cannot all together be the boundaries of two 2-cells s j , where SG (G 0 ) {s j }3j1 , j 2,3 . This means that at least one edge of the graph G belonging to zi one of the loops will not belong to the intersection of two 2-cells s j , si ,, which belong to the set SG (G 0 ) will be insignificant relative tG (G 0 ) to the operation of its removal. Thus we will have a contradiction to the condition of 3minimality of the graph G . Since our assumption is incorrect, we have inequality p1(L) 1 , which proves the double inequality. Since in Proposition 2) we have a transformation on one pair of simple chains, the proof is complete. graph G , only the following two types are possible: 3 a) the -transformation of type (A), given in the same way as the -transformation of a graph i1 H i into a graph G , ie on the edges (or parts of edges) of graphs H i , i 1(1)3 , has the property that - the M ' (G) can have no more than one common simple cycle. Then the following statements are made with precision to the renumbering of the elements of the set M '(G) :
1) There are elements (H i ) , i 1,2 , of the set M ' (G) with a common cycle and homeomorphic graphs K 2,3 that do not have common simple loops with the element (H 3 ) ; 2) There are elements (H i ) , i 1,2 , that do not have common simple cycles, and an element 2 homeomorphic K 2,3 has a common simple cycle with an element (U H i ) . i1
Proposition 3) is proved. We prove Proposition 4). The proof will follow as a partial case from the above proof of statement 2) and will differ in that part concerning the necessary condition of degeneracy at the point of simple chains of the second pair.
The proof of theorem 1 is complete. 2.2.
4.2. While the set L2 \ B2 is not empty to perform the following actions: 4.2.1. Take the element u from L2 \ (B3 + B4), enter the element u in the list B4; 4.2.2. We perform the identification of pairs of vertices or points of pairs of graphs (K4, K4) or (K4, K2,3) or (K2,3, K4) or (K2,3, K2,3). They are indicated as vertices or points of two different pairs of chains x and u performed on all types of possible φ-transformations for the selected pair of graphs and we obtain the graph G; 4.2.3. Procedure (G): Define the reachability number t of the set of all vertices of the graph G as the minimum number of simple cycles covering the set of all vertices of the graph G; 4.2.4. If t = 3, then perform: for each edge e of the graph G perform the operation of contraction to a point ;
G: = Ge; perform the procedure 4.2.3; If t = 3, then perform the end of the cycle on the edges of the graph G,
else derive the graph G; else the end of the cycle on the edges; 4.3. end of the internal cycle; 5. end of the external cycle; 6. While the set L4 is not empty to perform the following actions: 6.0. Take the element z from L4, enter the element x in the list B4; 6.1. L4: = L4 \ z; 6.2. While the set L4 \ B4 is not empty to perform the following actions: 6.2.1. Take the element u from L2 \ (B5 + B4), enter the element u in the list B5; 6.2.2. We identify pairs of vertices or points of pairs of graphs (K4, K4) or (K4, K2,3) or (K2,3 K4) or ( K2,3, K2,3) indicated as vertices of different pairs of cycles, performed on all possible φ-transformations for the selected pair of graphs and get the graph G; 6.2.3. Procedure (G): Determine the minimum number t of simple cycles covering the set of all vertices of the graph G; 6.2.4. If t = 3 then perform:
For each edge e of the graph G perform the contraction operation to a point;
G: = Ge, perform the procedure 6.2.3; If t = 3 then perform the end of the cycle on the edges of the graph G,
else derive he graph G; end of the cycle on the edges; 6.3. end of the internal cycle; 7. end of the external cycle; 8. end of the algorithm.
Result: Identity of non-cylindrical graphs to 3-minimal graphs with the proof of equivalence of non-cylindrical and 3-minimal planar graphs, theorem 1 on the characterization of 3-minimal planar graphs, and a modified algorithm for constructing all 3-minimal planar graphs. The 38 diagrams of 3minimal planar graphs as result presented in the figure 2.
Task: To construct the set of all nonisomorphic 2-minimal projective-planаг graphs in which the
fixed set of points is located on the two boundaries of 2-cells or pseudo-cells. Similarly of this task was
the tasks for graphs with number of vertexes less then 10 on various genus, which solved in [
Definition 1. For a given embedding f , f : G S , a graph G in S and a given set of points , G0 G1 determine tG , S, f , t tG , S, f , the number of reachability of the set relative to S , if t t there is a set SG , SG S \ f (G) , which satisfies the condition: ( f si X ) ( f si X ) , i1 i1,i j j 1,2,..,t . We say that the set has a reachability number t , tG , S t , relative to S , if among all no isomorphic embedding’s f : G S , the number t is the smallest among the numbers tG , S, f . We consider further the set of points of the graph G t -non-planar concerning the surface S , or ( t , S ) non-planar, if t 2 , where tG , S t . If t 2 , S is a projective plane, and the set is the set of vertices of the graph G , X G 0 , then we will call the graph G non-outer projective planar. A graph G is outer-projective-planar if embeds on the projective plane with all vertices on the boundary of one distinguished cell.
Definition 2. Suppose the embedding f , f : G S , of the graph G in surface S , which implements t, tG , S t , where SG S \ f (G) SG si 1t . We will say that concerning a given surface S the set will have the characteristic G ( X , S, f ) , G ( X , S, f ) , 1, if there are three cells sі 13 from the set SG , on the boundaries of which the subsets i , X i X , are placed arbitrarily and satisfy the relation: G 0 s1 s2 {a1} G 0 s2 s3 {a2} G 0 s1 s3 {a3} , and generates the smallest subgraph G ' of the graph G , (possibly degenerate), contains the points ai 13 of pairwise intersection of cell boundaries sі 13 . The set will have the -characteristic G ( X ) if G ( X ) max G ( X , f ) , where the maximum is taken for all embedding’s f : G S , realizing tG , f t and G , f .
Proposition 3.1. Each non-outer projective planar subgraph with a given set of points that are not located on the boundary of one 2-cell or pseudo-cell of an arbitrary graph obstruction of the projective plane can be represented as 1-subdivision graph K4, or a φ-image of a pair of graphs homeomorphic to graphs from the set {K5, K3,3, K4, K2,3, K5 \ e} when identifying pairs of points from the connection sets both in a path and in a cycle.
3.1.
Theorem 3.1. [
Theorem 3.2. [
Begin of Algorithm 1.
Input: The set Ρ of 35 minors Pi of the projective plane N1 with equivalence classes lij where i0 ni l , ni | Pi0 | .
j1 ij Output: List of graphs. 1. : ; v : 0 ; 2. For i =1 step 1 to 35, does these steps:
begin 2.1. P0 : Pi ; 2.2. v : vi1 ; 2.3. procedure А( P0 , 0 , P00 , N 2 );
ni 2.4. Output ( P0 , j1lij ) in ; 2.5. For k = 2 step 1 to| P0 |, does these steps: begin 2.5.1. If v vik then go to the end of the cycle by k ; else 2.5.2. P0 : Pi \ v ; 0 : i ; 2.5.3. L: = Function B ( P0 , X); 2.5.4. If L == true then do: begin;
M : {u | (u,v) P01}; 2.5.4.1. If K (G) == 1 then do begin; procedure А( P0 , 0 ,M, N1 ); output ( 0 , M) in ; end; 2.5.4.2. else do begin; procedure А ( P0 , 0 ,M, 0 ); output ( 0 , M) in ; end; 3. end; 4. end;
Procedure А ( G , , M, S) do the following: // Must construct the embedding of a graph G (without vertices of degree 2) with a given number of vertices in the surface S (Euclidean plane, projective plane or Klein surface) and determine the cells on the boundaries of which are the set of vertices M //.
If a graph G has a subgraph or part of the graph Н is homeomorphic K 5 or K3,3 , then we construct the embedding of these graphs in the projective plane, otherwise, we attach a graph to the Euclidean plane 0 . In nested graphs K 5 or K3,3 a projective plane, there are cells s5 , s33 with the following boundaries: s5 - a cycle of length 5 and 5 triangles for K 5 , or s33 - a cycle of length 6 and 4 quadrilaterals for K3,3 , in which we will embed stars with centers taken from the subset G 0 \ H 0 .
First of all, we will put all these stars in cells with either cycle boundaries of length 5 for or length 6 for and try to use no more than one additional Mobius strip glued to the cells s5 or s33 . The number of vertices | G 0 | of the obstruction graph of the projective plane is at least 12. The number of options for the location of the centers and edges of stars, not more than 7 stars, is equal r 7 because each center of the star does not belong to two cells, where r the number of cells of the graph embedded in the projective plane r 6 for K 5 , r 5 for K3,3 .
The time complexity of procedure А ( G , , M, S) is proportional O(r 7 ) .
The function K (G) will determine the presence or absence of a graph G of a subgraph or part of a
homeomorphic K 5 or K3,3 and will give it out. To do this, we need to examine the complement of the
G graph G for the presence of a subgraph of five isolated vertices, K 5 , or two triangles without
common vertices, i.e. 2K 3 . If such subgraphs of the graph are detected, the function K (G) will give 1
and return to algorithm 1 the found vertices as vertices of the graph K5 or K3,3 . In the absence case K 5 ,
2K 3 the function K (G) will give 0. The function В ( P0 , Х) checks for the presence of an isomorphism
of a graph P0 with another element of the set of graphs X and will have polynomial complexity [
The part of the output result of algorithm 1 is on figures 3, 4.
The authors gratefully acknowledge the support and help of officers of the organizing committee.