Mathematical model. Algorithm for identifying strongly connected components

Let G(V,X) be a pseudograph and let vertices v and w (v¹w) of this graph be connected by a route. Then there must be a minimal route connecting these vertices. Let us denote the length of this route as d(v, w). We also set d(v, v) =0 for any vertex vÎV; d(v, w) = ¥ if there is no route connecting v and w.

The value d(v,w) defined in this way for any vertices v and w of the graph G(V, X) is called the distance between v and w.

The number of distances in a graph with n vertices is equal to the number of combinations C n 2 .

Let the graph G(V,X) be connected. Let us define the following concepts for it:

Count Diameter: d(G) = maxd(v, w).

Eccentricity (maximum offset) of the vertex: r(v) = maxd(v, w);

Graph radius: r(G) = min r(v);

Graph center: any vertex vÎV such that r(v) = r(G).

The diameter of the graph, the eccentricities of the vertices, the radius of the graph and the centers of the graph are called the metric characteristics of the graph.

Example. Find the metric characteristics of the graph given by the diagram:

Let's find all the distances, taking into account that d(v, w) = d(w, v).

The number of distances in this graph C 5 2 = 5!/3!2! = 10: d(v 1 , v 2) = 1, d(v 1 , v 3) = 2, d(v 1 , v 4) = 2, d(v 1 , v 5) = 3, d(v 2, v 3) = 1, d(v 2, v 4) = 1, d(v 2, v 5) = 2, d(v 3, v 4) = 1, d(v 3, v 5) = 2, d(v 4, v 5) = 1.

Diameter of the graph d(G) =3.

Vertex eccentricities: r(v 1) = 3, r(v 2) = 2, r(v 3) = 2, r(v 4) = 2, r(v 5) = 3.

Graph radius r(G) = 2.

The centers of the graph are v 2, v 3, v 4.

3. Minimum routes in loaded graphs

A graph G(V, X) is called loaded if a function called a weight function is specified on the set of edges of the graph, which assigns each edge x ОХ of the graph a certain number l(x). The value l(x) is called the arc length.

The value l(x) can be given different meaning: transportation costs, travel time, distance between points, gasoline consumption, etc.

The sum of the lengths of the edges included in a route is called the route length.

Note that if for all x О Х l(x) = 1, then the graph can be considered as unloaded.

A route in the graph G(V, X) from vertex v to vertex w (v¹w) is called minimal if it has the minimum length among all routes in the graph G(V, X) from vertex v to vertex w.

Let us restrict ourselves to graphs for which l(x)>0.

When searching for the minimum route in a loaded graph with l(x)>0

Let's use the same statement as for the unloaded graph, namely:

any minimal route is a simple circuit.

Let us now consider the problem of finding the minimum route in a loaded graph.

Let the graph G(V,X) be loaded, the number of vertices n ³ 2, it is necessary to construct a minimal route from v 1 to v n .

Let's present the algorithm.

Step 1. Assign an index a(v i) to each vertex: a(v 1) = 0, a(v i) = ¥, i ¹ 1. Color the vertex v 1 and put v = v 1.

Step 2. For each uncolored vertex v j change the index according to the rule:

a(v j) = min (a(v j), a(v) + l(v, v j)).

Color the vertex for which a(v j) is the smallest. Also color the edge leading to the selected one. this step vertex v j . Set v = v j .

Step 3. If v = v j, end the procedure, since the shortest route is from v 1 to v n. if v ¹ v n , then go to step 2.

Comment. Step 2 is impossible if all a(v j)= ¥. In this case, the vertex v n is unreachable.

Let us apply the described algorithm to the graph specified by the diagram. Let us find in it the shortest route from v 1 to v 6.

Step 1. Color the vertex v 1 . Let's assign indices to the vertices: a(v 1) =0, a(v 2) = a(v 3)=…= a(v n)=¥. We assume v 1 = v.

a(v 2) = min (¥, 0+4) = 4,

a(v 3) = min (¥, 0+7) = 7,

a(v 4) = min (¥, 0+3) = 3,

a(v 5) = min (¥, 0+¥) = ¥,

a(v 6) = min (¥, 0+¥) = ¥.

Color the vertex v 4 and the edge (v 1 , v 4 ).

Step 3. Since vertex v 6 is not colored, we perform step 2, assuming v = v 4 .

a(v 2) = min (4, 3+¥) = 4,

a(v 3) = min (7, 3+¥) = 7,

a(v 5) = min (¥, 3+3) = 6,

a(v 6) = min (¥, 3+¥) = ¥.

Color the vertex v 2 and the edge (v 1 , v 2 ).

Step 3. Since vertex v 6 is not colored, we perform step 2, assuming v = v 2.

a(v 3) = min (7, 4+3) = 7,

a(v 5) = min (6, 4+2) = 6,

a(v 6) = min (¥, 4+¥) = ¥.

Color the vertex v 5 and the edge (v 4 , v 5 ).

Step 3. Since vertex v 6 is not colored, we perform step 2, assuming v = v 5 .

a(v 3) = min (7, 6+¥) = 7,

a(v 6) = min (¥, 6+2) = 8.

Color the vertex v 3 and the edge (v 1 , v 3 ).

Step 3. Since vertex v 6 is not colored, we perform step 2, assuming v = v 3 .

a(v 6) = min (8, 7+2) = 8.

