Reachability ratio of graph modules. Digraphs and Binary Relations

The questions of reachability for digraphs and methods for finding the reachability and counterreachability matrices are considered. A matrix method is considered for finding the number of paths between any vertices of a graph, as well as finding the set of vertices included in the path between a pair of vertices. The purpose of the lecture: To give an idea of ​​reachability and counterreachability and how to find them

Reachability and Counterreachability

Tasks in which the concept is used reachability, quite a bit of.

Here is one of them. Graph may be a model of some organization in which people are represented by vertices, and arcs interpret communication channels. When considering such a model, one can ask whether information from one person i can be transferred to another person j , i.e., is there a path going from vertices i to vertices j . If such a path exists, then we say that the vertices j achievable from vertices i . One can be interested in the reachability of vertices j from vertices i only on paths whose lengths do not exceed a given value or whose length is less than the largest number of vertices in the graph, etc. of the problem.

The reachability in the graph is described by the reachability matrix R=, i, j=1, 2, ... n, where n is the number of graph vertices, and each element is defined as follows:

r ij =1, if vertices j are reachable from x i ,

r ij =0, otherwise.

The set of vertices R(x i) of the graph G, reachable from a given vertex x i , consists of elements x i for which the (i, j)-th element in the reachability matrix is ​​equal to 1. Obviously, all diagonal elements in the matrix R are equal to 1, since each vertex is reachable from itself by a path of length 0. Since the first-order direct mapping Г +1 (x i) is the set of such vertices x j that are reachable from x i using paths of length 1, then the set Г + (Г +1 (x i)) = Г +2 (x i) consists of vertices reachable from x i using paths of length 2. Similarly, r + p (x i) is the set of vertices that are reachable from x i using paths of length p.

Since any graph vertex that is reachable from x i must be reachable using a path (or paths) of length 0 or 1, or 2, ..., or p, then the set of vertices reachable for vertex x i can be represented as

R (x i) = ( x i ) G +1 (x i) G +2 (x i) ... G + p (x i).

As you can see, the set of reachable vertices R(x i) is a direct transitive closure of the vertex x i , i.e. R(x i) = T + (x i). Therefore, to construct the reachability matrix, we find reachable sets R(x i) for all vertices x i X. Setting r ij =1 if x j R(x i) and r ij =0 otherwise.

Rice. 4.1. Reachability in the graph: a - graph; b – adjacency matrix; c – reachability matrix; r is the counterreachability matrix.

For the graph shown in fig. 4.1, a, reachable sets are located as follows:

R (x 1) = ( x 1 ) ( x 2 , x 5 ) ( x 2 , x 4 , x 5 ) ( x 2 , x 4 , x 5 ) = ( x 1 , x 2 , x 4 , x 5 ),

R (x 2) = ( x 2 ) ( x 2 , x 4 ) ( x 2 , x 4 , x 5 ) ( x 2 , x 4 , x 5 ) = ( x 2 , x 4 , x 5 ),

R (x 3) = ( x 3 )( x 4 )( x 5 )( x 5 ) = ( x 3 , x 4 , x 5 ),

R (x 4) = ( x 4 )( x 5 )( x 5 ) = ( x 4 , x 5 ),

R (x 5) = ( x 5 )( x 5 ) = ( x 5 ),

R (x 6) = ( x 6 )( x 3 , x 7 )( x 4 , x 6 )( x 3 , x 5 , x 7 )( x 4 , x 5 , x 6 ) = ( x 3 , x 4, x 5, x 6, x 7),

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

Reachability matrix has the form as shown in Fig. 4.1, c. Reachability matrix can be built according adjacency matrix(Fig. 4.1b), forming setsT + (x i) for each vertex x i .

Counterreachability matrix Q = [ q ij ],i, j =1, 2, ... n, where n is the number of graph vertices, is defined as follows:

q ij =1, if from vertex x j it is possible to reach vertex x i ,

q ij =0, otherwise.

counterachievable the set Q (x i) is the set of vertices such that from any vertex of this set it is possible to reach the vertex x i . Similarly to the construction of the reachable set R (x i), we can write an expression for Q (x i):

Q (x i) = ( x i ) Г -1 (x i) Г - 2(x i) ... Г -p (x i).

