({{, (RefLink[AdjacencyMatrix, paclet:ref/AdjacencyMatrix])[g] 
gives the vertex–vertex adjacency matrix of the graph g.}, {, (RefLink[AdjacencyMatrix, paclet:ref/AdjacencyMatrix])[{v->w,…}]
uses rules v->w to specify the graph g. }})

OpenersNotesSection(Spacer1)Details

An adjacency matrix is also known as a connectivity matrix.

(RefLink[AdjacencyMatrix, paclet:ref/AdjacencyMatrix]) returns a (RefLink[SparseArray, paclet:ref/SparseArray]) object, which can be converted to an ordinary matrix using (RefLink[Normal, paclet:ref/Normal]).

An entry (Subscript[a, ij]) of the adjacency matrix is the number of directed edges from vertex (Subscript[ν, i]) to vertex (Subscript[ν, j]).

The diagonal entries (Subscript[a, ii]) count the number of loops for vertex (Subscript[v, i]).

An undirected edge is interpreted as two directed edges with opposite directions.

The vertices (Subscript[v, i]) are assumed to be in the order given by (RefLink[VertexList, paclet:ref/VertexList])[g].

The adjacency matrix for a graph will have dimensions n×n, where n is the number of vertices.

OpenersPrimaryExamplesSection(Spacer1)Examples  (29)

OpenersExampleSection0(Spacer1)Basic Examples  (2)

The adjacency matrix of an undirected graph:

Graph[{1\[UndirectedEdge]2,2\[UndirectedEdge]3,3\[UndirectedEdge]1}]

AdjacencyMatrix[%]//MatrixForm

The adjacency matrix of a directed graph:

Graph[{1\[DirectedEdge]2,2\[DirectedEdge]3,3\[DirectedEdge]1}]

AdjacencyMatrix[%]//MatrixForm

OpenersExampleSection1(Spacer1)Scope  (5)

The adjacency matrix of an undirected graph is symmetric:

Graph[{1\[UndirectedEdge]2,1\[UndirectedEdge]3,2\[UndirectedEdge]3,2\[UndirectedEdge]4,3\[UndirectedEdge]4}]

AdjacencyMatrix[%]//MatrixForm

The adjacency matrix of a directed graph can be unsymmetric:

Graph[{1\[DirectedEdge]2,2\[DirectedEdge]1,3\[DirectedEdge]1,3\[DirectedEdge]2,4\[DirectedEdge]1,4\[DirectedEdge]2}]

AdjacencyMatrix[%]//MatrixForm

Use rules to specify the graph:

AdjacencyMatrix[{1->2,2->1,3->1,3->2,4->1,4->2}]//MatrixForm

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

{Graph[{1\[UndirectedEdge]2,2\[UndirectedEdge]3,3\[UndirectedEdge]1,2\[UndirectedEdge]2}],Graph[{1\[DirectedEdge]1,1\[DirectedEdge]2,2\[DirectedEdge]3,3\[DirectedEdge]1}]}

MatrixForm/@AdjacencyMatrix/@%

(RefLink[AdjacencyMatrix, paclet:ref/AdjacencyMatrix]) works with large graphs:

Graph[Table[i\[DirectedEdge]Mod[i^2,10^3],{i,0,10^3-1}]];

Timing[m=AdjacencyMatrix[%]]

Use (RefLink[MatrixPlot, paclet:ref/MatrixPlot]) to visualize the matrix:

MatrixPlot[m]

OpenersExampleSection3(Spacer1)Applications  (7)

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

adjacencyDegree[g_?UndirectedGraphQ]:=With[{a=AdjacencyMatrix[g]},Total[a]+Diagonal[a]]

adjacencyDegree[]

VertexDegree[]

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

adjacencyInDegree[g_?DirectedGraphQ]:=Total[AdjacencyMatrix[g]]

adjacencyInDegree[]

VertexInDegree[]

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

adjacencyOutDegree[g_?DirectedGraphQ]:=Total[AdjacencyMatrix[g]\[Transpose]]

adjacencyOutDegree[]

VertexOutDegree[]

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

graphPathCountMatrix[g_?DirectedGraphQ,k_Integer?Positive]:=
MatrixPower[AdjacencyMatrix[g],k]

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

graphPathCountMatrix[,2]//MatrixForm

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

graphPathCount[g_?DirectedGraphQ,s_,t_,k_Integer?Positive]:=
MatrixPower[AdjacencyMatrix[g],k][[VertexIndex[g,s],VertexIndex[g,t]]]

graphPathCount[,1,5,2]

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

cocitationMatrix[g_?DirectedGraphQ]:= With[{a=AdjacencyMatrix[g]},a\[Transpose].a-DiagonalMatrix[Diagonal[a\[Transpose].a]]]

g=;

cocitationMatrix[g]//MatrixForm

The co-citation between (Subscript[J, 2]) and (Subscript[J, 3]):

%[[VertexIndex[g,(Subscript[J, 2])],VertexIndex[g,(Subscript[J, 3])]]]

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

couplingMatrix[g_?DirectedGraphQ]:= With[{a=AdjacencyMatrix[g]},a.a\[Transpose]-DiagonalMatrix[Diagonal[a.a\[Transpose]]]]

g=;

couplingMatrix[g]//MatrixForm

The coupling between (Subscript[P, 1]) and (Subscript[P, 4]):