Color the vertex v 6 and the edge (v 5 , v 6 ).

Since vertex v 6 is colored, we stop working. We have obtained the minimum route v 1 v 4 v 5 v 6 , the length of which is 8 .

Note that this is in in this case not the only minimal route for vertices v 1 and v 6, because in the algorithm it was possible to color instead of the edge (v 4, v 5) the edge (v 2, v 5), then we would get another route of the same length.

4. Problems on trees

A graph is called acyclic if it has no cycles.

A graph without cycles is called a forest.

A tree is a connected acyclic graph.

In the last section, we emphasized that the adjacency matrix $A$ introduced there, or more precisely the vertex adjacency matrix of the graph, plays a very important role significant role in graph theory. We noted the advantages of this matrix - it is square, equal to the number rows of the incidence matrix $B$, i.e., as a rule, contains smaller number elements. Secondly, this matrix stores all the information about the edges of the graph and, with a given numbering of vertices, uniquely describes the graph. The adjacency matrix, like the incidence matrix of a graph, is a (0,1) matrix, i.e. its elements can be considered as elements of other algebraic structures, and not just as elements of the set of integers. In particular, we noted that the elements of the adjacency matrix can be considered as elements of Boolean algebra, subject to the laws of Boolean arithmetic, but did not properly explain this. Before filling this gap, let us emphasize the advantages of the adjacency matrix resulting from its squareness.

To do this, recall the rules for matrix multiplication. Let arbitrary matrices with numerical elements be given: matrix $A$ of dimension $n\times m$ with elements $a_(ik)$ and matrix $B$ of dimension $m\times q$ with elements $b_(kj)$. A matrix $C$ of dimension $n\times q$ is called the product of matrix $A$ by $B$ (the order is important) if its elements $c_(ij)$ are defined as follows: $c_(ij) = \sum\limits_( k = 1)^m (a_(ik) b_(kj))$. The product of matrices is written in the usual way $AB=C$. As we can see, the product of matrices requires consistency in the sizes of the first and second factors (the number of columns of the first factor matrix is equal to the number of rows of the second factor matrix). This requirement disappears if we consider square matrices of the same order and, therefore, we can consider arbitrary powers of a square matrix. This is one of the advantages of square matrices over rectangular ones. Another advantage is that we can give a graph interpretation to the degree elements of the adjacency matrix.

Let the adjacency matrix $A$ have the form: $A = \left(((\begin(array)(*c) (a_(11) ) & (a_(12) ) & (...) & (a_(1n ) ) \\ (a_(21) ) & (a_(22) ) & (...) & (a_(2n) ) \\ (...) & (...) & (...) & (...) \\ (a_(n1) ) & (a_(n2) ) & (...) & (a_(nn) ) \\ \end(array) )) \right)$, and her $ k$th degree — $A^k = \left(((\begin(array)(*c) (a_(11)^((k)) ) & (a_(12)^((k)) ) & (...) & (a_(1n)^((k)) ) \\ (a_(21)^((k)) ) & (a_(22)^((k)) ) & (.. .) & (a_(2n)^((k)) ) \\ (...) & (...) & (...) & (...) \\ (a_(n1)^(( k)) ) & (a_(n2)^((k)) ) & (...) & (a_(nn)^((k)) ) \\ \end(array) )) \right)$, where $k = 2,3,...$ Obviously, $A^k$, like the matrix $A$, will be a symmetric matrix.

Let $k=2$. Then $a_(ij)^((2)) = \sum\limits_(k = 1)^n (a_(il) a_(lj))$ ($i,j = 1,2,...,n $), and each term $a_(il) a_(lj)$ is equal to either $0$ or $1$. The case when $a_(il) a_(lj) = 1$ means that there are two edges in the graph: the edge $$i,l$$ (since $a_(il) = 1)$ and the edge $$ l,j$$ (since $a_(lj) = 1$) and therefore the path $$( \(i,l$, $l,j$ )\)$ from $i$- th vertex to the $j$th vertex of length two (a path of two edges). Here we're talking about it is about a path, not a chain, since the direction indicated is from the $i$th vertex to the $j$th vertex. Thus, $a_(ij)^((2))$ gives us the number of all paths on the graph (in the geometric interpretation of the graph) of length 2 leading from the $i$-th vertex to the $j$-th.

