Adjacency matrix

	${\displaystyle {\begin{array}{r|c}&{\begin{matrix}1&2&3&4\end{matrix}}\\\hline {\begin{matrix}1\\2\\3\\4\end{matrix}}&{\begin{pmatrix}0&1&0&0\\1&0&1&1\\0&1&0&0\\0&1&0&0\\\end{pmatrix}}\end{array}}}$
Undirected graph without edge weights and without multiple edges	4x4 adjacency matrix to the graph left, with the 3 edges (1,2), (2, 3) and (2, 4) which are marked by 1

An adjacency matrix (sometimes also called neighborhood matrix ) of a graph is a matrix that stores which nodes of the graph are connected by an edge . It has a row and a column for each node, resulting in a matrix for n nodes . An entry in the i th row and j th column indicates whether an edge leads from the i th to the j th node. If there is a 0 at this point , there is no edge - a 1 ${\displaystyle n\times n}$ indicates that an edge exists, see figure on the right.

There are different variants depending on the type of graph, e.g. B. for multiple edges.

The representation of a graph as a matrix allows the use of methods of linear algebra . The application and investigation of such methods is a central topic in spectral graph theory . It forms an interface between graph theory and linear algebra .

variants

The following definitions apply to graphs whose nodes are numbered continuously with the numbers 1 to n . The definition of the adjacency matrix differs slightly depending on whether one is looking at a graph with edge weights or multiple edges. Hypergraphs and edge-weighted graphs with multiple edges are not represented as an adjacency matrix. ${\displaystyle G=(V,E)}$

Graphs without edge weights, without multiple edges

In a graph without edge weights and without multiple edges, the edge set is given by a set of 2- tuples , where and are the numbers of the start and end nodes of the edges. If the graph is undirected, then is in the edge set if and only if is in the edge set. The adjacency matrix is ​​therefore always symmetric for undirected graphs. In this case it is sufficient to save only the upper half of the matrix. So only the matrix elements have to be saved. ${\displaystyle (i,j)}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle (i,j)}$ ${\displaystyle (j,i)}$ ${\displaystyle a_{i,j}}$ ${\displaystyle i\leq j}$

The adjacency matrix of the graph is defined by its entries as ${\displaystyle A=[a_{ij}]}$ ${\displaystyle G}$

${\displaystyle a_{ij}={\begin{cases}1\;{\text{falls}}\;(i,j)\in E,\\0\;{\text{sonst}}.\end{cases}}}$

An example of an undirected graph with no edge weights and no multiple edges is shown in the figure above. Next to it is the corresponding, symmetrical adjacency matrix. Self-edges, from one knot to the same knot, can be recognized by the corresponding 1 on the main diagonal . ${\displaystyle n}$ ${\displaystyle n}$

Graphs without edge weights, with multiple edges

If the graph is a multigraph without edge weights, then the set of its edges is described as a multi-set of pairs of nodes. ${\displaystyle G}$ ${\displaystyle E}$

The adjacency matrix of the graph is defined by its entries as ${\displaystyle A=[a_{ij}]}$ ${\displaystyle G}$

${\displaystyle a_{ij}={\begin{cases}|K(i,j)|,\;{\text{falls}}\;(i,j)\in E,\\0\;{\text{sonst}}.\end{cases}}}$

Here refers to the number of all edges which the nodes number and connect. ${\displaystyle |K(i,j)|}$ ${\displaystyle i}$ ${\displaystyle j}$

Graphs with edge weights, without multiple edges

	${\displaystyle A={\begin{pmatrix}0&0&12&60&0\\10&0&0&0&0\\0&20&0&32&0\\0&0&0&0&0\\7&0&0&0&0\\\end{pmatrix}}}$
Directed graph with edge weights and without multiple edges	Adjacency matrix for Graph on the left

For an edge-weighted graph with edge weight , its adjacency matrix is defined by its entries as ${\displaystyle G=(V,E,c)}$ ${\displaystyle c}$ ${\displaystyle A=[a_{ij}]}$

