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
![](https://upload.wikimedia.org/wikipedia/commons/thumb/a/ab/Adjazenzgraph.svg/220px-Adjazenzgraph.svg.png)
Let be a matrix with real entries. Then the adjacency graph with no edge weights of is defined as
- The knot set
- The set of edges . Here is exactly if is different from 0
If you want to create a weighted adjacency graph, the edge receives the weight if it is different from 0.
This definition corresponds to the interpretation of the matrix as an adjacency matrix and the reconstruction of the graph from this.
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 .
- The adjacency graph is loop-free if and only if all diagonal entries are equal to 0.
- The adjacency graph is strongly connected if and only if the matrix is irreducible.
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 .