Bracket form of graph description
I was prompted to write this note by the article “ Storing hierarchical data in a flat form, ” in which the author is engaged in solving the problem of storing a comment tree in the form of a flat text. A tree is a graph, so I remembered a young and little-known apparatus for describing graphs with their brackets, which I came across in the process of writing a dissertation. I will tell you about the technology for constructing bracket images of graphs.
The author of the described approach is the senior researcher of the Institute of Semiconductor Physics of the SB RAS V.A. Melentiev. A new way of formally describing graphs was first proposed by him in 2000 in the article "A bracing form for describing graphs and its use in structural studies of robust computing systems."
Two forms of graph description are well known: graphic and matrix. The graphic form is a mapping on the plane of an enumerable set of vertices in the form of nodes (points) and communication lines (arcs, edges) directly connecting these vertices. The matrix form, depending on the choice of the rows and columns forming the matrix, is called the adjacency matrix (rows and columns correspond to the vertices of the graph), the incidence matrix (rows - vertices, columns - edges) and the adjacency matrix of the edges (the elements of rows and columns are the edges of the graph). It is clear that, in contrast to the graphical form, the matrix implies the introduction of unique symbols of the corresponding elements of the graph, for example, numbering.
In order to avoid discrepancies, I will give some well-known definitions, as well as basic information about the graph images used in the article.
')
A graph G is an ordered pair of G (V, E) , in which V is a non-empty set of vertices or nodes, E is a set of pairs of vertices called edges.
The vertices u and v are called terminal vertices (or simply the ends) of the edge e = {u, v} . The edge, in turn, connects these vertices. Two end vertices of the same edge are called adjacent.
The degree deg (v) of a vertex v is the number of edges for which it is terminal. Simply put, this is the number of edges emanating from the top.
The image P (v i ) of the graph G (V, E) is the description of the graph in the bracket form, the starting point (angle of which) is the vertex v i ∈ V.
The set N (w) is the environment of the vertex w consisting of s (w) = deg (w) vertices.
The set M i is the set of vertices located on the i- th projection level.
C i - the total number of vertices of the i -th projection level.
The objects of research are, as a rule, connected non-oriented graphs with equal weighted edges without multiple edges and without loops. Let us demonstrate the construction of the bracket projection using the example of a unit cube.
For better visual perception of the image and for convenience of working with it, we structure the bracket description of the graph in the form of a finite set of levels. Choose a vertex of choice (the choice can be arbitrary or motivated, in our case v 0 = 0) and place it at the zero level, place the vertices adjacent to it on the 1st level above and to the right of the initial one. The environment of the angle vertex N (0) = {1, 2, 3} constitutes the set of vertices of the 1st level: M 1 = {1, 2, 3}, | M 1 | = C 1 = 3.
0 {1, 2, 3}
So, on the zero and first levels of the image of the graph under consideration, one vertex from | V | = 8 and three edges from | E | = 12
Continue the description to level 2. The set M 2 vertices of the 2nd level combines C 1 = 3 subsets, which are environments (without the vertex 0 immediately preceding these subsets) of the three vertices of the 1st level:
M 2 = M 21 U M 22 U M 23 = {4, 5} U {4, 6} U {5, 6} = {4, 5, 6}, with C 2 = 6, and | M 2 | = 3
We get:
0 {1 {4, 5} , 2 {4, 6} , 3 {5, 6} }
In the general case, starting from the 2nd level, each subsequent level is a set, not a set of vertices, since it can include duplicate elements. Note that M 1 U M 2 ≠ V , therefore, the construction of the projection should be continued with the next level.
The set of M 3 vertices of the 3rd level consists of 6 subsets, which are the environments of the corresponding 6 vertices of the 2nd level, each of which is modified by subtracting the sets of the vertices preceding this environment:
M 3 = M 34 1 U M 35 1 U M 34 2 U M 36 1 U M 35 2 U M 36 2 .
Here, the first digit of the subscript indicates that it belongs to the corresponding level of the projection, the second identifies the top of the graph, and the upper index is used for the additional indexation of several instances of the same vertex at the level of projection under consideration. From the projection thus constructed
0 {1 {4 {2, 7} , 5 {3, 7} } , 2 {4 {1, 7} , 6 {3, 7} } , 3 {5 {1, 7} , 6 {2, 7 } } }
it can be seen that only on the 3rd level there appears a vertex 7, which is not included in any of the subsets of the previous levels: M 3 = {2, 7} U {3, 7} U {1, 7} U {3, 7} U {1,7} U {2, 7} = {1, 2, 3, 7}. C 3 = 12. | M 3 | = 4. The record of the same projection in the single-line version is
P 3 (0) = 0 {1 {4 {2, 7}, 5 {3, 7}}, 2 {4 {1, 7}, 6 {3, 7}}, 3 {5 {1, 7} , 6 {2, 7}}}.
The opening brackets in front of one or another subset of vertices indicate its nesting, and the number of brackets “not covered” by closing ones determines the level of nesting of this subset into the sets of predecessor vertices. The level of nesting of a subset in the set of descendants of the angle vertex (the number of the level in the projection) determines its distance from the vertices of the corresponding subset.
The projection of the graph P k (v o ) is considered complete if it defines all vertices and all edges (adjacencies) of this graph. From the above projection P 3 (0) it can be seen that both the vertex and edge completeness conditions are fulfilled here only at the 3rd level:
M 0 U M 1 U M 2 U M 3 = V , | M 0 U M 1 U M 2 U M 3 | = | V | = 8
E 0 U E 1 U E 2 U E 3 = E , | E 0 U E 1 U E 2 U E 3 | = | E | = 12
Each level of the bracket image of a non-weighted graph contains a set of terminal vertices of all unique (not repeated) simple chains emanating from the initial vertex, whose lengths are equal to the number of this level.
Consider the set of vertices of the k -th level. The specified set includes end vertices of all outgoing simple chains from the initial vertex, whose lengths are equal to the number of this level, including the vertices whose distance from the initial vertex of the image is equal to the number of this level. This cannot include vertices whose distance from the initial vertex exceeds the level number k .
If the graph is Hamiltonian, then in the set of its vertices there exists such that the number of levels of the maximum image, including zero, is equal to the number of vertices of the graph.
In contrast to the well-known graphical and matrix representations, the bracket image of the graph is highly informative, since in addition to the information explicitly given on the sets of vertices and edges of the graph and their adjacency or incidence, information on the explicit or easily extractable form is presented sets of routes between vertices, about their lengths, etc. The presence in the description of the graph of additional information allows you to replace fairly time-consuming algorithms, for example, searching for shortest routes, finding routes that do not intersect for a pair of vertices, detecting the radius, diameter and circumference of the graph, eccentricity of its vertices and many other typical tasks on graphs with a fairly simple operation of sampling objects "lying on the surface" of such a description.
A significant gain in labor intensity is even more obvious when comparing several sets of subgraphs between themselves, since the proposed form of their presentation makes it possible to exclude multiple repetitions of previously executed branches or their sections. Attempts to fix such areas in subsequent algorithms for later use as intermediate results lead to an unjustified complication of the logic of these algorithms for particularly complex graphs, which, in turn, can lead to the opposite effect: an increase in the complexity of such algorithms due to their lack of transparency ".
The device of bracket images was successfully tested by Melent'ev in solving some classical problems of graph theory, in particular, on shortest and non-intersecting routes, on eccentricities of vertices, on diameter of a graph, etc.
List of works V.A. Melentyeva
The author of the described approach is the senior researcher of the Institute of Semiconductor Physics of the SB RAS V.A. Melentiev. A new way of formally describing graphs was first proposed by him in 2000 in the article "A bracing form for describing graphs and its use in structural studies of robust computing systems."
So what is the point?
Two forms of graph description are well known: graphic and matrix. The graphic form is a mapping on the plane of an enumerable set of vertices in the form of nodes (points) and communication lines (arcs, edges) directly connecting these vertices. The matrix form, depending on the choice of the rows and columns forming the matrix, is called the adjacency matrix (rows and columns correspond to the vertices of the graph), the incidence matrix (rows - vertices, columns - edges) and the adjacency matrix of the edges (the elements of rows and columns are the edges of the graph). It is clear that, in contrast to the graphical form, the matrix implies the introduction of unique symbols of the corresponding elements of the graph, for example, numbering.
In order to avoid discrepancies, I will give some well-known definitions, as well as basic information about the graph images used in the article.
')
A graph G is an ordered pair of G (V, E) , in which V is a non-empty set of vertices or nodes, E is a set of pairs of vertices called edges.
The vertices u and v are called terminal vertices (or simply the ends) of the edge e = {u, v} . The edge, in turn, connects these vertices. Two end vertices of the same edge are called adjacent.
The degree deg (v) of a vertex v is the number of edges for which it is terminal. Simply put, this is the number of edges emanating from the top.
The image P (v i ) of the graph G (V, E) is the description of the graph in the bracket form, the starting point (angle of which) is the vertex v i ∈ V.
The set N (w) is the environment of the vertex w consisting of s (w) = deg (w) vertices.
The set M i is the set of vertices located on the i- th projection level.
C i - the total number of vertices of the i -th projection level.
The objects of research are, as a rule, connected non-oriented graphs with equal weighted edges without multiple edges and without loops. Let us demonstrate the construction of the bracket projection using the example of a unit cube.
For better visual perception of the image and for convenience of working with it, we structure the bracket description of the graph in the form of a finite set of levels. Choose a vertex of choice (the choice can be arbitrary or motivated, in our case v 0 = 0) and place it at the zero level, place the vertices adjacent to it on the 1st level above and to the right of the initial one. The environment of the angle vertex N (0) = {1, 2, 3} constitutes the set of vertices of the 1st level: M 1 = {1, 2, 3}, | M 1 | = C 1 = 3.
0 {1, 2, 3}
So, on the zero and first levels of the image of the graph under consideration, one vertex from | V | = 8 and three edges from | E | = 12
Continue the description to level 2. The set M 2 vertices of the 2nd level combines C 1 = 3 subsets, which are environments (without the vertex 0 immediately preceding these subsets) of the three vertices of the 1st level:
M 2 = M 21 U M 22 U M 23 = {4, 5} U {4, 6} U {5, 6} = {4, 5, 6}, with C 2 = 6, and | M 2 | = 3
We get:
0 {1 {4, 5} , 2 {4, 6} , 3 {5, 6} }
In the general case, starting from the 2nd level, each subsequent level is a set, not a set of vertices, since it can include duplicate elements. Note that M 1 U M 2 ≠ V , therefore, the construction of the projection should be continued with the next level.
The set of M 3 vertices of the 3rd level consists of 6 subsets, which are the environments of the corresponding 6 vertices of the 2nd level, each of which is modified by subtracting the sets of the vertices preceding this environment:
M 3 = M 34 1 U M 35 1 U M 34 2 U M 36 1 U M 35 2 U M 36 2 .
Here, the first digit of the subscript indicates that it belongs to the corresponding level of the projection, the second identifies the top of the graph, and the upper index is used for the additional indexation of several instances of the same vertex at the level of projection under consideration. From the projection thus constructed
0 {1 {4 {2, 7} , 5 {3, 7} } , 2 {4 {1, 7} , 6 {3, 7} } , 3 {5 {1, 7} , 6 {2, 7 } } }
it can be seen that only on the 3rd level there appears a vertex 7, which is not included in any of the subsets of the previous levels: M 3 = {2, 7} U {3, 7} U {1, 7} U {3, 7} U {1,7} U {2, 7} = {1, 2, 3, 7}. C 3 = 12. | M 3 | = 4. The record of the same projection in the single-line version is
P 3 (0) = 0 {1 {4 {2, 7}, 5 {3, 7}}, 2 {4 {1, 7}, 6 {3, 7}}, 3 {5 {1, 7} , 6 {2, 7}}}.
The opening brackets in front of one or another subset of vertices indicate its nesting, and the number of brackets “not covered” by closing ones determines the level of nesting of this subset into the sets of predecessor vertices. The level of nesting of a subset in the set of descendants of the angle vertex (the number of the level in the projection) determines its distance from the vertices of the corresponding subset.
The projection of the graph P k (v o ) is considered complete if it defines all vertices and all edges (adjacencies) of this graph. From the above projection P 3 (0) it can be seen that both the vertex and edge completeness conditions are fulfilled here only at the 3rd level:
M 0 U M 1 U M 2 U M 3 = V , | M 0 U M 1 U M 2 U M 3 | = | V | = 8
E 0 U E 1 U E 2 U E 3 = E , | E 0 U E 1 U E 2 U E 3 | = | E | = 12
Some properties of bracket image
Each level of the bracket image of a non-weighted graph contains a set of terminal vertices of all unique (not repeated) simple chains emanating from the initial vertex, whose lengths are equal to the number of this level.
Consider the set of vertices of the k -th level. The specified set includes end vertices of all outgoing simple chains from the initial vertex, whose lengths are equal to the number of this level, including the vertices whose distance from the initial vertex of the image is equal to the number of this level. This cannot include vertices whose distance from the initial vertex exceeds the level number k .
If the graph is Hamiltonian, then in the set of its vertices there exists such that the number of levels of the maximum image, including zero, is equal to the number of vertices of the graph.
And how to use it?
In contrast to the well-known graphical and matrix representations, the bracket image of the graph is highly informative, since in addition to the information explicitly given on the sets of vertices and edges of the graph and their adjacency or incidence, information on the explicit or easily extractable form is presented sets of routes between vertices, about their lengths, etc. The presence in the description of the graph of additional information allows you to replace fairly time-consuming algorithms, for example, searching for shortest routes, finding routes that do not intersect for a pair of vertices, detecting the radius, diameter and circumference of the graph, eccentricity of its vertices and many other typical tasks on graphs with a fairly simple operation of sampling objects "lying on the surface" of such a description.
A significant gain in labor intensity is even more obvious when comparing several sets of subgraphs between themselves, since the proposed form of their presentation makes it possible to exclude multiple repetitions of previously executed branches or their sections. Attempts to fix such areas in subsequent algorithms for later use as intermediate results lead to an unjustified complication of the logic of these algorithms for particularly complex graphs, which, in turn, can lead to the opposite effect: an increase in the complexity of such algorithms due to their lack of transparency ".
The device of bracket images was successfully tested by Melent'ev in solving some classical problems of graph theory, in particular, on shortest and non-intersecting routes, on eccentricities of vertices, on diameter of a graph, etc.
Literature
List of works V.A. Melentyeva
Source: https://habr.com/ru/post/126502/
All Articles