If $k=3$, then $A^3 = A^2A = AA^2 = AAA$ and $a_(ij)^((3)) = \sum\limits_(l_1 = 1)^n (a_( il_1 ) ) a_(l_1 j)^((2)) = $ $\sum\limits_(l_1 = 1)^n (a_(il_1 ) ) \left((\sum\limits_(l_2 = 1)^n ( a_(l_1 l_2 ) a_(l_2 j) ) \right) =$ $\sum\limits_(l_1 = 1)^n (\sum\limits_(l_2 = 1)^n (a_(il_1 ) ) ) a_( l_1 l_2 ) a_(l_2 j) = \sum\limits_(l_1 ,l_2 = 1)^n (a_(il_1 ) a_(l_1 l_2 ) a_(l_2 j) )$.

The term $a_(il_1 ) a_(l_1 l_2 ) a_(l_2 j) $ if it is equal to 1, defines a path of length 3 going from the $i$-th vertex to the $j$-th and passing through the vertices $l_1$ and $l_2$. Then $a_(ij)^((3))$ gives us the number of paths of length 3 connecting the $i$th and $j$th vertices. IN general case$a_(ij)^((k))$ specifies the number of paths of length $k$ connecting the $i$-th and $j$-th vertices. In this case, $a_(ij)^((k)) = \sum\limits_(l_1 ,l_2 ,...,l_(k - 1) = 1)^n (a_(il_1 ) a_(l_1 l_2 ) .. .) a_(l_(k - 2) l_(k - 1) ) a_(l_(k - 1) j)$.

It is clear that the value $a_(ii)^((k)) $ gives us the number of closed paths of length $k$ starting and ending at vertex $i$. Thus, a path of length 2 - $a_(il) a_(li)$, means a path passing along the edge $$ i,l $$ from vertex $i$ to vertex $l$ and back. Therefore $a_(ii)^((2)) = s_i$, i.e. the diagonal elements of the matrix $A^2$ are equal to the degrees of the corresponding vertices.

Let us now consider, along with the matrix $A$, the matrix $\dot (A)$, which differs from the matrix $A$ only in that its elements (numbers 0 or 1) are considered as elements of Boolean algebra. Therefore, actions with such matrices will be carried out according to the rules of Boolean algebra. Since the actions of adding and multiplying matrices with Boolean elements are reduced to the actions of adding and multiplying the elements of these matrices according to the rules of Boolean arithmetic, we hope that this will not lead to difficulties. A matrix with Boolean elements will be called a Boolean matrix. It is obvious that the operations of addition and multiplication of Boolean matrices are closed on the set of Boolean matrices, i.e. the result of these operations will again be a Boolean matrix.

Obviously, for a given numbering of vertices, there is a one-to-one correspondence between Boolean adjacency matrices and graphs. Therefore, the graph interpretation of the actions of addition and exponentiation of Boolean adjacency matrices is of interest (in the general case, the product of two symmetric matrices of the same order is not necessarily a symmetric matrix).

The result of adding two Boolean symmetric matrices of the same order will be a Boolean symmetric matrix of the same order with zeros in those places where both terms have zeros and ones in those places where at least one term has a one. In the graph interpretation, this operation is called the operation graph addition. The sum of two graphs, given on the same set of vertices with the same numbering, a graph is called whose vertices i and j are non-adjacent if they are non-adjacent in both graph-components, and vertices i and j are adjacent if they are adjacent in at least one graph-summand.

Let us now interpret the second degree of the Boolean adjacency matrix $\dot (A)^2$ with elements $\dot (a)_(ij)^((2)) = \sum\limits_(l = 1)^n (\dot ( a)_(il) \dot (a)_(lj) )$. It is clear that $\dot (a)_(ij)^((2)) = 1$ if at least one term $\dot (a)_(il) \dot (a)_(lj) $ is equal to 1 and $\dot (a)_(ij)^((2)) = 0$ if all terms are equal to 0. If the matrix $\dot (A)$ is the adjacency matrix of some graph, i.e. is a symmetric (0,1) matrix with a zero main diagonal, then the matrix $\dot (A)^2$, generally speaking, is not an adjacency matrix of a graph in the sense we accept, since all its diagonal elements are equal to 1 (if the graph has no isolated vertices). So that such matrices can be looked at as adjacency matrices, we must, when considering connections between the vertices of some connected system that define this system as a graph, allow some vertices to be connected to themselves. An “edge” that defines the connection of a certain vertex with itself is called loop. Further, as before, by the word graph we will mean a graph without loops, and about a graph with loops, if this is not clear from the context, we will say so - a graph with loops.

Consider the sum $\dot (A)^() = \dot (A) + \dot (A)^2$. The matrix $\dot (A)^()$ gives us a graph obtained from the original one by “saturating” it with additional connections corresponding to paths of length 2. That is, in the new graph the vertices $i$ and $j$ are adjacent if they are adjacent in the original graph or these vertices are connected by some path of length 2, and vertices $i$ and $j$ are non-adjacent, if they are non-adjacent in the original graph and there is no path of length 2 connecting these vertices.

$\dot (A)^() = \dot (A) + \dot (A)^2 + \dot (A)^3$ is defined similarly. That is, in the graph given by the matrix$\dot (A)^()$ vertices $i$ and $j$ are adjacent if they are adjacent in the graph $\dot (A)^()$ or these vertices are connected by some path of length 3 in the original graph, and vertices $i$ and $j$ are nonadjacent if they are nonadjacent in the graph $\dot (A)^()$ and there is no path of length 3 connecting these vertices in the original graph. And so on.

In general, $\dot (A)^([k]) = \sum\limits_(i = 1)^k (\dot (A)^i) $. It is easy to see that all $\dot (A)^([k])$ for $k \ge n - 1$, where $n$ is the order of the matrix $\dot (A)$, are equal to each other. Indeed, if the vertices $i$ and $j$ are connected, then there is a path (chain) connecting these vertices, and, therefore, there is a simple path (simple chain) connecting these vertices. The maximum possible simple path in an $n$-vertex graph has length $n-1$ (a simple path connecting all distinct vertices of the graph). Therefore, if in the matrix $\dot (A)^()$ there is a 1 at the place $(i,j)$, then at the same place in the matrix $\dot (A)^([k])$ at $k \ge n - 1$ will also be 1, since the matrix $\dot (A)^()$ is included as a Boolean term in the definition of the matrix $\dot (A)^([k])$. If in the matrix $\dot (A)^()$ there is 0 in place of $(i,j)$, then this means that there is no simple chain in the graph connecting the $i$-th and $j$- vertices, and, therefore, there is no chain connecting these vertices at all. This means that in the case under consideration and in the matrix $\dot (A)^([k])$ for $k \ge n - 1$ there will be 0 in place ($i$,$j)$. This is what our statement proves about the equality of all matrices $\dot (A)^([k])$ for $k \ge n - 1$ to the matrix $\dot (A)^()$ and, therefore, to each other.

The matrix $\dot (A)^()$ is called matrix of the transitive closure of the matrix$\dot (A)$, as well as the adjacency matrix of the transitive closure of the graph defined by the matrix $\dot (A)$. It is quite obvious that the matrix of the transitive closure of a connected graph will be the adjacency matrix complete graph, i.e. square matrix, consisting of only units. This observation also gives us a method for determining the connectivity of a graph: a graph is connected if and only if the transitive closure matrix of its adjacency matrix consists of only ones (will be the matrix of the complete graph).

The transitive closure matrix also allows us to solve the problem of partitioning a graph into connected components.

Let us now show how the transitive closure procedure allows us to construct the so-called “distance matrix”. To do this, we determine the distance between vertices $i$ and $j$. If vertices $i$ and $j$ are connected, then distance between them we call the length of the minimum (in terms of the number of edges traversed) simple path connecting these vertices; if the vertices $i$ and $j$ are disconnected, then we set the distance equal to zero (zero as the negation of any path connecting these vertices). With this definition of distance, the distance between the vertex and itself is equal to 2 (the length of the path along the edge and back). If there is a loop at the vertex, then the distance between the vertex and itself is equal to 1.

To construct a distance matrix for an $n$-vertex graph with an adjacency matrix $A$, which would indicate the distance between any two vertices, we introduce into consideration the matrices $A^($k$) = A^([k]) - A^()$, where $k = 2,3,...,n - 1$ and $A^($1$) = A^() = A$. The absence of dots above the matrix designation indicates that we consider the matrices $A^([k])$ ($k = 1,2,...,n - 1)$ as numeric (0,1)-matrices, naturally obtained from the matrices $\dot (A)^([k])$ (we now consider the Boolean elements 0 and 1 as numbers 0 and 1). From the method of constructing matrices $A^([k])$ it follows that $A^([k]) \ge A^()$ ($k = 2,3,...,n - 1$) and, therefore, $A^($k$)$ ($k = 1,2,...,n - 1$) are (0,1)-matrices. Moreover, the matrix $A^($2$)$ contains 1 only in those places where the vertices determined by this place (row number and column number) are connected by some path of length two and are not connected by a shorter path. Similarly, $A^($3$)$ contains 1 only at those places where the vertices defined by this place are connected by a path of length three and are not connected by any path of shorter length, etc. Thus, the matrix $D = \sum\limits_(k = 1)^(n - 1) (k \cdot A^($k$))$ will be the required distance matrix. Element $d_(ij)$ of this matrix will be equal to the distance between vertices $i$ and $j$. The distance between vertices $u$ and $v$ will also be denoted as $d(u,v)$.

Comment. Specific product term $a_(il_1 ) a_(l_1 l_2 ) ...a_(l_(k - 2) l_(k - 1) ) a_(l_(k - 1) j) = 1$ element $a_(ij )^((k))$ of the $k$-th power of the adjacency matrix $A^k$ specifies a specific $(i,j)$-path $i$i,l_1$l_1 $l_1 ,l_2 $l_2 ...l_(k - 2) $l_(k - 2) ,l_(k - 1) $l_(k - 1) $l_(k - 1) ,j$j$ from $i$ -th vertex to $j$-th. Sequence of adjacent vertices and edges connecting them $i$i,l_1 $l_1 $l_1 ,l_2 $l_2 ...l_(k - 2) $l_(k - 2) ,l_(k - 1) \ )l_(k - 1) \(l_(k - 1) ,j$j$ is also called $(i,j)$-route. A route differs from a chain consisting only of different adjacent edges in that the route allows equal edges. A simple route consists of various adjacent vertices and edges, i.e. practically coincides with a simple chain.

It is quite obvious that the element $d_(ij) $ of the distance matrix determines the length of the minimum chain connecting the $i$th vertex to the $j$th vertex.

Let's consider examples of the graphs given by Figures 1 and 2, their adjacency matrices and their distance matrices.

Fig. 1 (Graph $\Gamma _1$, adjacency matrix $A_1$, distance matrix $D_1$).
$A_1 = \left(((\begin(array)(*c) 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \end(array) )) \right), $
$D_1 = \left(((\begin(array)(*c) 2 & 1 & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 1 & 2 & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 1 & 1 & 2 & 1 & 1 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 1 \\ 1 & 1 & 1 & 2 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 2 & 2 & 1 & 2 & 2 & 1 & 1 & 1 & 2 & 1 & 2 & 2 & 1 \\ 3 & 3 & 2 & 3 & 1 & 2 & 1 & 1 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 1 & 1 & 2 & 1 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 1 & 1 & 1 & 2 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & 1 & 1 & 1 & 2 \\ 2 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 1 & 1 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & 2 & 2 & 1 & 2 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 1 & 1 & 1 & 2 & 2 \\ 2 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 2 \\ \end(array) )) \right) $

Rice. 2 (Graph $\Gamma _2$, adjacency matrix $A_2$, distance matrix $D_2$).
$A_2 = \left(((\begin(array)(*c) 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0\ \ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end(array) )) \right)$,
$D_2 = \left(((\begin(array)(*c) 2 & 1 & 2 & 3 & 4 & 5 & 6 & 4 & 4 & 5 \\ 1 & 2 & 1 & 2 & 3 & 4 & 5 & 3 & 3 & 4 \\ 2 & 1 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 3 \\ 3 & 2 & 1 & 2 & 1 & 2 & 3 & 1 & 1 & 2\ \ 4 & 3 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 3 \\ 5 & 4 & 3 & 2 & 1 & 2 & 1 & 3 & 3 & 4 \\ 6 & 5 & 4 & 3 & 2 & 1 & 2 & 4 & 4 & 5 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 3 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 1 \\ 5 & 4 & 3 & 2 & 3 & 4 & 5 & 3 & 1 & 2 \\ \end(array) )) \right). $

From the matrices $D_1$ and $D_2$ one can easily determine diameters$d_1$ of the graph $\Gamma _1$ and $d_2$ of the graph $\Gamma _2$, as the maximum values of the elements of these matrices. So $d_1 = 3$, and $d_2 = 6$.

In addition to the distance matrix, graph theory also considers other matrices, the elements of which are determined through the length of the path. Such, for example, is traversal matrix. IN traversal matrix$(i,j)$th element equal to length the longest path (longest chain) from the $i$th vertex to the $j$th vertex, and if there are no such paths at all, then, in accordance with the definition of distance, the $(i,j)$th element of the traversal matrix is set equal to zero .

We will make a note at the end of the section about methods for determining the minimum and maximum chains using a matrix of distances connecting the $i$-th and $j$-th vertices in the graph.

Now let’s give some more definitions of graph theory related to distances between vertices and which are easily determined from distance matrices.

Eccentricity$e(v)$ of a vertex $v$ in a connected graph $\Gamma$ is defined as max $d(u,v)$ over all vertices $u$ in $\Gamma$. Radius$r(\Gamma)$ is the smallest eccentricity of the vertices. Note that the largest of the eccentricities is equal to the diameter of the graph. A vertex $v$ is called the central vertex of the graph $\Gamma$ if $e(v) = r(\Gamma)$; center graph $\Gamma$ is the set of all central vertices.

So for the graph $\Gamma _1$ from Fig. 1, the eccentricity of vertex 13 will be equal to 2 ($e(13) = 2$). Peaks 3, 5 and 10 will have the same eccentricities ($e(3) = e(5) = e(10) = 2$). An eccentricity equal to 2 will be the smallest for the graph $\Gamma _1$, i.e. $r(\Gamma _1) = 2$. The center of the graph $\Gamma _1$ will consist of vertices 3, 5, 10 and 13. The largest eccentricity will be 3 and will be equal, as noted above, to the diameter of the graph $\Gamma _1$.

For the graph $\Gamma _2$ from Fig. 2, the only vertex 4 will have the smallest eccentricity ($e(4) = r(\Gamma _2) = 3$). Consequently, the center of the graph $\Gamma _2$ consists of one vertex 4. The diameter of the graph $\Gamma _2$, as noted above, is 6.

The graph $\Gamma _2$ is a tree, and the structure of the center of any tree is described by the theorem given below.

The Jordan–Sylvester theorem. Each tree has a center consisting of either one vertex or two adjacent vertices.

Proof. Let us denote by $K_1$ a graph consisting of one isolated vertex, and by $K_2$ a graph consisting of two vertices connected by an edge. By definition, we put $e(K_1) = r(K_1) = 0$. Then the theorem will be true for $K_1$ and $K_2$. Let us show that any tree $T$ has the same central vertices as a tree $(T)"$ obtained from $T$ by removing all its hanging vertices. It is clear that the distance from a given vertex $u$ to any other vertex $v$ can reach highest value only if $v$ is a hanging vertex.

Thus, the eccentricity of each vertex of the tree $(T)"$ is exactly one less than the eccentricity of the same vertex in $T$. It follows that the vertices of the tree $T$ that have the smallest eccentricity in $T$ coincide with the vertices that have the smallest eccentricity in $(T)"$, i.e. the centers of the trees $T$ and $(T)"$ coincide. If we continue the process of removing pendant vertices, we will obtain a sequence of trees with the same center as that of $T$. Since $T$ is finite, we will necessarily arrive at either $ K_1$, or to $K_2$. In any case, all the vertices of the tree obtained in this way form the center of the tree, which, therefore, consists of either a single vertex or two adjacent vertices.

Let us now show how, using the distance matrix, we can determine, for example, the minimal chain connecting vertex 4 to vertex 8 on the graph $\Gamma _1$. In the matrix $D_1$ the element $d_(48) = 3$. Let's take the 8th column of the matrix $D_1$ and find in the column all elements of this column equal to 1. At least one such element will be found due to the connectedness of the graph $D_1$. In fact, there will be three such units in the 8th column, and they are located in the 5th, 6th and 7th rows. Let's now take the 4th row and look at the elements in it located in the 5th, 6th and 7th columns. These elements will be 2, 3 and 3 respectively. Only the element located in the 5th column is equal to 2 and, together with 1, located at the place (5,8), gives the sum 3. This means that vertex 5 is included in the chain $$ \(4,?$, $? ,5$, $5,8$ \)$. Let us now take the 5th column of the matrix and consider 1 of this column. These will be elements located in the 3rd, 6th, 7th, 8th, 10th and 13th lines. We return again to the 4th line and see that only at the intersection of the third column and the 4th line there is a 1, which in combination with the 1 in place (3.5) gives a total of 2. Therefore, the desired chain will be $$ \ (4,3$, $3,5$, $5,8$ \)$. Having now looked at Figure 1, we are convinced of the validity of the solution found.

Although about the traversal matrix modern textbooks they say that “there are no effective methods for finding its elements,” let’s remember that using the incidence matrix we can find all the chains connecting a pair of vertices in a connected graph, and therefore chains of maximum length.

Let G is a finite n-graph.

Route V G is a sequence of edges in which every two adjacent edges have a common vertex:

The number of edges in a route is called its length.

Route M called route general view chain simple chain – if its vertices are not repeated,

A route in which the starting and ending vertices coincide, i.e. , called cyclical (closed ).

Cyclic route M called general route , if vertices and edges are repeated, cycle – if its edges are not repeated, simple loop – if its vertices are not repeated (except for the beginning and end).

Graph, not containing cycles is called acyclic.

Peaks And are called coherent , if there is a route starting at and end at .

Statement: The connection relation of graph vertices is an equivalence relation and determines the partition of the set of graph vertices into disjoint subsets .

The graph is called coherent , if for any two different vertices there is a route connecting them.

Obviously, all subgraphs G(V i) of this graph are connected and are called connected components of the graph.

Distance between the peaks a And b is called the length of the minimum simple chain connecting them. The distance is indicated d(a, b) .

Metric axioms:

1) d(a, b) =d(b,a);

2) d(a, b) ≥ 0, d(a, b) = 0 ↔ a = b;

3) d(a, b) ≤ d(a, c) + d(c, b)

The distance matrix is a symmetrical square matrix of dimension , the rows and columns of which correspond to the vertices of the graph, and at the intersection of the rows and columns the distance between the vertices is written.

			…
			…
			…
…	…	…	…	…	…
			…

The last column of the matrix indicates eccentricity for each vertex: the distance from a given vertex to the most distant vertex.

. (7.1)

Diameter graph G – maximum distance between the vertices of the graph. The diameter is found by the formula:

Using the found eccentricities of the vertices, the diameter can be found using the formula:

. (7.2)

Radius graph G – minimum value eccentricity. The radius is found by the formula:

. (7.3)

Center graph G– such a peak for which .

Comment. There may not be only one center in the graph.

Diameter chain graph G diameter, connecting the most distant vertices of the graph.

Radial chain graph G– a simple chain whose length is equal to radius, connecting the center and the vertex of the graph most distant from it.

Example 7.1.

For the n-graph shown in Figure 7.1, write down 1) a general route, 2) a non-simple circuit, 3) a simple circuit, 4) a general cyclic route, 5) a non-simple cycle, 6) a simple cycle.

Solution:

1) A general route is a route in which the starting and ending vertices are different and some edges are repeated. M 1 = (1, 4 , 5, 1, 4 , 7, 3). The edge (1, 4) is repeated here.

