G(V,X) with loops but without multiple arcs defines a binary relation X on the set V. The complete graph corresponds to a universal relation. An undirected graph corresponds to a symmetric relation. The complement of a graph corresponds to the complement of a relation. Changing the direction of the arcs corresponds to the inverse relationship.
Digraphs and binary relations are the same class of objects described by different means. Binary relations and functions are the basic tools for constructing the vast majority of mathematical models used to solve practical problems, and graphs can be visually represented in the form of a diagram. This explains the widespread use of diagrams of various types in coding and design.
Vertex b of a 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 starting vertex, V is the final vertex). Thus, on the set of vertices of a digraph (graph), not only the adjacency relation A, but also the reachability relation T is defined.
Reachability matrix T digraph (graph) G is called T 2 n×n, the elements of which are found from the condition: 1, if reachable from ; 0 if not reachable from .
Definition of the digraph reachability matrix as a matrix of reflexive and transitive closure of the adjacency relation.
The introduced reachability relation on the vertices of the graph G(V,X): a vertex w is reachable from a vertex v if v = w or there is a path from v to w in G. In other words, reachability is a reflexive and transitive closure of the contiguity relation.
Find the adjacency matrix, transitive and reflexive closure.
Connectivity in graphs. Weak, one-sided and strong connectivity in digraphs. Matrix of connectivity and strong connectivity. Connectivity components. Determination of a strong connectivity matrix based on the reachability matrix.
G(V,X) is called coherent, 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 weakly connected, if the corresponding non-digraph obtained by removing the orientation of the arcs is connected.
A digraph that is not weakly connected is called incoherent.
Component of a strong bond of a digraph G(V,X) is called the maximal, in terms of the number of occurrences of vertices, strongly connected subgraph of this digraph. The connected component of a non-digraph is defined similarly.
Matrix of strong connectivity (connectivity) digraph (graph) G(V,Х) is called S n×n, the elements of which are found from the condition: 1, if reachable from and reachable from ; 0 if not reachable from and not reachable from .
(digraph) strongly connected or connected, for this it is sufficient to determine the presence of 0 in the matrix if
0 no, then the graph (digraph) is connected (strongly connected), otherwise not.
The strong connectivity matrix can be constructed from the reachability matrix using the formula
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, that is, is there a path going from vertex x i to vertex x j. If such a path exists, then we say that vertex x j is reachable from vertex x i. One can be interested in the reachability of vertex x j from vertex x i only on paths whose lengths do not exceed a given value or whose length is less the largest number vertices in a graph, etc. problems.
Reachability in a graph is described by the reachability matrix R=, i, j=1, 2, ... n, where n is the number of vertices in the graph, 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 such elements x j for which the (i, j)th element in achievability 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 length of 0. Since direct mapping 1st order Г +1 (x i) is the set of 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 that are reachable from x i using paths of length 2. Similarly, Г +p (x i) is the set of vertices that are reachable from x i using paths of length p.
Since any vertex in the graph that is reachable from x i must be reachable using a path (or paths) of length 0 or 1 or 2, ..., or p, then set of vertices, reachable for vertex x i, can be represented in the form
As we see, the set of reachable vertices R(x i) is a straight line transitive closure vertices x i, i.e. R (x i) = T + (x i) . Consequently, 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.
Rice. 4.1.
For the graph shown in Fig. 4.1,a, the reachability sets are found as follows:
Reachability Matrix looks like shown in Fig. 4.1,c. Reachability Matrix can be constructed using the adjacency matrix (Fig. 4.1, b), forming sets T + (x i) for each vertex x i.
Counter-reachability 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.
Let G = (X, G) - graph of modular structure, x r, X-. - vertices belonging to X. If in the column G there is an oriented chain from x, to XP then vertex x,- - reachable from vertex x,-. The following statement is true: if the vertex Xj reachable from x, ah (- from XP That X/ reachable from x^ The proof of this fact is obvious. Consider a binary relation on the set X, which determines the reachability between the vertices of the graph. Let us introduce the notation x, -> x, for the reachability of vertex x, - from Xj. The relation is transitive. Let us denote by R(x) the set of vertices of the graph G, reachable from x; . Then equality
defines the transitive closure of x, with respect to reachability.
Let us prove the following theorem.
Theorem 1.1. For a selected connected component of a modular structure graph, any vertex is reachable from the root one corresponding to this component, i.e. equality holds (X/- root node)
Proof. Suppose the vertices (x, e X) is unreachable from Xj. Then x, е X/ and the set X" = X x), non-empty. Since the selected graph component is connected, there are vertices x, - e x, and the chain /7(x; , xj), leading from x, to x,-. Based on the acyclicity of the graph G, V X" there must be a simple chain H(x/, xj), where to the top x f arcs are not included (this chain may be empty if X" consists only of x,). Consider the chain R(x/, xj) = N(x/, x,) U I (x, xj). This means that modulus 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, g 6 will never be executed. Thus, the results of Theorem 1.1 strengthen the requirement that there are no directed cycles in the module graph.
To analyze the matrix representation of the reachability relation of a modular structure graph, 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 degree of adjacency matrix Defines the number of different routes containing / arcs and connecting a vertex X/s vertex of a ^-oriented graph.
Consider the following three corollaries from this theorem.
Corollary 1.1. Matrix М = "? J M t, Where M- adjacency matrix oriented
graph with P vertices, coincides, up to the numerical values of the coefficients, with the reachability matrix A.
Proof. In a directed graph containing P vertices, the maximum path length 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 the number of arcs n. Let the coefficient t 1) matrices M different from zero. This means that there is a degree of the matrix M>, which has a corresponding coefficient T () is also different from zero. Therefore, there is a path going from the vertex Xj To XP those. vertex ^ is reachable from x g This corollary determines the connection between the call matrix of the modular structure graph, which coincides with the adjacency matrix A/, and the reachability matrix A and determines the algorithm for constructing the latter.
Corollary 1.2. Let for some i in the sequence of degrees 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. Hence, Xj reachable from x v those. there is a cycle. According to Theorem 1.2, this cycle has / arcs (in the general case, repeating).
Corollary 1.3. Let p-i degree of adjacency matrix M p of the acyclic graph coincides with the zero matrix (all coefficients are 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 arc. And this path can only be an oriented cycle. Therefore, all coefficients M p for an acyclic graph are equal to zero. This corollary provides the necessary and sufficient condition absence of cycles in the graph of the modular structure.
For acyclic graphs, the reachability relation is equivalent to partial strict ordering. The transitivity of the reachability relation is discussed above. Antisymmetry follows from the absence of oriented cycles: if a vertex X ) reachable from x v then the opposite is not true. Let us introduce the notation x x > Xp if the top Xj reachable from the 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, then the chain breaks x p > x i2 > ... > x in . Vertex xjn has no outgoing arcs, i.e. element xin 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 plan: Circuit routes and cycles. Graph connectivity and connected components. Diameter radius and center of the graph.
Share your work on social networks
If this work does not suit you, at the bottom of the page there is a list of similar works. You can also use the search button
Baranov Viktor Pavlovich. Discrete Math. Section 3.Graphs, networks, codes.
Lecture 8. Reachability and connectivity in graphs
Lecture 8. REACHABILITY AND CONNECTIVITY IN GRAPHS
Lecture outline:
- Routes, chains and cycles.
- Graph connectivity and connected components.
- Diameter, radius and center of the graph.
- Matrices of reachability and counter-reachability.
- Routes, chains and loops
Directed route(or by ) of a digraph is a sequence of arcs in which the final vertex of any arc different from the last one is the starting vertex of the next one. In Fig. 1 arc sequences
, (1)
, (2)
(3)
are paths.
Rice. 1.
Chain oriented(or chain ) is a path in which each arc and With Used no more than once. So, for example, paths (2) and (3) are orceps, but path (1) is not, since the arc is used twice in it.
Simple is called an orchain in which each vertex is used at most once O th time. For example, chain (3) is simple, but chain (2) is not.
Route is an undirected double of a path, that is, a sequence of edges in which each edge, with the exception of the first and last, is connected by end vertices to the edges and. The bar above the arc symbol means that it is treated as an edge.
In the same way that we defined orchains and simple chains, we can define chains and simple chains.
A path or route can also be represented as 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 coincides with the end h the new vertex of the arc. Closed chains (chains) are called orcycles (cycles ). Orcycles are also called contours . Closed simple chains (chains) are called are simple orcycles(in cycles). Closed routeis unoriented n ny twin of a closed p at ty.
- Graph connectivity and connected components
A vertex in a digraph is said to be reachable from the vertex if there is a path. If at the same time from is reachable, 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 are achievable. An example of a strong digraph is shown in Fig. 2 a. Since in the column they e If there is an orcycle that includes all vertices, then any two of them and they are achievable.
° ° °
° ° ° ° ° °
° ° ° ° ° °
a B C
Rice. 2.
The digraph is calledone-way connected or one-sided , 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 accessible vertices. The vertex has a zero degree of approach, which means that there are no paths leading to this vertex. In this case, any of the four remaining vertices is reachable.
The digraph is called weakly connected or weak , if it contains any two vertices with o united halfway . A half-path, unlike a path, can have the opposite direction V line arcs. An example of a weak digraph is shown in Fig. 2nd century Obviously, there are no n in the graph at between the vertices and, but there is a halfway consisting of opposite n A straightened arcs etc.
If for some pair of vertices there is no route connecting them, then A what 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 O ronny subgraph andweak componentthe weakest subgraph.
The concept of a strong component is illustrated in Fig. 3.
° ° ° ° ° °
° ° ° °
° ° ° ° ° °
° ° ° ° ° °
° ° °
° ° ° ° °
Rice. 3
A graph that is one-way connected contains six strong d graphs, only of which are strong components n tami. The concept of a one-sided component is illustrated similarly. In this note e The one-sided component coincides with the graph itself. If you change the orientation A tion of an arc, for example, to the opposite one, we obtain a weak graph with two one-point O ronny components, one of which is formed by the vertices, and the other by the vertices r tires.
For an undirected graph, we define a bin on the set of its vertices R nary relation, assuming if there is a chain connecting with. This is the attitude of the region A gives the properties of reflexivity, symmetry and transitivity, that is, it is about T wearing equivalence. It splits a set of vertices into disjoint classes: . Two vertices from the same class are equivalent, that is, the graph has a chain connecting them; for vertices from different classes there is no such chain. Since the ends are l Yu If the edges are in a relation, then the set of edges of the graph will also be divided into disjoint classes: , where through denotes the set of all edges whose ends belong to, .
The graphs are connected and add up to a graph. These graphs are calledconnectivity componentsgraph. Number is another numerical characteristic of the graph. For a connected graph, if the graph is disconnected, then.
If a given graph is not connected and splits into several components, then the solution to 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.
- Diameter, radius and center of the graph
For a connected graph we define distance between its two vertices and as the length of the shortest chain connecting these vertices, and denote by. The chain length is the number of edges that make up the chain. It's easy to check what you've entered. n This distance satisfies the axioms of the metric:
2) ;
3) .
Let us determine the distance from each vertex of the graph to the farthest vertex from it
which is calledeccentricity. Obviously, the eccentricity for all vertices in a complete graph equal to one, and for vertices of a simple cycle .
The maximum eccentricity is called diameter graph, and the minimum radius graph. In a complete graph we have, and in a simple cycle .
A vertex is called central if. The graph may have several b to such vertices, and in some graphs all vertices are central. In a simple circuit with odd number only one of the vertices is central, and if their number is even With There are two such peaks. 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. 4.
° °
° ° °
° °
° °
Rice. 4.
To solve this problem, it is convenient to pre-calculatedistance matrix between the vertices a 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 A va from the line. The largest of these numbers is equal to the diameter of the graph, the smallest p A dius graph. The center of the graph is made up of the central vertices and.
The concepts of central vertex and center of a graph appeared in connection with optical problems And small placement of public service points, such as hospitals, fire stations, public order points, etc., when it is important to minimize And greater distance from any point of some network to the nearest service point and niya.
- Matrices of achievability and counter-achievability
Achievability Matrixis defined as follows:
The set of graph vertices reachable from a given vertex consists of such elements for which the th element in the matrix is equal to 1. This set can be represented as
Contra-achievability matrix (inverse reachability) I defined is as follows:
Similar to the construction of a reachable set, one can form multiply O gesture using the following expression:
From the definitions it follows that the th column of the matrix coincides with the th row of the matrix T rits, i.e., where is a matrix transposed to a matrix.
Example 2. Find matrices of reachability and counter-reachability for the graph, etc. And shown in Fig. 5.
Rice. 5.
Let us define reachability sets for the vertices of the graph:
Consequently, the attainability and counter-attainability matrices have the form:
Since is a set of such vertices, each of which belongs to at least one path going from k, then the vertices of this set are called and are essential or integral relative to the end vertices and. All other vertices are calledinsignificant or redundant , since removing them does not affect the paths from to.
You can also define matrices limited achievements and counter-achievement And bridges if we require that the lengths of the paths do not exceed a certain given number. Then will be an upper bound on the length of admissible paths.
The graph is called transitive , if from the existence of arcs and trace at no arc exists.Transitive closuregraph is a graph where is the minimum possible set of arcs necessary for the graph to be transitive. Obviously, the graph's reachability matrix coincides with the graph's adjacency matrix if we put ones in the matrix on the main diagonal.
By analogy with the reachability graph, we define a strong reachability graph.
Definition:
Let be a directed graph. Strong reachability graph
For 
also has many vertices 
and the next set of edges 
in the column 
peaks 
And 
mutually accessible.
Based on the reachability graph matrix 
easy to build matrix 
strong reachability graph. Indeed, from the definitions of reachability and strong reachability it immediately follows that for all pairs 
,
, element value 
equals 1 if and only if both elements 
And 
are equal to 1, i.e.
By matrix 
it is possible to identify the components of a strongly connected graph 
in the following way:
We repeat the second step until all vertices are distributed among the components.
In our example for the graph 
example 14.1. by matrix 
we obtain the following matrix of the strong reachability graph
Using the procedure described above, we find that the vertices of the graph 
are divided into 4 components of strong connectivity: 
,
,
,
. On the set of strongly connected components we also define the reachability relation.
Definition:
Let 
And 
– strongly connected components of the graph 
. Component 
achievable from components 
, If 
or there are two such vertices 
And 
, What 
reachable from 
.
strictly achievable from 
, If 
And 
reachable from 
. Component 
is called minimal if it is not strictly reachable from any component.
Since all vertices in one component are mutually reachable, it is easy to understand that the relations of reachability and strict reachability on components do not depend on the choice of vertices 
And 
.
The following characteristic of strict reachability is easily deduced from the definition.
Lemma: The strict reachability relation is a partial order relation, i.e. it is anti-reflexive, anti-symmetric and transitive.
This relationship can be represented as a directed graph, the vertices of which are the components, and the edge 
means that 
strictly achievable from 
. Below is the component graph for the graph in Example 14.1.
In this case there is one minimal component 
.
In many applications, a directed graph represents a distribution network of some resource: product, goods, information, etc. In such cases, the task of finding the minimum number of such points (vertices) from which this resource can be delivered to any point in the network naturally arises.
Definition:
Let 
- directed graph. Subset of vertices 
called generating, if from the vertices 
you can reach any vertex of the graph. Subset of vertices 
is called the base of a graph if it is generating, but no proper subset of it is generating.
The following theorem allows us to efficiently find all bases of a graph.
Theorem:
Let
- directed graph. Subset of vertices
is the base
if and only if contains one vertex from each minimal strongly connected component
and does not contain any other vertices.
Proof:
Let us first note that each vertex of the graph is reachable from a vertex belonging to some minimal component. Therefore, the set of vertices 
, containing one vertex from each minimal component, is generating, and when any vertex is removed from it, it ceases to be so, since the vertices from the corresponding minimal component become unreachable. That's why 
is the base.
Back if 
is a base, then it must include at least one vertex from each minimal component, otherwise the vertices of such a minimal component will be inaccessible. No other peaks 
cannot contain, since each of them is reachable from already included vertices.
From this theorem follows the following procedure for constructing one or listing all bases of the graph 
:
Example 14.3:
Let's define all bases of a directed graph 
.
At the first stage, we find the components of strong connectivity 
:
At the second stage, we construct a strict reachability graph on these components.
We define the minimum components: 
,
And 
.
Finally we list all four bases 
:
,
,
And 
.