adjacentiematrix

An adjacency matrix is a way to represent a graph as a square matrix. Given a graph G with n vertices V = {v1, v2, ..., vn}, its adjacency matrix A is an n-by-n matrix where the entry Aij indicates the presence and often the weight or multiplicity of the edge from vertex vi to vertex vj. In simple, unweighted graphs, Aij is 1 if there is an edge from vi to vj and 0 otherwise; typically Aii is 0 unless loops are allowed.

Different graph types yield different matrix patterns. For undirected graphs without loops, the adjacency matrix is symmetric (Aij = Aji). For directed graphs, A need not be symmetric, reflecting the directionality of edges. In weighted graphs, Aij equals the weight of the edge from vi to vj; in multigraphs, Aij may count the number of parallel edges.

Key properties and uses. The sum of the ith row equals the degree of vertex vi in undirected graphs; in directed graphs, the ith row sum gives the out-degree of vi and the ith column sum gives the in-degree of vi. The eigenvalues and eigenvectors of the adjacency matrix are central to spectral graph theory and related analyses. Powers of A have combinatorial meaning: the entry (A^k)ij counts the number of walks of length k from vi to vj. Boolean versions of adjacency matrices are used to compute reachability and transitive closures.

Computational considerations. Storing an adjacency matrix requires O(n^2) space, which can be inefficient for large, sparse graphs. In such cases, adjacency lists or sparse matrix representations are preferred. Matrix-based operations support algorithms for counting paths, assessing connectivity, and performing various graph analyses.