2) A non-simple chain is a route in which the edges are not repeated, but the vertices are repeated. M 2 = (4, 3, 1 , 5, 6, 7 , 4, 1 ). Peak 1 is repeated here.

3) A simple chain is a route in which no vertices are repeated. M 3 = (4, 3, 7, 5, 6).

4) A general cyclic route is a route in which the starting and ending vertices coincide and some edges are repeated. M 4 = (1, 5 , 1, 5 , 1 ). The edge (1, 5) is repeated here.

Figure 7.1. Building routes

V undirected graph

5) A non-simple cycle is a cyclic route in which the edges are not repeated, but the vertices are repeated. M 5 = (3, 4 , 5, 7, 4 , 13). Peak 4 is repeated here.

Note that that a complex cycle occurs only in graphs in which an hourglass configuration exists.

6) A simple cycle is a cyclic route in which no vertices are repeated. M 6 = (5, 4, 3, 2, 1, 5).

Example 7.2.

For the n-graph shown in Figure 7.1, construct a distance matrix. Determine the diameter and radius of the graph. Indicate the centers of the graph. Write diametrical and radial chains

Solution:

To construct a distance matrix, we compare the rows and columns of the vertices. At the intersection of rows and columns, we indicate the distance between the corresponding vertices.

d( a, b)	1	2	3	4	5	6	7
1	0	1	1	1	1	2	2	2
2	1	0	1	2	2	3	2	3
3	1	1	0	1	2	2	1	2
4	1	2	1	0	1	2	1	2
5	1	2	2	1	0	1	1	2
6	2	3	2	2	1	0	1	3
7	2	2	1	1	1	1	0	2

