You get a bonus - 1 coin for daily activity. Now you have 1 coin

Reachability matrix

Lecture



Attainability matrix of a simple oriented graph Reachability matrix - binary closure matrix for relation transitivity Reachability matrix (it is given by the adjacency matrix of the graph). Thus, information about the existence of paths between vertices of a digraph is stored in the reachability matrix.

Ways to build a reachability matrix

Matrix Multiplication

Let a simple graph be given Reachability matrix whose adjacency matrix is Reachability matrix where Reachability matrix . The adjacency matrix provides information on all paths of length 1 (that is, the edges) in an ograph. To search for paths of length 2 you can find the composition of the relationship Reachability matrix With myself:

Reachability matrix .

By definition, a relationship composition matrix Reachability matrix there is Reachability matrix where Reachability matrix - conjunction, and Reachability matrix - disjunction.

After finding the matrices Reachability matrix compositions Reachability matrix for all Reachability matrix , Reachability matrix information on all paths of length from Reachability matrix before Reachability matrix . So the matrix Reachability matrix there is a desired reachability matrix.

The case of several ways

If boolean operations Reachability matrix disjunctions and conjunctions replaced by ordinary algebraic operations Reachability matrix addition and multiplication respectively, finding the reachability matrix Reachability matrix reduced to the usual step-by-step multiplication of matrices with the subsequent addition of the results of each step. Then the resulting matrix Reachability matrix will consist not only of 0 and 1 and will characterize not only the presence of paths between the vertices, but already the number of such paths. In this case, you can allow the presence of multiple edges in the graph.

Example

Reachability matrix
Graph Reachability matrix

Consider a simple connected oriented graph Reachability matrix . It has an adjacency matrix. Reachability matrix view:

Reachability matrix

Find the boolean powers of this matrix. Reachability matrix , Reachability matrix , Reachability matrix :

Reachability matrix , Reachability matrix , Reachability matrix .

Get the reachability matrix

Reachability matrix

So from the top Reachability matrix You can get to any other.

When using algebraic operations, we get the matrix

Reachability matrix

It shows the number of paths of length from 1 to 4 between the vertices of the digraph.

Warschel Algorithm

There is another algorithm for finding the reachability matrix exactly in Reachability matrix Steps - Worshel's algorithm.

Related Concepts

Strong Connected Matrix

A strong connected matrix of a simple digraph is a binary matrix containing information about all strongly connected vertices in a digraph. The strong connected matrix is ​​symmetric. For a strongly connected graph, such a matrix is ​​filled with units.

Constructing a strong connectivity matrix

A strong connectivity matrix can be constructed from a reachability matrix. Let be Reachability matrix - matrix of reachability of the digraph Reachability matrix . Then the strong connectivity matrix Reachability matrix consists of elements Reachability matrix .

Example

Consider the same graph as before.

Its reachability matrix is:

Reachability matrix

From it we get a strong connected matrix:

Reachability matrix

Vertices 3 and 4 are strongly connected with each other and with themselves.

Count Connectivity Matrix

For a connected graph, there is a notion of a connection matrix , similar to the reachability matrix.


Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Discrete Math. Set theory. Graph theory. Combinatorics.

Terms: Discrete Math. Set theory. Graph theory. Combinatorics.