Adjacency graph

An adjacency graph is a concept in graph theory that assigns a graph to each matrix . This creates a connection between linear algebra and graph theory, which allows terms and solution concepts to be transferred.

definition

The edge-weighted adjacency graph of the matrix . There is no path from node 3 to node 2, so the matrix is reducible . Since all diagonal entries are equal to 0, the graph is loop-free. ${\displaystyle A={\begin{bmatrix}0&3&0&0\\2&0&4&0\\0&0&0&1\\0&0&2&0\end{bmatrix}}}$ ${\displaystyle A}$

Let be a matrix with real entries. Then the adjacency graph with no edge weights of is defined as ${\displaystyle A\in \mathbb {R} ^{n\times n}}$ ${\displaystyle G_{A}=(V,E)}$ ${\displaystyle A}$

• The knot set ${\displaystyle V=\{1,\ldots ,n\}}$
• The set of edges . Here is exactly if is different from 0 ${\displaystyle E}$ ${\displaystyle (i,j)\in E}$ ${\displaystyle a_{i,j}}$

If you want to create a weighted adjacency graph, the edge receives the weight if it is different from 0. ${\displaystyle (i,j)}$ ${\displaystyle a_{i,j}}$

This definition corresponds to the interpretation of the matrix as an adjacency matrix and the reconstruction of the graph from this. ${\displaystyle A}$

properties

As with the adjacency matrix, some properties of the matrix are reflected in the adjacency graph:

• The adjacency graph is undirected if and only if the matrix is symmetric . ${\displaystyle A}$
• The adjacency graph is loop-free if and only if all diagonal entries are equal to 0. ${\displaystyle A}$
• The adjacency graph is strongly connected if and only if the matrix is irreducible. ${\displaystyle A}$

use

Like the adjacency matrix, the adjacency graph establishes a connection between linear algebra and graph theory and thus enables solution concepts for both topics to be combined. An example of this is the irreducibility of matrices. This is difficult to check with the means of linear algebra. If you create the adjacency graph and check it for a strong connection, this is equivalent to checking the irreducibility of the matrix. In addition, adjacency graphs can be used to illustrate Markov chains , since every transition graph is an adjacency graph of a row-stochastic matrix .

literature

• Peter Knabner , Wolf Barth : Lineare Algebra . Basics and applications (=  Springer textbook ). Springer, Berlin 2012, ISBN 978-3-642-32185-6 .