Thus, it is clear that Q (x i) is nothing more than the reverse transitive closure of the vertex x i, i.e. Q (x i) = T - (x i). From the definitions, it is obvious that the column x i of the matrix Q (in which q ij =1 if x j Q (x i), and q ij =0 otherwise) coincides with the row x i of the matrix R, i.e., Q = R T , where R T is the matrix transposed to reachability matrix R.

Counterreachability matrix shown in fig. 4.1, g.

It should be noted that since all elements of the matrices R and Q are equal to 1 or 0, each row can be stored in binary form, saving computer memory costs. Matrices R and Q are convenient for processing on a computer, since from a computational point of view, the main operations are high-speed logical operations.

Finding the set of vertices included in the path

If you need to know about the vertices of the graph included in these paths, then you should remember the definitions of direct and inverse transitive closures. Since T + (x i) is the set of vertices to which there are paths from the vertex x i , and T - (x j) is the set of vertices from which there are paths to x j , then T + (x i) T - (x j) is the set of vertices , each of which belongs to at least one path going from x i to x j . These vertices are called essential or integral with respect to the two end vertices x i and x j . All other vertices of the graph are called insignificant or redundant, since their removal does not affect the paths from x i to x j .

Rice. 4.2. digraph

So for the graph in Fig. 4.2 finding the vertices included in the path, for example, from vertex x 2 to vertices 4, is reduced to finding T + (x 2) \u003d ( x 2, x 3, x 4, x 5, x 6 ),

T - (x 4) \u003d ( x 1, x 2, x 3, x 4, x 5), and their intersections T + (x 2) T - (x 4) \u003d ( x 2, x 3, x 4, x 5 ).

Matrix method for finding paths in graphs

The adjacency matrix completely defines the structure of the graph. Let's square the adjacency matrix according to the rules of mathematics. Each element of the matrix A 2 is determined by the formula

a (2) ik = n j=1 a ij a jk

The term in the formula is equal to 1 if and only if both numbers a ij and a jk are equal to 1, otherwise it is equal to 0. Since the equality a ij = a jk = 1 implies the existence of a path of length 2 from vertex x i to vertices k passing through vertex x j , then the (i -th,k-th) element of the matrix A 2 is equal to the number of paths of length 2 going from x i to k .

Table 4.1a shows the adjacency matrix of the graph shown in fig. 4.2. The result of squaring the adjacency matrix A 2 is shown in Table 4.1b.

So "1", standing at the intersection of the second row and the fourth column, indicates the existence of one path of length 2 from vertex x 2 to vertices 4 . Indeed, as we see in column in fig. 4.2, there is such a path: a 6 , a 5 . The "2" in matrix A 2 indicates the existence of two paths of length 2 from vertices 3 to vertices 6: a 8 , a 4 and a 10 , a 3 .

Similarly, for the adjacency matrix raised to the third power A 3 (Table 4.1c), a (3) ik is equal to the number of paths of length 3 going from x i to x k . It can be seen from the fourth row of matrix A 3 that there are paths of length 3: one of x 4 in 4 (a 9 , a 8 , a 5), ​​one of x 4 in

x 5 (a 9, a 10, a 6) and two paths from x 4 in 6 (a 9, a 10, a 3 and a 9, a 8, a 4). Matrix A 4 shows the existence of paths of length 4 (Table 4.1d).

Thus, if a p ik is an element of the matrix A p, then a p ik is equal to the number of paths (not necessarily or chains or simple or chains) of length p going from x i to x k .

There are quite a lot of problems in which the concept of reachability is used. Here is one of them. A graph can be a model of some kind of organization, in which people are represented by vertices, and arcs interpret communication channels. When considering such a model, one can raise the question whether information from one person x i can be transferred to another person x j , i.e., is there a path going from the top x i to the top x j . If such a path exists, then the vertex x j is said to be reachable from the vertex x i . One can be interested in the reachability of the vertex x j from the vertex x i only on such paths, the lengths of which do not exceed a given value or the length of which is less than the largest number of vertices in the graph, etc. of the problem.

The reachability in the graph is described by the reachability matrix R=, i, j=1, 2, ... n , where n is the number of graph vertices, and each element is defined as follows:

r ij =1 if vertex x j is reachable from x i ,

r ij =0 , otherwise.

Many peaks R(x i) of the graph G , reachable from a given vertex x i , consists of elements x j for which the (i, j) -th element in reachability matrix is equal to 1. Obviously, all diagonal elements in the matrix R are equal to 1, since each vertex is reachable from itself by a path of length 0. Since direct display 1st order Г +1 (x i) is the set of such vertices x j that are reachable from x i using paths of length 1, then the set G + (G +1 (x i)) = G +2 (x i) consists of vertices reachable from x i using paths of length 2. Similarly, r+p(x i) is the set of vertices that are reachable from x i using paths of length p.

Since any graph vertex that is reachable from x i must be reachable using a path (or paths) of length 0 or 1 or 2, ..., or p , then many vertices reachable for vertex x i can be represented as

As you can see, the set of reachable vertices R(x i) is a direct transitive closure vertices x i , i.e. R (x i) = T + (x i) . Therefore, to construct the reachability matrix, we find reachable sets R (x i) for all vertices . Assuming r ij =1 if and r ij =0 otherwise.

For the graph shown in fig. 4.1,a, the reachable sets are found as follows:

Reachability matrix has the form as shown in Fig. 4.1, c. Reachability matrix can be constructed from the adjacency matrix (Fig. 4.1, b), forming sets T + (x i) for each vertex x i .

Counterreachability matrix Q = [ q ij ], i, j =1, 2, ... n, where n is the number of graph vertices, is defined as follows:

q ij =1 , if from vertex x j it is possible to reach vertex x i ,

q ij =0 , otherwise.

G(V,X) with loops but no multiple arcs defines a binary relation X on the set V. The complete graph corresponds to the universal relation. An undirected graph corresponds to a symmetric relation. The complement of the graph corresponds to the complement of the relation. Changing the direction of the arcs corresponds to the reverse relationship.

Digraphs and binary relations are the same class of objects described by different means. Binary relations, functions are the basic tools for building the vast majority of mathematical models that are used to solve practical problems, and graphs can be visualized in the form of a diagram. This explains the widespread use of diagrams of various types in coding and design.

The vertex b of the digraph (graph) G is called achievable from U if and only if U=V or there is a path (route) connecting U with V (U is the initial vertex, V is the final vertex). Thus, on the set of vertices of a digraph (graph), not only the adjacency relation A is defined, but also the reachability relation T.

Reachability matrix T digraph (graph) G is called T 2 n×n, whose elements are found from the condition: 1, if it is reachable from ; 0 if not reachable from .

Definition of the reachability matrix of a digraph as a matrix of reflexive and transitive closure of the adjacency relation.

The introduced relation of reachability at the vertices of the graph G(V,X): the vertex w is reachable from the vertex v if v = w or there is a path from v to w in G. In other words, reachability is the reflexive and transitive closure of the adjacency relation.

Find adjacency matrix, transitive and reflexive closure.

Connectivity in graphs. Weak, one-way and strong connectivity in digraphs. Matrix of connectivity and strong connectivity. Connectivity components. Definition of a matrix of strong connectivity based on the reachability matrix.

G(V,X) is called connected if any of its vertices is reachable from any other vertex.

The digraph G(V,X) is called one way connected, if for any two of its vertices, at least one is reachable from the other.

The digraph G(V,X) is called strongly connected if any of its vertices is reachable from any other.

The digraph G(V,X) is called loosely connected, if the non-digraph corresponding to it, obtained as a result of deleting the orientation of the arcs, is connected.

A digraph that is not weakly connected is called incoherent.

Strong bond component of the digraph G(V,X) is called the maximal, according to the number of occurrences of vertices, strongly connected subgraph of this digraph. The connected component of a non-digraph is defined similarly.

The matrix of strong connectivity (connectivity) of the digraph (graph) G(V,Х) is called S n×n, the elements of which are found from the condition: 1, if it is reachable from and reachable from ; 0 if not reachable from and not reachable from .

(digraph) strongly connected or connected, it suffices to determine the presence of 0 in the matrix if

0 is not present, then the graph (digraph) is connected (strongly connected), otherwise not.