The place (1, 1) is 0, since the shortest route between vertex 1 and vertex 1 is a degenerate route (without edges) of length 0.

The place (1, 2) is 1, since the shortest route between vertex 1 and vertex 2 is the only edge connecting these vertices.

In place (1, 6) there is a 2, since the shortest simple chain between vertex 1 and vertex 6 is a chain of two edges (1, 5, 6). This means that the distance between these vertices is 2.

The last column of the table indicates the distance from a given vertex to the vertex most distant from it - eccentricity. We find their values using formula (7.1).

The maximum value of the last column is the diameter of the graph. Where d(G) = 3.

The minimum value of the last column is the radius of the graph. Where r(G) = 2.

The centers are the vertices: 1, 3, 4, 5, 7. Their eccentricities are equal to the radius of the graph.

To build diametrical chains, use the distance matrix to find out which vertices are furthest from each other. Since the maximum distance between vertices is the diameter of the graph, it means that we will find vertices located at a distance equal to the diameter. These are vertices 2 and 6. Consequently, all diametrical chains in the graph connect these vertices. There are two such chains:

D 1 = (2, 1, 5, 6) and D 2 = (2, 3, 7, 6).

To build radial chains, use the distance matrix to find out which vertices are furthest from the centers.

From center 1, at a distance of radius equal to 2, there are vertices 6 and 7. This means that radial chains can be drawn:

