Adjacency matrix

Definition

An adjacency matrix is a square matrix used to represent a finite graph, where the elements indicate whether pairs of vertices are adjacent or not in the graph. Each row and column of the matrix corresponds to a vertex, and the entries indicate the presence or absence of edges between these vertices, making it a fundamental tool in graph theory and network analysis.

5 Must Know Facts For Your Next Test

1. In an undirected graph, the adjacency matrix is symmetric, meaning that if there is an edge from vertex A to vertex B, there is also an edge from B to A.
2. For directed graphs, the adjacency matrix may not be symmetric, as an edge from vertex A to vertex B does not imply an edge from B to A.
3. The elements of an adjacency matrix can be either 0 or 1 in unweighted graphs, where 1 indicates the presence of an edge and 0 indicates its absence.
4. In weighted graphs, the adjacency matrix can have values greater than 1, representing the weight or cost associated with each edge.
5. The adjacency matrix provides a straightforward way to compute properties of the graph, such as finding connected components or determining if a path exists between vertices using matrix operations.

Review Questions

• How does the structure of an adjacency matrix reflect the properties of undirected versus directed graphs?
  • An adjacency matrix for an undirected graph is symmetric because edges connect vertices without direction; thus, if there's an edge from vertex A to B, there's also one from B to A. In contrast, a directed graph's adjacency matrix is not necessarily symmetric since an edge from A to B does not imply one exists from B to A. This difference in structure helps in analyzing the connectivity and flow within each type of graph.
• Discuss how an adjacency matrix can be utilized to determine the degree of vertices in a graph.
  • To determine the degree of vertices using an adjacency matrix, you can sum the entries in each row for undirected graphs. The resulting sum represents the number of edges connected to that vertex, reflecting its degree. In directed graphs, separate calculations are needed for in-degrees and out-degrees; in-degrees are found by summing columns while out-degrees are calculated by summing rows.
• Evaluate the advantages and disadvantages of using an adjacency matrix versus an adjacency list for representing large sparse graphs.
  • Using an adjacency matrix for large sparse graphs has both pros and cons. On one hand, it provides efficient access to check if an edge exists between any two vertices since it's simply looking up a value in a two-dimensional array. On the other hand, it requires O(n^2) space regardless of how many edges there are, which can be inefficient for sparse graphs with many more vertices than edges. An adjacency list is more space-efficient for sparse graphs as it only stores actual edges but may take longer for edge existence checks.

Related terms

Graph: A collection of vertices (or nodes) connected by edges, used to model pairwise relationships between objects.

Degree: The degree of a vertex in a graph is the number of edges connected to it, indicating its connectivity.

Graph Laplacian: A matrix representation that combines the degree of vertices with the adjacency matrix, useful for various analyses in spectral graph theory.