The strongly connected matrix can be constructed from the reachability matrix by the formula

Let G = (X, d) - graph of modular structure, х r, X-. - vertices belonging to x. If in the graph G there is an oriented chain from x, to Xp then the vertex x, - reachable from the vertex x,-. The following assertion is true: if a vertex Xj reachable from x, ax (- from Xp then x/ reachable from x^ The proof of this fact is obvious. Consider a binary relation on the set x, which determines the reachability between graph vertices. We introduce the notation x, -> x, for the reachability of the vertex x, - from Xj. The relation is transitive. Denote by H(x,) the set of vertices of the graph g, reachable from x; . Then the equality

defines a transitive closure of x, with respect to reachability.

Let us prove the following theorem.

Theorem 1.1. For a selected connected component of a graph of a modular structure, any vertex is reachable from the root corresponding to this component, i.e. equality (X/- root top)

Proof. Suppose the vertices, (x, e x) unreachable from Xj. Then x, e X/ and the set X" = X x) is not empty. Since the selected component of the graph is connected, then there are vertex x, - e x, and the chain /7(x; , xj), leading from x, to x, -. Based on the acyclicity of the graph g, in X" there must be a simple chain H(x/, xj), where to the top x f do not include arcs (this chain can be empty if X" consists only of x,). Consider the chain H(x/, xj) = H(x/, x,) U I (x, xj). This means that the x. reachable from vertices x, and Xj and both vertices do not contain incoming arcs. And this contradicts the definition of a graph of a modular structure with a single root vertex. The theorem has been proven.

The main requirement for reachability is the absence of undirected cycles in the graph. Based on the graph in Fig. 1.4, we note that the graph contains a directed cycle and modules corresponding to the vertices x 4, x 5, f 6 , will never be executed. Thus, the results of Theorem 1.1 strengthen the requirement that there are no directed cycles in the moduli graph.

To analyze the matrix representation of the reachability relation of a graph of a modular structure, consider the graph of the reachability matrix shown in Fig. 1.1.

Coefficient a, y= 1 if the module corresponding to index / is reachable from the module corresponding to index i. The following results are based on a well-known theorem from graph theory.

Rice. 1.4.

Theorem 1.2. Coefficient that l-th degrees of the adjacency matrix Extends the number of different routes containing / arcs and connecting the vertex X/s vertex of an ^-directed graph.

Consider the following three corollaries of this theorem.

Corollary 1.1. Matrix M \u003d "? J M t, where M- adjacency matrix of orientation

tired graph with P vertices, coincides up to numerical values ​​of the coefficients with the reachability matrix BUT.

Proof. In a directed graph containing P vertices, the maximum length of a path without repeating arcs cannot exceed P. Therefore, the sequence of degrees of the adjacency matrix M 1, where i = 1,2,

i, determines the number of all possible paths in a graph with n arcs. Let the coefficient t 1) matrices M different from zero. This means that there is a degree of the matrix M>, for which the corresponding coefficient t () is also different from zero. Therefore, there is a path from the top Xj to Xp those. vertex ^ is reachable from x r This corollary determines the connection of the call matrix of the graph of a modular structure, which coincides with the adjacency matrix A/, with the reachability matrix BUT and determines the algorithm for constructing the latter.

Corollary 1.2. Let for some i in the order of powers of the adjacency matrix M* there is a coefficient t X1> 0. Then there is a directed cycle in the original graph.

Proof. Let m (i > 0 for some I. Consequently, Xj reachable from x v those. there is a cycle. According to Theorem 1.2, this cycle has / arcs (generally repeating).

Corollary 1.3. Let p-i adjacency matrix degree M p acyclic graph coincides with the zero matrix (all coefficients are equal to zero).

Proof. If the graph is acyclic, then the simplest path in it cannot have more than P- 1 arc. If in M p there is a non-zero coefficient, then there must be a path consisting of P arcs. And this path can only be an oriented cycle. Therefore, all coefficients M p for an acyclic graph are zero. This corollary provides a necessary and sufficient condition for the absence of cycles in a graph of a modular structure.

For acyclic graphs, the reachability relation is equivalent to a partial strict order. The transitivity of the reachability relation was discussed above. The antisymmetry follows from the absence of directed cycles: if the vertex X ) reachable from x v then the reverse is not true. We introduce the notation x x > Xp if top Xj reachable from top x v

Let G=(X, Г) is an acyclic graph corresponding to some modular structure. Consider a descending chain of elements of a partially ordered set X:

where the “>” sign denotes the reachability relation. Because the X Of course, the chain is broken x n > x i2 > ... > x in . Vertex xjn has no outgoing arcs, i.e. element x in minimal (it corresponds to a module that does not contain calls to other modules). The maximum element in the set X is the root vertex.

• The proof of this theorem is given in the work (book): Lavrishcheva E. M., Grishchenko V. N. Assembly programming. Kyiv: Naukova Dumka, 1991. 287 p.

REACHABILITY AND CONNECTIVITY IN GRAPHS Lecture outline: Paths of a chain and cycles. Graph connectivity and connectivity components. Diameter, radius and center of the graph.

If this work does not suit you, there is a list of similar works at the bottom of the page. You can also use the search button

Baranov Viktor Pavlovich Discrete Math. Section 3Graphs, networks, codes.

Lecture 8

Lecture 8 REACHABILITY AND CONNECTIVITY IN GRAPHS

Lecture plan:

1. Routes, chains and cycles.
2. Graph connectivity and connectivity components.
3. Diameter, radius and center of the graph.
4. Reachability and counterreachability matrices.

1. Routes, circuits and loops

Oriented route(or by ) of a digraph is a sequence of arcs in which the end vertex of any arc other than the last one is the starting vertex of the next one. On fig. 1 arc sequence

, (1)

, (2)

(3)

are paths.

Rice. one.

oriented chain(or orepio ) is called the path in which each arc and With used no more than once. So, for example, paths (2) and (3) are orchains, but path (1) is not, since the arc is used twice in it.

Simple is called a chain in which each vertex is used by at most one about times. For example, orchain (3) is simple, but orchain (2) is not.

Route is an undirected twin of the path, i.e., a sequence of edges in which each edge, except for the first and last, is connected by end vertices with the edges and. A bar over an arc symbol means that it is treated as an edge.

Just as we have defined orchains and simple chains, we can define chains and simple chains.

A path or route can also be represented by a sequence of vertices. For example and measures, path (1) can be written as: .

The path is called closed , if the initial vertex of the arc in it coincides with the horse h noah apex of the arc. Closed orchains (chains) are called orcycles (cycles ). Orcycles are also called contours . Closed simple orchains (chains) called s simple orcycles(cycles). closed routeis unoriented n closed double at you.

1. Graph Connectivity and Connectivity Components

A vertex in a digraph is said to be reachable from the vertex if there is a path. If, moreover, is reachable from, then these vertices are said to be mutually reachable.

A digraph is called strongly connected or strong , if any two vertices in it are a imo achievable. An example of a strong digraph is shown in fig. 2 a. Since in the column e given an orcycle that includes all vertices, then any two of them are taken but achievable.

° ° °

° ° ° ° ° °

° ° ° ° ° °

a B C

Rice. 2.

The digraph is calledone way connected or unilateral if in any pair of its vertices at least one is reachable from the other. An example of a one-way graph is shown in fig. 2 b. This graph has an orcycle that includes four mutually reachable vertices. The vertex has a degree of entry of zero, which means that there are no paths leading to this vertex. Moreover, any of the other four vertices is reachable from it.

The digraph is called loosely connected or weak , if it contains any two vertices with about united halfway . A half path, unlike a path, can have the opposite direction. in lazy arcs. An example of a weak digraph is shown in fig. 2 in. It is obvious that the graph does not contain at ty between the vertices and, but there is a half-path consisting of opposite n a ruled arcs and.

If for some pair of vertices there is no route connecting them, then t a which digraph is called incoherent.

Three types of connected components are defined for a digraph:strong component ma k the strongest subgraph,one-sided componentmaximum single about ronny subgraph andweak componentmaximally weak subgraph.

The concept of a strong component is illustrated in Fig. 3.

° ° ° ° ° °

° ° ° °

° ° ° ° ° °

° ° ° ° ° °

° ° °

° ° ° ° °

Rice. 3

A graph that is unidirectionally connected contains six strong d graphs, of which only and are strong components n tami. The concept of a one-way component is illustrated similarly. In this note e The re one-way component is the same as the graph itself. If we change the orientation a arc, for example, to the opposite one, then we get a weak graph with two one-sided about frontal components, one of which is formed by vertices, and the other by ve r tires.

For an undirected graph, we define on the set of its vertices the bin R relation, assuming if there is a chain linking to. This relation is a gives the properties of reflexivity, symmetry and transitivity, that is, it is about t wearing equivalence. It splits the set of vertices into non-intersecting classes: . Two vertices from the same class are equivalent, that is, there is a chain in the graph that connects them; there is no such chain for vertices from different classes. Since the ends of Yu If the edges are in relation, then the set of edges of the graph will also be divided into non-intersecting classes: , where the set of all edges whose ends belong to is denoted by .

The graphs are connected and add up to a graph. These graphs are calledconnectivity componentsgraph. The number is another numerical characteristic of the graph. For a connected graph, if the graph is disconnected, then.

If the given graph is not connected and splits into several components, then the solution of any question regarding this graph, as a rule, can be reduced to the study of individual components that are connected. Therefore, in most cases it makes sense to assume that the given graph is connected.

1. Diameter, radius and graph center

For a connected graph, we define distance between its two vertices and as the length of the shortest chain connecting these vertices, and denoted by. The length of a chain is the number of edges that make up the chain. It is easy to check that you enter n This distance satisfies the axioms of the metric:

2) ;

