Reachability relation for vertices of a digraph. Digraphs and binary relations
Let V- set of vertices of a directed graph F, E- many of its edges. Every rib eÎ E has a beginning v'Î V and the end v''Î V. Thus, two mappings j 1 and j 2 are given, where v'=j 1 ( e) - beginning of the rib e, v''=j 2 ( e) - end of the rib e.
Several definitions can be given ways in a digraph F.
1. Path of vertices and edges- this is a sequence L(v 0 ,e 1 ,v 1 ,e 2 ,...,e n,vn), Where v i- 1 =j 1 ( e i), v i=j 2 ( e i). Vertex v 0 is called the beginning of the path L,vertex vn - end of path L, number n ribs - his length. A path consisting of one vertex has zero length.
2. Path of edges is the sequence ( e 1 ,e 2 ,...,e n). This concept of a path is analogous to the concept of a route in an undirected graph.
3. Path from the peaks is the sequence ( v 0 ,v 1 ,...,vn). A path from vertices is defined for graphs that do not contain multiple edges.
In practice, you can use the path definition that is more convenient for a given specific task.
The path is called oriented chain(or simply chain, when only digraphs are considered), if each edge occurs in it no more than 1 time, and simple oriented chain, if each vertex of the graph F is incident to at most two of its edges.
Example. Path ( e 5 ,e 6 ,e 7 ,e 1 ,e 4 ,e 3) (Fig. 3.11) is an or.chain, and the path ( e 7 ,e 1 ,e 4 ,e 3) - simple op. chain.
| Rice. 3.11. |
The path is called oriented cycle(or simply cycle, when only digraphs are considered) if it consists of more than one element and its beginning coincides with its end. As with an undirected graph, the start of the cycle is usually not fixed. The cycle is called simple, if each vertex belonging to it is incident to exactly two of its edges.
Example. Path ( e 1 ,e 4 ,e 3 ,e 2 ,e 5 ,e 6 ,e 7) - cycle, path ( e 5 ,e 6 ,e 7) - a simple cycle.
In connection with oriented chains, a theorem is valid that was proved by Redei in the study of quadratic fields.
Theorem 3.3. Let F- a finite digraph in which each pair of vertices is connected by an edge. Then in F there is a simple oriented path passing through all its vertices.
ÿ We will carry out the proof using the MI method. Let us denote the number of vertices of the graph by n.
· n=2: arc connecting two vertices of the graph F 2, and there is a simple directed path passing through all the vertices of the graph.
· Let us assume that when n= m for graph Fm the theorem is correct.
· Let us prove that when n= m+1 for the Count Fm+1 the theorem is correct.
Let's build a graph Fm+1 by adding to the graph Fm some peak v m+1 , which has edges to all vertices v i (i=1,2,...,m) from Fm. By assumption, there is a simple directed path passing through all the vertices of the graph Fm: P m=(v 1 ,v 2 ,...,v m). For edges incident to a vertex v m+1, there are three possibilities.
1. There is an arc ( v m +1, v 1). Adding it to the chain P m“on the left”, we get the desired chain passing through all the vertices of the graph Fm +1: P m +1 =(v m +1 ,v 1 ,v 2 ,...,v m).
2. There is an arc ( v m , v m+1). Adding it to the chain P m“on the right”, we get the desired chain passing through all the vertices of the graph Fm +1: P m +1 =(v m +1 ,v 1 ,v 2 ,...,v m,v m +1).
3. If in the column Fm+1 there is no arc ( v m +1 ,v 1), no arc ( v m,v m+1), then for some k (k=2,3,...,m-1) there will definitely be arcs in it ( vk,v m+1) and ( v m +1 ,vk+1). Let's make a chain
P m +1 =(v 1 ,v 2 ,...,vk,v m +1 ,vk +1 ,...,v m).
This chain goes through all the vertices of the graph Fm +1 .
On many peaks V let's set the attitude reachability R D as follows: Top v'Î V is in relation R D with top v''Î V(in this case they say that the top v'' is reachable from the top v'), if there is a path L(v',... ,v'') with the beginning v' and the end v''.
Similar to the connectivity relation for the vertices of an undirected graph, the relation reachability for vertices of a directed graph reflexively And transitively, but unlike the connectedness relation, the reachability relation not necessarily symmetrical.
Using the reachability relation, the partition of the set of vertices of a digraph into equivalence classes is determined: vertices v', v'' belong to the same class if the relation is symmetrical, i.e. v'' reachable from v', A v' reachable from v''.
Let L 1 (v', ... ,v'') And L 2 (v'', ... ,v') are the corresponding paths connecting these vertices. Then together they form a cycle passing through the vertices v' And v''. Thus, any vertices of the same equivalence class belong to some cycle. If there are no cycles in the graph, then each equivalence class consists of one vertex.
| Rice. 3.13. |
Minimal graph F B, inducing on the set of vertices V the same reachability relation as the given directed graph F, i.e. a graph with a further irreducible set of edges is called basis graph for graph F.
If there is a basis graph, then it is not necessarily unique. So, for the graph in Fig. 3.13, any a radial edge and a directed polygonal cycle define a basis graph.
If F is a finite digraph, then basis graphs exist; they can be obtained by sequentially removing “excess” edges ( v 0 ,vn), for which there is an edge-free ( v 0 ,vn) oriented chain R(v 0 ,vn).
Reachability graph
One of the first questions that arises when studying graphs is the question of the existence of paths between given or all pairs of vertices. The answer to this question is the above-introduced reachability relation on the vertices of the graph G=(V,E): vertex w is reachable from vertex v if v = w or G has a path from v to w. In other words, the reachability relation is the reflexive and transitive closure of the relation E. For undirected graphs, this relation is also symmetric and, therefore, is an equivalence relation on the vertex set V. In an undirected graph, the equivalence classes with respect to the reachability relation are called connected components. For directed graphs, reachability does not, in general, need to be a symmetric relation. Mutual reachability is symmetrical.
Definition 9.8. Vertices v and w of a directed graph G=(V,E) are said to be mutually reachable if G has a path from v to w and a path from w to v.
It is clear that the mutual reachability relation is reflexive, symmetric and transitive and, therefore, equivalence on the set of vertices of the graph. Equivalence classes with respect to mutual reachability are called strongly connected components or doubly connected components graph.
Let us first consider the question of constructing the reachability relation. Let us define for each graph its reachability graph (sometimes also called a transitive closure graph), the edges of which correspond to the paths of the original graph.
Definition 9.9. Let G=(V,E) be a directed graph. The reachability graph G * =(V,E *) for G has the same set of vertices V and the next set of edges E * =( (u, v) | in the graph G, vertex v is reachable from vertex u).
Example 9.3. Consider the graph G from Example 9.2.
Rice. 9.2. Graph G
Then we can check that the reachability graph G* for G looks like this (new loop edges for each of vertices 1-5 are not shown):
Rice. 9.3. Graph G*
How can a graph G * be constructed from a graph G? One way is to determine for each vertex of the graph G the set of vertices reachable from it, sequentially adding to it vertices reachable from it by paths of length 0, 1, 2, etc.
We will consider another method based on the use of the adjacency matrix A G of the graph G and Boolean operations. Let the set of vertices V=(v 1 , … , v n ). Then the matrix A G is an n × n Boolean matrix.
Below, to maintain similarity with ordinary operations on matrices, we will use “arithmetic” notation for Boolean operations: we will use + to denote disjunction, and · to denote conjunction.
Let us denote by E n the identity matrix of size n × n. Let's put 
. Let Our procedure for constructing G * be based on the following statement.
Lemma 9.2. Let . Then
Proof Let's do it by induction on k.
Basis. For k=0 and k=1, the statement is true by definition and .
Induction step. Let the lemma be true for k. Let us show that it remains valid for k+1. By definition we have:
Suppose that in the graph G there is a path from v i to v j of length k+1. Let's consider the shortest of these paths. If its length is k, then by the induction hypothesis a_(ij)^((k))=1. In addition, a jj (1) =1. Therefore a ij (k) a jj (1) =1 and a ij (k+1) =1. If the length of the shortest path from v i to v j is k+1, then let v r be its penultimate vertex. Then from v i to v r there is a path of length k and by the induction hypothesis a ir (k) =1. Since (v r ,v j) E, then a_(rj)^((1))=1. Therefore a ir (k) a rj (1) =1 and a ij (k+1) =1.
Conversely, if a ij (k+1) =1, then for at least one r the summand a ir (k) a rj (1) is equal to 1. If this is r=j, then a ij (k) =1 and by the inductive hypothesis, G has a path from v i to v j of length k. If r j, then a ir (k) =1 and a rj (1) =1. This means that G has a path from v i to v r of length k and an edge (v r ,v j) E. Combining them, we obtain a path from v i to v j of length k+1.
From Lemmas 9.1 and 9.2 we directly obtain
Corollary 1. Let G=(V,E) be a directed graph with n vertices and G * be its reachability graph. Then A_(G*) = . Proof. It follows from Lemma 5.1 that if G has a path from u to v u, then it also contains a simple path from u to v of length n-1. And by Lemma 5.2, all such paths are represented in the matrix.
Thus, the procedure for constructing the adjacency matrix A G* of the reachability graph for G is reduced to raising the matrix to the n-1 power. Let us make a few comments to simplify this procedure.
where k is the smallest number such that 2 k n.
If an r is found such that a ir = 1 and a rj =1, then the entire sum a ij (2) =1. Therefore, the remaining terms can be ignored.
Example 9.3. Let us consider, as an example, the calculation of the matrix of the reachability graph A G* for the graph G presented in Fig.9.2. In this case
Since G has 6 vertices, then . Let's calculate this matrix:
and (the last equality is easy to check). Thus,
As we can see, this matrix really defines the graph presented in Fig.9.3.
Mutual reachability, strongly connected components and graph bases
By analogy with the reachability graph, we define a strong reachability graph.
Definition 9.10. Let G=(V,E) be a directed graph. The strong reachability graph G * * =(V,E * *) for G has the same set of vertices V and the next set of edges E * * =( (u, v) | in the graph G the vertices v and u are mutually reachable).
Using the matrix of the reachability graph, it is easy to construct a matrix of the strong reachability graph. Indeed, from the definitions of reachability and strong reachability it immediately follows that for all pairs (i,j), 1 i,j n, the value of an element is 1 if and only if both elements A G* (i, j) and A G* (j, i) are equal to 1, i.e.
Based on the matrix, we can identify the strongly connected components of the graph G as follows.
Let us place in component K 1 vertex v 1 and all vertices v j such that A_(G_*^*)(1,j) = 1.
Let the components K 1, …, K i and v k have already been constructed - this is the vertex with the minimum number that has not yet been included in the components. Then we place in the component K_(i+1) the vertex v k and all such vertices v j ,
that A_(G_*^*)(k,j) = 1.
We repeat step (2) until all vertices are distributed among the components.
In our example, for graph G on Fig.2 from the matrix we obtain the following matrix of the strong reachability graph
Using the procedure described above, we find that the vertices of the graph G are divided into 4 components of strong connectivity: K 1 = (v 1, v 2, v 3), \ K 2 =( v 4), \ K 3 =( v 5), \ K 4 =( v 6 ). On the set of strongly connected components we also define the reachability relation.
Definition 9.11. Let K and K" be the strongly connected components of the graph G. Component K reachable from components K^\prime if K= K" or there are two vertices u K and v K" such that u is reachable from v. K strictly achievable from K^\prime if K K" and K is reachable from K". The component K is called minimum, 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 u K and v K."
The following characteristic of strict reachability is easily deduced from the definition.
Lemma 9.3. The strict reachability relation is a partial order relation, i.e. it is anti-reflexive, anti-symmetric and transitive.
This relation can be represented as a directed graph whose vertices are the components, and the edge (K", K) means that K is strictly reachable from K". On rice. 9.4 this component graph is shown for the graph G considered above.
Rice. 9.4.
In this case, there is one minimal component K 2 .
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 9.12. Let G=(V,E) be a directed graph. A subset of vertices W V is called generating, if any vertex of the graph can be reached from the vertices of W. A subset of vertices W V 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 9.1. Let G=(V,E) be a directed graph. A subset of vertices W V is a base of G if and only if it contains one vertex from each minimal strongly connected component of G 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 W 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. Therefore W is a base.
Conversely, if W 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. W cannot contain any other vertices, since each of them is reachable from already included vertices.
From this theorem follows the following procedure for constructing one or enumerating all bases of a graph G.
Find all strongly connected components of G.
Determine the order on them and select the minimal components relative to this order.
Generate one or all bases of a graph by selecting one vertex from each minimal component.
Example 9.5. Let us define all the bases of the directed graph G shown in Fig.9.5.
Rice. 9.5. Graph G
At the first stage, we find the strongly connected components of G:
At the second stage, we construct a strict reachability graph on these components.
Rice. 9.6. Graph of reachability relations on components of G
We define the minimum components: K 2 = ( b ), K 4 = ( d, e, f, g) and K 7 = ( r).
Finally we list all four bases of G: B 1 = ( b, d, r), B 2 = ( b, e, r), B 3 = ( b, f, r) and B 1 = ( b, g, r) .
Tasks
Problem 9.1. Prove that the sum of the degrees of all vertices of an arbitrary directed graph is even.
This problem has a popular interpretation: prove that total number There is always an even number of handshakes exchanged between people who come to the party.
Problem 9.2. List all non-isomorphic undirected graphs that have at most four vertices.
Problem 9.3. Prove that an undirected connected graph remains connected after removing some edge ↔ this edge belongs to some cycle.
Problem 9.4. Prove that an undirected connected graph with n vertices
contains at least n-1 edges,
if it contains more than n-1 edges, then it has at least one cycle.
Problem 9.5. Prove that in any group of 6 people there are three pairs of acquaintances or three pairs of strangers.
Problem 9.6. Prove that the undirected graph G=(V,E) is connected ↔ for each partition V= V 1 V 2 with non-empty V 1 and V 2 there is an edge connecting V 1 to V 2 .
Problem 9.7. Prove that if an undirected graph has exactly two vertices of odd degree, then they are connected by a path.
Problem 9.8. Let G=(V,E) be an undirected graph with |E|< |V|-1. Докажите, что тогда G несвязный граф.
Problem 9.9. Prove that in a connected undirected graph any two simple ways of maximum length have a common vertex.
Problem 9.10. Let an undirected graph without loops G=(V,E) have k connected components. Prove that then
Problem 9.11. Determine what the reachability graph is for
a graph with n vertices and an empty set of edges;
graph with n vertices: V= (v 1 ,… , v n ), the edges of which form a cycle:
Problem 9.12. Compute reachability graph matrix for graph
and construct a corresponding reachability graph. Find all bases of graph G.
Problem 9.13. Build for given on rice. 9.7 directed graph G 1 =(V,E) its adjacency matrix A G1, incidence matrix B G1 and adjacency lists. Calculate the reachability matrix A G1* and construct the corresponding reachability graph G1*.
Rice. 9.7.
Undirected and directed trees
Trees are one of the most interesting classes of graphs used to represent various types of hierarchical structures.
Definition 10.1. An undirected graph is called a tree if it is connected and has no cycles.
Definition 10.2. A directed graph G=(V,E) is called a (directed) tree if
On rice. 10.1 examples of an undirected tree G 1 and a directed tree G 2 are shown. Note that the tree G 2 is derived from G 1 by choosing vertex c as the root and orienting all edges in the direction away from the root.
Rice. 10.1. Undirected and directed trees
This is no coincidence. Prove on your own the following statement about the relationship between undirected and directed trees.
Lemma 10.1. If in any undirected tree G=(V,E) we select an arbitrary vertex v V as the root and orient all edges in the direction “from the root”, i.e. make v the beginning of all edges incident to it, the vertices adjacent to v the beginnings of all not yet oriented edges incident to it, etc., then the resulting directed graph G" will be a directed tree.
Undirected and directed trees have many equivalent characteristics.
Theorem 10.1. Let G=(V,E) be an undirected graph. Then the following conditions are equivalent.
G is a tree.
For any two vertices in G there is a unique path connecting them.
G is connected, but when any edge is removed from E it ceases to be connected.
G is connected and |E| = |V| -1.
G is acyclic and |E| = |V| -1.
G is acyclic, but adding any edge to E generates a cycle.
Proof(1) (2): If some two vertices in G were connected by two paths, then obviously G would have a cycle. But this contradicts the definition of a tree in (1).
(2) (3): If G is connected, but when some edge (u,v) is removed, E does not lose connectivity, then between u and v there is a path that does not contain this edge. But then there are at least two paths in G connecting u and v, which contradicts condition (2).
(3) (4): Provided to the reader (see Problem 9.4).
(4) (5): If G contains a cycle and is connected, then when removing any edge from the cycle, the connectedness should not be broken, but the edges will remain |E|= V -2, and according to Problem 9.4(a) there should be at least V -1 ribs. The resulting contradiction shows that there are no cycles in G and condition (5) is satisfied.
(5) (6): Suppose that adding an edge (u,v) to E did not result in a cycle. Then the vertices u and v in G are in different connected components. Since |E|= V -1, then in one of these components, let it be (V 1 ,E 1), the number of edges and the number of vertices coincide: |E 1 |=|V 1 |. But then it has a cycle (see Problem 9.4 (b)), which contradicts the acyclicity of G.
(6) (1): If G were not connected, then there would be two vertices u and v from different connected components. Then adding an edge (u,v) to E would not lead to the appearance of a cycle, which contradicts (6). Therefore, G is connected and is a tree.
For directed trees it is often convenient to use the following inductive definition.
Definition 10.3. Let us define by induction a class of directed graphs called trees. At the same time, for each of them we define a selected vertex - the root.
Rice. 10.2 illustrates this definition.
Rice. 10.2. Inductive determination of oriented trees
Theorem 10.2. The definitions of directed trees 10.2 and 10.3 are equivalent.
Proof Let the graph G=(V,E) satisfy the conditions of Definition 10.2. Let us show by induction on the number of vertices |V| that .
If |V|=1, then the only vertex v V is, by property (1), the root of the tree, i.e. there are no edges in this graph: E = . Then .
Suppose that every graph with n vertices that satisfies Definition 10.2 is included in . Let the graph G=(V,E) with the (n+1)th vertex satisfy the conditions of Definition 10.2. By condition (1) it has a vertex-root r 0 . Let k edges emerge from r 0 and they lead to the vertices r 1 , ... , r k (k 1). Let us denote by G i ,(i=1, …, k) a graph that includes vertices V i =( v V|v \textit( reachable from )r i ) and edges E i E connecting them. It is easy to understand that G i satisfies the conditions conditions of definition 10.2. Indeed, r i does not include edges, i.e. this vertex is the root of G i. Each of the remaining vertices from V i contains one edge, as in G. If v V i , then it is reachable from the root r i by the definition of the graph G i . Since |V i | n, then by inductive hypothesis . Then the graph G is obtained according to the inductive rule (2) of Definition 10.3 from the trees G 1, ..., G k and therefore belongs to the class.
⇐ If some graph G=(V,E) is included in the class , then the fulfillment of conditions (1)-(3) of Definition 10.2 for it can be easily established by induction using Definition 10.2. We leave this to the reader as an exercise.
There is a wealth of terminology associated with oriented trees, coming from two sources: botany and the field of family relations.
The root is the only vertex that has no edges, the leaves are the only vertices that have no edges. The path from the root to the leaf is called a branch of the tree. The height of a tree is the maximum length of its branches. The depth of a vertex is the length of the path from the root to that vertex. For a vertex v V, a subgraph of the tree T=(V,E), including all vertices reachable from v and edges from E connecting them, forms a subtree T v of the tree T with root v (see Problem 10.3). The height of a vertex v is the height of the tree T v . A graph that is a union of several disjoint trees is called a forest.
If an edge leads from vertex v to vertex w, then v is called father w, and w - son v (lately, an asexual pair of terms has been used in English-language literature: parent - child). From the definition of a tree it immediately follows that each vertex, in addition to the root, has a single father. If a path leads from a vertex v to a vertex w, then v is called the ancestor of w, and w is called the descendant of v. Vertices that have a common father are called brothers or sisters.
Let us highlight another class of graphs that generalizes oriented trees - oriented acyclic ones. Two types of such labeled graphs will be used later to represent Boolean functions. These graphs can have several roots - vertices that do not include edges, and each vertex can contain several edges, rather than just one, like trees.
computer technologies, in particular program ... 2009 of the year Primary School is an experimental site By introduction of the Federal state ...
M MEDIA MONITORING Modernization of vocational education March - August 2011
SummaryUnited state exams " By choice": informational computertechnologies, biology and literature. By the way, in this year Unified State Exam... question"About the results of implementation programs development of national research universities in 2009 -2010 years". ...
STRATEGIC DEVELOPMENT PROGRAM Tver 2011
ProgramIN 2009 year. Structural changes observed in 2010 yearBy towards 2009 , ... Professionally – oriented foreign language", "Modern educational technologies". In each program advanced training module is being implemented “ State ...
1. Reachability and counter-attainability
There are quite a lot of problems in which the concept of reachability is used. Here is one of the nicknames. 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, the question can be raised whether information from one person x can be transferred to another person x 7, i.e. Is there a path going from vertex x to vertex X/. If such a path exists, then the vertex x is said to be reachable from the vertex x. One can be interested in the reachability of a vertex x from a vertex x 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.
Reachability in the graph is described by the reachability matrix R = ||r,y||, i,j =1,2,... P, Where P is the number of vertices of the graph, and each element is defined as follows:
Gu- 1 if vertex X, reachable from x,
Gu= 0 otherwise.
The set of vertices R(x,) of the graph G that are reachable from a given vertex x„ consists of the following elements x; , for which the (/, /)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 direct mapping of the 1st order Г +1 (x,) is the set of such vertices Xj, which are reachable from x using paths of length 1, then the set Г(Г(x,)) = Г X,) consists of vertices reachable from x using paths of length 2. Similar to G p(x,) is the set of vertices that are reachable from x using paths of length R.
Since any vertex in the graph that is reachable from x„ must be reachable using a path (or paths) of length 0 or 1 or 2,..., or R, then the set of vertices reachable for vertex x„ can be represented in the form
As we see, the set of reachable vertices R(x,) represents the direct transitive closure of the vertex x„, i.e. R(x,) = T(x,). Consequently, to construct the reachability matrix, we find reachable sets R(x,) for all vertices x, e X. Assuming g y - 1 if x 7 e R(x,) and gu- 0 otherwise. For the graph shown in Fig. 59.4, A, the reachability sets are found as follows: 
Rice. 59.4.
The adjacency (A), reachability (R), counter-reachability (Q) matrices have the following form:
Counter-reachability matrix Q = qij,i,j= 1,2,... P, Where P- the number of vertices of the graph, determined as follows:
qij= 1, if from vertex xy it is possible to reach the vertex x h qtj = Otherwise.
Counterreachable set Q(x,) is the set of vertices such that from any vertex of this set one can get to the vertex X/. Similar to constructing the reachable set R(x,), we can write an expression for Q(x,):
Thus, it is clear that Q(x,) is nothing more than the inverse transitive closure of the vertex x, i.e. Q(x() = T"(x,). From the definitions it is clear that the column X, matrix Q (in which q t j = 1 if xyQ(x,), and s/u=0 otherwise) coincides with the row x of the matrix R, i.e. Q = R, where R is the matrix transposed to the reachability matrix R.
The counter-reachability matrix is shown earlier.
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 computer processing, since in computational terms the main operations are high-speed logical operations.
2. Finding the set of vertices included in a path If you need to find out about the graph vertices included in these paths, then you should remember the definitions of direct and reverse transitive closures. Since T + (x,) is the set of vertices to which there are paths from the vertex x„ and T"(Y) is the set of vertices from which there are paths to x /, then T (x,) n T (xj)- a set of vertices, each of which belongs to at least one path going from x to xy. These vertices are called essential, or integral with respect to the two end vertices X, and hu. All other vertices of the graph are called unimportant, or redundant, since their removal does not affect the paths from x/ to xy.
So, for the graph in Fig. 59.5, finding the vertices included in the path, for example, from vertex X2 to vertex X4, comes down to finding T + (xg) = (xg, x3, X4, X5, Xb), T "(x4) = (xi, X2, X3 , X4, X5), and their intersections T + (xr) n T(x4) = = (X2, X3, X4, X 5).
