AdjacencyMatrix

AdjacencyMatrix[g]

gives the vertexvertex adjacency matrix of the graph g.

AdjacencyMatrix[{vw,}]

uses rules vw to specify the graph g.

Details

  • An adjacency matrix is also known as a connectivity matrix.
  • AdjacencyMatrix returns a SparseArray object, which can be converted to an ordinary matrix using Normal.
  • An entry aij of the adjacency matrix is the number of directed edges from vertex νi to vertex νj.
  • The diagonal entries aii count the number of loops for vertex vi.
  • An undirected edge is interpreted as two directed edges with opposite directions.
  • The vertices vi are assumed to be in the order given by VertexList[g].
  • The adjacency matrix for a graph will have dimensions ×, where is the number of vertices.

Background & Context

  • AdjacencyMatrix returns a square matrix whose rows and columns correspond to the vertices of a graph and whose elements aij are non-negative integers that give the numbers of (directed) edges from vertex vi to vertex vj. An adjacency matrix provides a useful representation of a graph that can be used to compute many properties by means of simple operations on matrices. Examples of computations on graphs that can be performed efficiently given an adjacency matrix include vertex degrees, in- and out-degrees, counts of paths between vertices in at most steps, graph spectrum, and many others.
  • For a graph on vertices, the adjacency matrix has dimensions ×. For an undirected graph, the adjacency matrix is symmetric. For a finite simple graph (i.e. an undirected, unweighted graph with no self-loops or multiple edges), the adjacency matrix must have 0s on the diagonal, and its matrix elements are given by if is adjacent to and otherwise.
  • An explicit adjacency matrix representation of a graph based on a particular ordering of vertices is unique. However, since the vertices of a graph may be permuted, there is a class of adjacency matrices that represents the corresponding isomorphism class of graphs. Nonetheless, the adjacency matrix for an isomorphism class is unique modulo permutation of rows and columns of the matrix (corresponding precisely to relabeling of the graph vertices).
  • AdjacencyGraph can be used to construct a graph from an adjacency matrix. IncidenceMatrix gives another matrix representation of a graph that gives vertex-edge relationships instead of vertex-vertex relationships. AdjacencyMatrix does not take graph weights into account, so WeightedAdjacencyMatrix must be used when computing the adjacency matrix of a graph having edge weights.

Examples

open allclose all

Basic Examples  (2)

The adjacency matrix of an undirected graph:

The adjacency matrix of a directed graph:

Scope  (5)

The adjacency matrix of an undirected graph is symmetric:

The adjacency matrix of a directed graph can be unsymmetric:

Use rules to specify the graph:

The adjacency matrix of the graph with self-loops has diagonal entries:

AdjacencyMatrix works with large graphs:

Use MatrixPlot to visualize the matrix:

Applications  (7)

Compute the degree for an undirected graph from its adjacency matrix:

Compute the in-degree for a directed graph from its adjacency matrix:

Compute the out-degree for a directed graph from its adjacency matrix:

Count the number of paths between all vertices in exactly steps for a directed graph:

There are two paths from 1 to 5 in two steps:

Count the number of paths from to in exactly steps for a directed graph:

Compute the co-citation matrix, where the co-citation for two vertices is the number of common ancestors:

The co-citation between and :

Compute the coupling matrix, where the coupling between two vertices is the number of common descendants:

The coupling between and :

Properties & Relations  (14)

Rows and columns of the adjacency matrix follow the order given by VertexList:

Use VertexIndex to find the matrix row and column corresponding to a pair of vertices:

Check whether 1 and 4 are adjacent vertices:

Compare with EdgeQ:

An undirected graph has a symmetric adjacency matrix:

Use AdjacencyGraph to construct a graph from an adjacency matrix:

The main diagonal of the adjacency matrix for any graph without loops has all zero entries:

The number of rows or columns of the adjacency matrix is equal to the number of vertices:

Isomorphic graphs can have different adjacency matrices:

Permute the adjacency matrix of g according to the mapping that gets an equal matrix of h:

A d-regular graph g is connected if the multiplicity of its d eigenvalue is 1:

The graph is 3-regular:

The multiplicity 3 is 1, so it is connected:

For a complete graph, all entries outside the diagonal are 1s in the adjacency matrix:

A complete -partite graph has zero diagonal block entries:

A TuranGraph is bipartite:

A StarGraph has 1s in the first column and first row only:

For a path, rows of an adjacency matrix will contain one or two elements:

The adjacency matrix of a line graph can be computed by its IncidenceMatrix:

Possible Issues  (1)

An empty graph has no adjacency matrix:

Introduced in 2010
 (8.0)
 |
Updated in 2015
 (10.3)