3) .

Determine the distance from each vertex of the graph to the vertex farthest from it

which is calledeccentricity. It is obvious that the eccentricity for all vertices in the complete graph is equal to one, and for the vertices of a simple cycle .

The maximum eccentricity is called diameter graph, and the minimum radius graph. In the complete graph we have, and in the simple cycle .

A vertex is called central if. The graph may have several b such vertices, and in some graphs all vertices are central. In a simple chain, with an odd number of vertices, only one is central, and with an even number of them With there are two such vertices. In a complete graph and for a simple cycle, all vertices are central. The set of central vertices is called the center of the graph.

Example 1 Find the diameter, radius and center of the graph shown in fig. four.

° °

° ° °

° °

° °

Rice. four.

To solve this problem, it is convenient to precomputedistance matrix between the tops mi count. In this case, it will be a matrix of size, in which the distance from vertex to vertex is in place:

For each row of the matrix, we find the largest element and write it down with a wa from the dash. The largest of these numbers is equal to the diameter of the graph, the smallest p a the graph's dius. The center of the graph is formed by the central vertices and.

The concepts of the central vertex and the center of the graph appeared in connection with the problems of optimism. and small location of public service points such as hospitals, fire departments, public order stations, etc., when it is important to minimize the and greater distance from any point of some network to the nearest service point a niya.