R 1 = (1, 5, 6) and R 2 = (1, 4, 7).

From center 3 at a radius distance there are vertices 5 and 6. This means that radial chains can be drawn:

R 3 = (3, 4, 5) and R 4 = (3, 7, 6).

Calculating distances and determining routes in a graph is one of the most obvious and practical problems that arise in graph theory. Let us introduce some necessary definitions.

Eccentricity graph vertices – the distance to the maximum vertex from it. For a graph for which it is not defined weight its edges, the distance is defined as the number of edges.

Radius graph is the minimum eccentricity of the vertices, and diameter graph – maximum eccentricity of vertices.

Center the graph is formed by vertices whose eccentricity equal to the radius. The center of the graph can consist of one, several or all vertices of the graph.

Peripheral the vertices have an eccentricity equal to the diameter.

A simple chain with a length equal to the diameter of the graph is called diametrical .

Theorem 12.1.In a connected graph, the diameter is no greater than the rank of its adjacency matrix.

Theorem 12.2.(Jordan) Every tree has a center consisting of one or two adjacent vertices.

Theorem 12.3.If the diameter of the tree is even, then the tree has a single center, and all diametrical chains pass through it; if the diameter is odd, then there are two centers and all diametrical chains contain an edge connecting them.

Obviously practical significance center of the graph. If, for example, we are talking about a graph of roads with city vertices, then it is advisable to place in the mathematical center administrative center, warehouses, etc. The same approach can be applied to a weighted graph, where the distances are the weights of the edges. As a weight, you can take the Euclidean distance, time or cost of movement between points.

Example 12.5. Find the radius, diameter and center of the graph shown in Fig. 12.1.

Solution. In this task it is convenient to use distance matrix S. An element of this square symmetric matrix is equal to the distance between the vertices i and the top j. For the graph shown in Fig. 12.1, the distance matrix has next view:

Let's calculate the eccentricity of each vertex. This value can be defined as the maximum element of the corresponding column of the distance matrix (or row - since the matrix S symmetrical). We get

Graph radius r– minimum eccentricity of the vertices. In this case r= 2. Vertices No. 2, No. 4 and No. 5 have such eccentricity. These vertices form the center of the graph. Count Diameter d– maximum eccentricity of the vertices. In this case d= 3. Peaks No. 1 and No. 3 have such eccentricity; this is the periphery of the graph. In the studied graph, the vertices turned out to be either central or peripheral. In graphs of higher order, there are other vertices.

The eccentricities of the vertices of a small graph can be easily calculated by direct calculation from the drawing. However, the graph is not always defined by its design. In addition, the graph may have big size. Therefore, another way to solve the previous problem is needed. The following theorem is known.

Theorem 12.4. Let be the adjacency matrix of a graph G without loops and , where . Then equal to the number of routes of length k from vertex to vertex.

Solving graph theory problems using various transformations of the adjacency matrix is called algebraic method .

Example 12.6. Find the distance matrix of the graph shown in Fig. 12.1, using the algebraic method.

Solution. The adjacency matrix of this graph is equal to:

We will fill out the distance matrix by considering the degrees of the adjacency matrix. The units of the adjacency matrix show pairs of vertices that have a distance of one between them (i.e., they are connected by a single edge).

The diagonal elements of the distance matrix are zeros. Multiply the adjacency matrix by itself:

According to the theorem, between vertices 2 and 3, 1 and 4, etc. there is a certain number of routes of length 2 (since the degree of the matrix is two). The number of routes is not used here; the very fact of the presence of a route and its length are important, as indicated by the non-zero element of the matrix degree, which does not coincide with the element noted when calculating a route of shorter length. We put 2 in the empty elements of the distance matrix and get next approximation:

The distance between vertices 1 and 3 remains unknown. We will multiply the adjacency matrix on itself until in the matrix non-zero element will not appear . Then the corresponding element of the distance matrix equal to the power adjacency matrices: . At the next step we get

hence, , and finally

The resulting matrix coincides with the distance matrix S(12.2), found by direct calculations from the figure.

1. Assign p=1 (p − number of connected components), .

2. Include in the set of vertices V p strongly connected components D p vertices corresponding to the units of the first row of the matrix S p . As a matrix A(D p) take a submatrix of the matrix A(D AV p .

3. Cross out from S p rows and columns corresponding to vertices from V p. If there are no rows (and columns) left, then p- number of strongly connected components. Otherwise, we denote the matrix remaining after deleting the term and columns as S p +1 , we assign p= p+1 and go to step 2.

Example

Let us highlight the connected components of the directed graph shown in Fig. 1. In this problem, the number of vertices n= 5.

This means that for a given directed graph the adjacency matrix will have a dimension of 5×5 and will look like this

Let's find the reachability matrix for a given directed graph using formula 1) from statement 3:

,
,

Hence,

Thus, the strongly connected matrix obtained by formula 2) of statement 3 will be as follows:

We assign p=1
and compose the set of vertices of the first strongly connected component D 1: these are the vertices that correspond to ones in the first row of the matrix S(D). Thus, the first strongly connected component consists of one vertex
.

Crossed out from the matrix S 1 (D) row and column corresponding to the vertex v 1 to get matrix S 2 (D):

We assign p=2. The set of vertices of the second connected component will consist of those vertices that correspond to the ones in the first row of the matrix S 2 (D), that is
. Constructing an adjacency matrix for a strongly connected component
original graph D − as its quality we take a submatrix of the matrix A(D), consisting of matrix elements A, located at the intersection of rows and columns corresponding to the vertices of V 2:

Crossed out from the matrix S 2 (D) rows and columns corresponding to the vertices from V 2 to get the matrix S 3 (D), which consists of one element:

and assign p=3. Thus, the third strongly connected component of the original graph, like the first, consists of one vertex
.

Thus, 3 components of strong connectivity of a directed graph are identified D:

Task 2. Distances in a directed graph

Use the wavefront algorithm to find distances in a directed graphD: diameter, radius and centers.

Let
directed graph with n³2 vertices and v,w (v¹ w) – given vertices from V.

Algorithm for finding the minimum path from a directed graph

(wave front algorithm).

Otherwise we continue:

Otherwise we have found the minimum path from V
and its length is k. Vertex sequence

there is this minimum path. The work is completed.

Notes

To find distances in a directed graph, you need to construct a minimum distance matrix R(D) between its vertices. This is a square matrix of dimensions
, the elements of the main diagonal of which are equal to zero (
,i=1,..,n).

First we create an adjacency matrix. Then we transfer the units from the adjacency matrix to the minimum distance matrix (
, If
). Next, fill the matrix line by line as follows.

Let's look at the first row, which contains ones. Let this be a string − i-taya and at the intersection with j-th column is one (that is
). This means that from the top you can get to the top in one step. We are considering j-th term (a line should be entered into consideration if it contains at least one unit). Let element
. Then from the top to the top you can get there in two steps. Thus, we can write
. It should be noted that if there are two or more ones in the lines under consideration, then all possible options for getting from one vertex to another should be considered, recording the length of the shortest of them in the matrix.

Note: In the test, find the longest path using the wave front algorithm.

Example

Let's find distances in a directed graph D, shown in Fig. 2. In this problem, the number of vertices n= 7, therefore, the adjacency and minimum distance matrices between the vertices of a directed graph D will have a dimension of 7x7.

Adjacency matrix:

Let's start filling out the matrix R(D) minimum distances: first put zeros along the main diagonal And r ij =a ij, If a ij=1, (i.e. we transfer units from the adjacency matrix). Let's look at the first line. There are two units here, that is, from the first vertex in one step you can get to the second and sixth. From the second vertex you can get to the third in one step (we are not interested in the path to the first vertex), therefore, we can write
. From the sixth peak we can reach the fifth and seventh in one step, which means
,
. Now we are looking for routes emanating from the first vertex, consisting of 3 steps: in 2 steps we go to the third vertex, from there in one step we get to the fourth, so
. As a result, we get the following matrix:

Thus, the diameter of the directed graph under study will be
.

For each vertex of a given oriented graph, we find the maximum distance (eccentricity) in the graph G from its vertex using the formula given above
:r(v i) is the maximum of the distances standing in i-that line. Thus,

r(v 1)=3, r(v 2)=3, r(v 3)=5, r(v 4)=4, r(v 5)=2, r(v 6)=2, r(v 7)=3.

So, the radius graph G will

Accordingly, the centers of the graph G there will be peaks v 5 and v 6, since the values of their eccentricities coincide with the value of the radius
.

Let us now describe finding the minimum path from a vertex v 3 to the top v 6 according to the wave front algorithm. Let's denote the vertex v 3 how V 0 and the top v 6 - how W(see Fig. 3). The set of vertices belonging to the image V 0, consists of one element - this is the vertex v 4, which, according to the algorithm, is denoted as V 1: FW 1 (v 3)={v 4 ). Since the desired vertex does not belong to the front of the first level wave
, we continue the algorithm. We build the wave front of the second level - this is a set of vertices belonging to the image of the vertex V 1: FW 2 (v 3)={v 7 ), denote v 7 ≡V 2. Into the image of the peak V 2 includes two vertices - v 5 and v 4, but, since v 4 was already marked as V 0, then the wave front of the third level consists of one element: FW 3 (v 3)={v 5 }, v 5 ≡V 3. From unlabeled vertices to vertex image V 3 included v 1 and v 2, respectively, FW 4 (v 3)={v 1 , v 2 }, v 1 ≡V 4 , v 2 ≡V 4 . Now all vertices are marked except v 6, which is included in the image of the vertex
, that is FW 5 (v 3)={v 6 ≡W), the algorithm is completed. Minimum path (5 steps) from a vertex v 3 to the top v 6 looks like this: v 3 v 4 v 7 v 5 v 1 v 6 .