${\displaystyle a_{ij}={\begin{cases}c_{ij}\;{\text{falls}}\;(i,j)\in E,\\0\;{\text{sonst}}.\end{cases}}}$

Occasionally, a is entered in the adjacency matrix instead of a . This is particularly useful if the adjacency matrix is ​​to be used for algorithms, for the purposes of which missing connections can be regarded as "infinitely expensive". This is the case, for example, for all shortest-path algorithms. ${\displaystyle 0}$ ${\displaystyle \infty }$

properties

	${\displaystyle A={\begin{pmatrix}0&3&0&0\\2&0&4&0\\0&0&0&1\\0&0&2&0\\\end{pmatrix}}}$
Directed graph with edge weights and without multiple edges	reducible adjacency matrix for loop-free graph on the left

Some properties of a graph can easily be determined from its adjacency matrix:

• If the graph is undirected, the adjacency matrix is symmetrical .
• If all entries along the main diagonal of the adjacency matrix are 0, the graph is free of loops, see figure.
• The adjacency matrix of a directed graph is irreducible if and only if the graph is strongly connected . Analog is the adjacency matrix of an undirected graph irreducible if the graph connected is.
• If the adjacency matrix is ​​a directed graph and the matrix is irreducible, the graph is weakly connected . The matrix then corresponds (except for weights) to the adjacency matrix of the undirected graph on which the directed graph is based ${\displaystyle A}$ ${\displaystyle A^{T}+A}$ ${\displaystyle A^{T}+A}$
• If two adjacency matrices are equal, the graphs are isomorphic. Isomorphic graphs can have different adjacency matrices because the adjacency matrix changes when the nodes are renumbered.
• For an undirected and unweighted graph, let the associated incidence matrix be given. Then where represents a diagonal matrix and the transpose . For loop-free graphs, therefore . ${\displaystyle B=(b_{i,j})}$ ${\displaystyle BB^{T}=A+\Delta }$ ${\displaystyle \Delta }$ ${\displaystyle B^{T}=(b_{j,i})}$ ${\displaystyle BB^{T}-\operatorname {diag} (BB^{T})=A}$
• The number of all spanning trees for the associated graph can be determined from the adjacency matrix with the help of the node degrees . This amounts to pieces, whereby is determined by . ${\displaystyle \det(A')}$ ${\displaystyle A'}$ ${\displaystyle \operatorname {diag} (\operatorname {deg} (v_{1}),\operatorname {deg} (v_{2}),...,\operatorname {deg} (v_{n}))-A}$

use

Storage of graphs in the computer

Adjacency matrices can also be used to store graphs in the computer. They are particularly easy to implement and can be accessed in (see Landau symbols ). However, they require memory of , where is the number of nodes in the graph. This is why this type of storage for graphs is rarely used in practice. However, if a graph has only a few edges compared to the number of nodes, the adjacency matrix can be implemented as a sparse matrix . Alternatively, an incidence matrix can also be used to show only neighborhood relationships . Their size depends directly on the number of edges. ${\displaystyle {\mathcal {O}}(1)}$ ${\displaystyle {\mathcal {O}}(n^{2})}$ ${\displaystyle n}$

Spectral graph theory

→ Main article : spectrum (graph theory)

Adjacency matrices are also used in spectral graph theory. It is particularly a matter of drawing conclusions about certain properties of the represented graph by means of the various properties of the adjacency matrix.

Construction of ranking algorithms

The adjacency matrix is ​​also used in the construction of numerous ranking algorithms such as B. the PageRank algorithm or the concept of hubs and authorities . Both methods are mainly used to link homepages on the Internet (which is why the adjacency matrix is ​​often called the link matrix in this context ), but can also be interpreted more generally as methods for calculating the relative importance of a node in a graph. With PageRank z. B. the adjacency matrix modified step by step in order to obtain a stochastic matrix , which is also called Google matrix .

Calculate path length in graph

If a directed graph without multiple edges and without edge weights and the associated adjacency matrix, then the number of paths from node to node , which contain exactly edges, can be determined as follows: calculate and consider the entry in the -th row and -th column. This is the number of paths from to which exactly contain edges. ${\displaystyle G=(V,E)}$ ${\displaystyle A}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle k}$ ${\displaystyle A^{k}}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle k}$