1. Reachability and counterreachability matrices

Reachability matrixis defined as follows:

The set of graph vertices reachable from a given vertex consists of those elements for which the th element in the matrix is ​​1. This set can be represented as

Counterreachability matrix (inverse reachability) define is as follows:

Similarly to the construction of an accessible set, one can form a set about gesture using the following expression:

It follows from the definitions that the -th column of the matrix coincides with the -th row of the ma t , i.e. , where is the matrix transposed to the matrix.

Example 2 Find matrices of reachability and counterreachability for a graph, etc. and shown in Fig. 5.

Rice. 5.

Let us define the reachability sets for graph vertices:

Therefore, the reachability and counterreachability matrices have the form:

Since is the set of such vertices, each of which belongs to at least one path going from to, then the vertices of this set are called are essential or inalienable with respect to the end vertices and. All other vertices are calledinsignificant or redundant , since their removal does not affect the paths from to.

You can also define matrices limited reachability and counterreachability and bridges, if we require that the lengths of the paths do not exceed some given number. Then will be the upper bound on the length of admissible paths.

The graph is said to be transitive if from the existence of arcs and the trace at there is the existence of an arc.transitive closuregraph is a graph where is the minimum possible set of arcs necessary for the graph to be transitive. It is obvious that the reachability matrix of the graph coincides with the adjacency matrix of the graph, if we put units on the main diagonal in the matrix.