%[[VertexIndex[g,(Subscript[P, 1])],VertexIndex[g,(Subscript[P, 4])]]]

OpenersExampleSection4(Spacer1)Properties & Relations  (14)

Rows and columns of the adjacency matrix follow the order given by (RefLink[VertexList, paclet:ref/VertexList]):

g=Graph[{2\[UndirectedEdge]3,3\[UndirectedEdge]1,1\[UndirectedEdge]2,1\[UndirectedEdge]4},VertexShapeFunction->"Name",VertexStyle->Blue]

VertexList[g]

TableForm[Normal@AdjacencyMatrix[g],TableHeadings->{c=Style[#,Blue]&/@%,c}]

Use (RefLink[VertexIndex, paclet:ref/VertexIndex]) to find the matrix row and column corresponding to a pair of vertices:

g=Graph[{2\[UndirectedEdge]3,3\[UndirectedEdge]1,1\[UndirectedEdge]2,1\[UndirectedEdge]4},VertexShapeFunction->"Name"]

(a=AdjacencyMatrix[g])//MatrixForm

Check whether 1 and 4 are adjacent vertices:

a[[VertexIndex[g,1],VertexIndex[g,4]]]==1

Compare with (RefLink[EdgeQ, paclet:ref/EdgeQ]):

%==EdgeQ[g,1\[UndirectedEdge]4]

An undirected graph has a symmetric adjacency matrix:

g=CompleteGraph[4]

AdjacencyMatrix[g]//MatrixForm

SymmetricMatrixQ[%]

Use (RefLink[AdjacencyGraph, paclet:ref/AdjacencyGraph]) to construct a graph from an adjacency matrix:

AdjacencyGraph[{{0,1,0},{0,0,1},{1,1,0}}]

AdjacencyMatrix[%]//Normal

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

GridGraph[{2,3}]

Diagonal[AdjacencyMatrix[%]]//Normal

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

g=CompleteGraph[5]

Dimensions[AdjacencyMatrix[g]]

VertexCount[g]

Isomorphic graphs can have different adjacency matrices:

{g,h}={PetersenGraph[4,1],HypercubeGraph[3]}

IsomorphicGraphQ[g,h]

AdjacencyMatrix[g]==AdjacencyMatrix[h]

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

perm=Values[First[FindGraphIsomorphism[g,h]]]

AdjacencyMatrix[g][[perm,perm]]==AdjacencyMatrix[h]

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

g=HypercubeGraph[3]

The graph is 3-regular:

VertexDegree[g]

The multiplicity 3 is 1, so it is connected:

Count[Eigenvalues[AdjacencyMatrix[g]],3]

ConnectedGraphQ[g]

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

AdjacencyMatrix[CompleteGraph[10]]//MatrixPlot

A complete k-partite graph has zero diagonal block entries:

AdjacencyMatrix[CompleteGraph[{2,3,4}]]//MatrixPlot

A (RefLink[TuranGraph, paclet:ref/TuranGraph]) is bipartite:

BipartiteGraphQ[g=TuranGraph[5,2]]

MatrixPlot[AdjacencyMatrix[g]]

A (RefLink[StarGraph, paclet:ref/StarGraph]) has 1s in the first column and first row only:

AdjacencyMatrix@StarGraph[10]//MatrixPlot

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

PathGraph[Range[20]]

MatrixPlot[AdjacencyMatrix[%]]

The adjacency matrix of a line graph can be computed by its (RefLink[IncidenceMatrix, paclet:ref/IncidenceMatrix]):

g=GridGraph[{2,3}]

m=IncidenceMatrix[g];

MatrixPlot/@{Transpose[m].m-2 IdentityMatrix[EdgeCount[g]],AdjacencyMatrix[LineGraph[g]]}

OpenersExampleSection5(Spacer1)Possible Issues  (1)

An empty graph has no adjacency matrix:

AdjacencyMatrix[Graph[{},{}]]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[AdjacencyGraph, paclet:ref/AdjacencyGraph])  ▪  (RefLink[WeightedAdjacencyMatrix, paclet:ref/WeightedAdjacencyMatrix])  ▪  (RefLink[IncidenceMatrix, paclet:ref/IncidenceMatrix])  ▪  (RefLink[KirchhoffMatrix, paclet:ref/KirchhoffMatrix])  ▪  (RefLink[VertexIndex, paclet:ref/VertexIndex])  ▪  (RefLink[DistanceMatrix, paclet:ref/DistanceMatrix])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Graphs and Matrices, paclet:guide/GraphsAndMatrices])}, {▪(RefLinkPlain[Graph Construction & Representation, paclet:guide/GraphConstructionAndRepresentation])}, {▪(RefLinkPlain[Graph Programming, paclet:guide/GraphProgramming])}, {▪(RefLinkPlain[Computation on Graphs, paclet:guide/ComputationOnGraphs])}})}})

({{(Spacer1), ({{(Spacer1)Related Links}, {(WebLink[DocumentationFooterIconsRelatedLinks-EIWL.png(Spacer1)An Elementary Introduction to the Wolfram Language, https://www.wolfram.com/language/elementary-introduction/21-graphs-and-networks.html])(WebLink[: Graphs and Networks, https://www.wolfram.com/language/elementary-introduction/21-graphs-and-networks.html])}})}})