Knowra Adjacency matrix Adjacency matrix An adjacency matrix is a square matrix whose entries encode whether pairs of graph vertices are joined by edges, and may also record edge weights or multiplicities.
Adjacency matrix of a directed graph : A matrix representation of a directed graph in which entry (i, j) records an edge from vertex i to vertex j. Direction determines whether an edge appears at (i, j), (j, i), or both.
Walk (graph theory) : A sequence of vertices in which consecutive vertices are connected by edges; vertices and edges may repeat. Adjacency-matrix powers count walks between each pair of vertices.
Graph (discrete mathematics) : A structure consisting of vertices and edges that represent relationships between pairs of objects. An adjacency matrix is one representation of this broader structure.
Adjacency list : A graph representation that stores, for each vertex, a list of its neighboring vertices. It avoids allocating entries for nonedges, unlike a full adjacency matrix.
Weighted adjacency matrix : A graph’s square matrix representation with edge weights stored in entries instead of simple presence indicators. Replacing binary entries with weights preserves connection strength or cost.
Transitive closure : The relation containing every ordered pair connected by a path in a directed graph or relation. Boolean matrix operations can derive reachability from adjacency information.
Vertex (graph theory) : An entity in a graph that may be connected to other entities by edges. Each vertex corresponds to one row and one column of the matrix.
Edge list : A graph representation consisting of a collection of its edges, usually as endpoint pairs. It records only existing edges rather than all possible vertex pairs.
Graph Laplacian : A matrix formed from a graph’s degree matrix and adjacency matrix, encoding connectivity and diffusion structure. Subtracting adjacency from degree information turns links into a matrix for graph structure.
PageRank : An algorithm that ranks nodes by the stationary probabilities of a random walk on a directed network. A normalized adjacency matrix defines the transitions used by the random walk.
Show all 21