The vector space , which is spanned by the columns of the adjacency matrix, is also called the adjacency space of the graph.

example

Consider the following unweighted adjacency matrix:

${\displaystyle A={\begin{pmatrix}0&1&0&0\\1&0&1&0\\0&0&0&1\\0&0&1&0\end{pmatrix}}}$

The number of paths from node 2 to node 3 is sought, with path length 3. For this purpose, the following must be calculated: ${\displaystyle A^{3}}$

${\displaystyle A^{2}={\begin{pmatrix}1&0&1&0\\0&1&0&1\\0&0&1&0\\0&0&0&1\end{pmatrix}}}$ ${\displaystyle A^{3}={\begin{pmatrix}0&1&0&1\\1&0&2&0\\0&0&0&1\\0&0&1&0\end{pmatrix}}}$

So there are two paths in the graph, which go from node 2 to node 3 and contain exactly 3 edges: The first is 2-1-2-3, the second 2-3-4-3.

Determine accessible nodes

To find the nodes of an output node in are achievable steps, firstly sums the first potencies an adjacency matrix including the identity matrix as a zero power. Then you replace all elements unequal with . This gives a matrix that indicates for each node which nodes can be reached from it in at most steps. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle n}$

If this matrix does not change from the -th to the -th step, then the reachability matrix of the graph has been determined. ${\displaystyle n}$ ${\displaystyle (n+1)}$

example

The following unweighted adjacency matrix is ​​also considered:

${\displaystyle A={\begin{pmatrix}0&1&0&0\\1&0&1&0\\0&0&0&1\\0&0&1&0\end{pmatrix}}}$

If you calculate and replace all entries that are not 0 by 1, the result is the matrix ${\displaystyle \sum _{n=0}^{4}A^{n}}$

${\displaystyle K_{4}={\begin{pmatrix}1&1&1&1\\1&1&1&1\\0&0&1&1\\0&0&1&1\end{pmatrix}}}$

Analogous procedure with supplies . The matrix no longer changes and is therefore already the reachability matrix of the graph. ${\displaystyle \sum _{n=0}^{5}A^{n}}$ ${\displaystyle K_{4}=K_{5}}$ ${\displaystyle K_{4}}$

Alternatively, the adjacency matrix also can be used for distances between points in the graph distance table use. This also has a row and a column for each node, but contains the distance between 2 nodes, regardless of whether they are connected directly or via several edges.

literature

• Reinhard Diestel: graph theory . 4th edition. Springer, Berlin a. a. 2010, ISBN 978-3-642-14911-5 .
• Peter Knabner , Wolf Barth : Lineare Algebra. Basics and applications (=  Springer textbook ). Springer Spectrum, Berlin and others 2013, ISBN 978-3-642-32185-6 .
• Volker Turau: Algorithmic Graph Theory . 3rd, revised edition. Oldenbourg, Munich 2009, ISBN 978-3-486-59057-9 .

Individual evidence

1. ^ ^{A b c} Gerald Teschl , Susanne Teschl : Mathematics for computer scientists. Volume 1: Discrete Mathematics and Linear Algebra. Corrected reprint. Springer, Berlin a. a. 2006, ISBN 3-540-25782-9 , pp. 387-389.
2. ↑ Peter Pepper: Programming with Java. A basic introduction for computer scientists and engineers . Springer, Berlin a. a. 2005, ISBN 3-540-20957-3 , pp. 304 .
3. ^ Sven Oliver Krumke, Hartmut Noltemeier: Graph Theoretical Concepts and Algorithms . Vieweg + Teubner, Wiesbaden 2009, ISBN 978-3-8348-0629-1 , pp. 18-19 .
4. ↑ Dieter Jungnickel: Graphs, Networks and Algorithms 1989, p. 84.