Adjacency matrix
Without edge weights and
Without multiple edges
Left, with the three edges
(1,2), (2, 3) and ( 2, 4)
Which are characterized by 1
An adjacency matrix (sometimes adjacency matrix ) of a graph is a matrix that stores the graph which nodes are connected by an edge. It has one row and one column, resulting in a matrix of n nodes for each node. An entry in the i-th row and j -th column is to consider whether an edge of the i-th leading to the j-th node. If at this point a 0, no edge exists - a 1 indicates that an edge exists, as shown at right.
There are different variants, depending on the type of graph, for example, for multiple edges.
The representation of a graph as a matrix allows the use of methods of linear algebra. The application and study of such methods is a central topic in the spectral graph theory. It thus forms an interface between graph theory and linear algebra.
- 3.1 Storage of graphs in the computer
- 3.2 Spectral Graph Theory
- 3.3 Design of ranking algorithms
- 3.4 Calculate path length in graphene 3.4.1 example
- 3.5.1 example
Variants
The following definitions apply for graphs whose nodes are numbered consistently with the numbers 1 to n. Depending on whether you look at a graph with edge weights or multiple edges, the definition of the adjacency matrix is slightly different. Hypergraphs and edge- weighted graphs with multiple edges do not have representation as an adjacency matrix.
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 2- tuples, and the numbers of the start and end nodes of the edges. If it is an undirected graph is the set of edges if and only if is in the edge set. The Adjazentmatrix is therefore always symmetric for undirected graphs. In this case, it is sufficient to store only the upper half of the matrix. It is therefore necessary items shall not be stored, for which it holds true: i ≤ j.
The Adjazenzmathrix of the graph G is defined by its entries as
An example of an undirected graph without edge weights and without multiple edges can be seen in the figure above. In addition, the associated symmetric adjacency matrix. Self- edges from one node to the same node can be identified by the corresponding one on the main diagonal.
Graphs without edge weights, with multiple edges
If it is in the graph G is a multigraph without edge weights, then the set of its edges is described as a multiset of pairs of nodes.
The Adjazenzmathrix of the graph G is defined by its entries as
This refers to the number of all edges that connect the nodes and number.
Graph with edge weights, without multiple edges
With edge weights and
Without multiple edges
Graph on the left
For an edge-weighted graph with edge weight his Adjazenzmathrix is defined by their entries as
Occasionally a registered instead of in the adjacency matrix. This is useful especially if the adjacency matrix to be used for an algorithm that is based on larger / smaller operations, such as many shortest path algorithms.
Properties
With edge weights and
Without multiple edges
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 symmetric.
- Are all entries along the main diagonal of the adjacency matrix is 0, then the graph is loop-free, see picture.
- The adjacency matrix of a directed graph is irreducible if and only if the graph is strongly connected. The adjacency matrix of an undirected graph is irreducible Similarly, when the graph is connected.
- If the adjacency matrix of a directed graph and the matrix is irreducible, then the graph is weakly connected. The matrix then corresponds to lying (up to weights ) of the adjacency matrix of the directed graph underlying undirected graph
- Two adjacency matrices are equal, the graph equivalent. Equivalent graphs can but contain different adjacency matrices, because the adjacency matrix changes when the nodes are umnummieriert.
- Given the associated incidence matrix for an undirected and unweighted Be graph. Then, where is a diagonal matrix and the transpose. Is therefore for loop-free graphs.
Use
Storing graphs in the computer
Adjacency matrices can be used in the computer also for storing graphs. They are particularly easy to implement and is accessed in (see Landau symbols). However, they require memory, the number of nodes of the graph. Therefore, these graphs for storing way is rarely used in practice. However, if a graph compared to the number of nodes has few edges, the adjacency matrix can be implemented as a sparse matrix. Alternatively, to represent only neighborhood relationships, use an incidence matrix. Their size is directly dependent on the number of edges.
Spectral Graph Theory
Adjacency matrices are also used in the spectral graph theory. This involves, in particular, to draw conclusions about certain properties of the graph represented by 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 using the PageRank algorithm or the concept of hubs and Authorities. Both methods are mainly applied to the linking of home pages on the Internet (hence the adjacency matrix is in this context often called the link matrix ), but can be generally interpreted as methods for calculation of the relative importance of a node in a graph. PageRank is, for example, the adjacency matrix gradually modified, to obtain a stochastic matrix, which is also referred to as Google matrix.
Calculate path length in graphene
Is a directed graph without multiple edges and without edge weights and the corresponding adjacency matrix, as can the number of paths from node i to node j, which contain exactly k edges, determine as follows: Calculate and look at the entry in the i- th row and the j -th column. This is the number of paths from i to j, which contain exactly k edges.
The vector space spanned by the columns of the adjacency matrix, and the graph is called Adjazenzraum.
Example
Consider the following unweighted adjacency matrix:
We are looking for the number of paths from node 2 to the node 3, with path length 3 These must be calculated:
So there are 2 paths in the graph, which go from node 2 to the node 3 and contain exactly 3 edges: the first is 2-1-2-3, 2-3-4-3 second.
Determine Achievable node
To determine the nodes that are reachable from an output node in steps, one first sums up the powers of a first adjacency matrix including the unit matrix as a zero- power. Then, it replaces all elements by unequal. There is obtained a matrix indicating for each node, which nodes are accessible from out of it in most steps.
Changes this matrix is not from th on the second step, one has to determine the reachability matrix of the graph.
Example
We continue to consider the following unweighted adjacency matrix:
Calculating and replace all entries that are not 0 by 1, we obtain the matrix
Analogous procedure provides with. The matrix therefore does not change, is therefore already the reachability matrix of the graph.
Alternative to the adjacency matrix can also use a distance table for distances between points in graph. This also has a node for each row and one column, includes the distance between two nodes, regardless of whether they are connected directly or over multiple edges.