gives the vertex–vertex adjacency matrix of the graph g.
uses rules vw to specify the graph g.
- 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.
Examplesopen allclose all
Basic Examples (2)
AdjacencyMatrix works with large graphs:
Use MatrixPlot to visualize the matrix:
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:
Compare with EdgeQ:
Use AdjacencyGraph to construct a graph from an adjacency matrix:
A TuranGraph is bipartite:
A StarGraph has 1s in the first column and first row only:
The adjacency matrix of a line graph can be computed by its IncidenceMatrix: