adiacentiematrix

Adiacentiematrix is a term used in graph theory to refer to what is commonly called the adjacency matrix of a graph. It is a square matrix that encodes the connections between the vertices of a graph with n vertices.

In a simple, unweighted, undirected graph, the adjacency matrix A is an n×n matrix where A[i][j] equals 1 if there is an edge between vertex i and vertex j, and 0 otherwise. For directed graphs, A[i][j] indicates the presence of a directed edge from i to j. In weighted graphs, the entries A[i][j] contain the weight of the edge (or the number of parallel edges in a multigraph). Self-loops are represented by nonzero diagonal entries.

Key properties include that, for undirected graphs without loops, A is symmetric with zeros on the diagonal (unless loops are allowed). The sum of all entries in A equals twice the number of edges in an undirected graph (or the number of directed edges in a directed graph). The matrix power A^k counts walks of length k between pairs of vertices, and the trace of A^k equals the number of closed walks of length k.

The adjacency matrix is a primary tool for algebraic graph analysis. Its eigenvalues and eigenvectors form the basis of spectral graph theory, informing about connectivity, expansion, and clustering. Related matrices include the degree matrix D and the Laplacian L = D − A, used in various analyses. Normalizations of A, such as the symmetric normalized adjacency matrix D^−1/2 A D^−1/2, are used in spectral clustering and graph neural networks. In practice, adjacency matrices are dense representations for small graphs but can be very sparse for large graphs, in which case sparse representations or alternative structures (like adjacency lists) are often preferred.