Historical Context & Motivation
The formal study of networks as mathematical objects has roots stretching back to the eighteenth century, when Leonhard Euler posed a deceptively simple question about walking across the bridges of Königsberg. His 1736 paper showed that the physical layout of the bridges was irrelevant; what mattered was which landmasses were connected to which. That insight—stripping away geometry to focus on connections—gave birth to graph theory, the mathematical backbone of modern network science. Today, graph-based representations underpin algorithms in social-network analysis, logistics, epidemiology, computer networking, and operations research, making them indispensable tools in finite mathematics.
Despite centuries of development, the core question remains the same: How do we represent a real-world network in a precise, computable form so that we can analyze its structure and draw conclusions? This lesson addresses that question by introducing graph models, adjacency matrices, and adjacency lists—the standard representations that bridge intuitive network diagrams and rigorous mathematical analysis.
Core Principles & Definitions
A graph is an ordered pair G = (V, E), where V is a finite set of vertices (also called nodes) and E is a set of edges (also called links or arcs) that express pairwise relationships among elements of V. Edges may be undirected, meaning the relationship is symmetric—like a two-way street—or directed, meaning one vertex points to another—like a one-way street. The following foundational ideas form the scaffolding upon which all network analysis rests.
Vertex (Node)
Edge (Link)
Adjacency
Degree
Weighted vs. Unweighted
Visual Explanation — Graph Diagram
The diagram below illustrates an undirected graph with five vertices (labeled A through E) and seven edges. Each vertex is drawn as a colored circle, and each edge is rendered as a line segment between two vertices. Notice that vertex C has the highest degree (four edges), while vertex E has the lowest degree (two edges). The spatial positions of the vertices are arbitrary—what matters is which pairs are connected.
Several structural features are visible at a glance. Vertices A, B, and C form a triangle (a 3-cycle), and every vertex is reachable from every other vertex through some sequence of edges, making the graph connected. These observations—cycles, connectivity, vertex degrees—are precisely the kinds of questions that adjacency representations let us answer computationally.
Mathematical Framework — Adjacency Matrices & Lists
While a node-and-link diagram conveys intuition, algorithms require a data structure. The two most common representations are the adjacency matrix and the adjacency list. Each encodes the same connectivity information but optimizes for different computational tasks.
The Adjacency Matrix
The Adjacency List
An adjacency list associates each vertex vᵢ with the set of its neighbors, Adj(vᵢ). For the graph in Figure 1: Adj(A) = {B, D, C}, Adj(B) = {A, C, E}, Adj(C) = {A, B, D, E}, Adj(D) = {A, C}, and Adj(E) = {B, C}. The list representation uses Θ(|V| + |E|) space rather than the Θ(|V|²) required by a full matrix, making it preferable for sparse graphs—graphs where |E| is much smaller than |V|². Conversely, the adjacency matrix supports constant-time edge queries (simply check aᵢⱼ) and matrix operations that reveal deeper structural properties such as walk counts and spectral information.
Directed and Weighted Graph Representations
Many real-world networks are inherently asymmetric or carry quantitative information along their edges. A directed graph (digraph) replaces unordered edge sets {u, v} with ordered pairs (u, v), indicating that the relationship flows from u to v. The adjacency matrix of a digraph is generally asymmetric: aᵢⱼ may differ from aⱼᵢ. In a weighted graph, each edge carries a numerical weight representing cost, capacity, distance, or probability, and the adjacency matrix stores those weights instead of ones. The diagram below shows a small directed, weighted network alongside its adjacency matrix.
| Feature | Undirected Graph | Directed Graph |
|---|---|---|
| Edge notation | {u, v} (unordered pair) | (u, v) (ordered pair) |
| Adjacency matrix symmetry | Symmetric (aᵢⱼ = aⱼᵢ) | Generally asymmetric |
| Degree definition | Single degree = row sum | In-degree (col sum) and out-degree (row sum) |
| Max edges (simple) | n(n − 1) / 2 | n(n − 1) |
Worked Example — Building and Analyzing an Adjacency Matrix
Consider an undirected network of four cities—Atlanta (A), Boston (B), Chicago (C), and Denver (D)—with direct flights between A–B, A–C, B–C, and C–D. We wish to construct the adjacency matrix, read off the vertex degrees, and determine the number of walks of length 2 from A to D.
Strengths & Limitations of Representation Methods
Choosing between an adjacency matrix and an adjacency list is not merely a matter of preference; it is a design decision that affects both memory consumption and algorithmic efficiency. The table below summarizes the key trade-offs for a graph with n vertices and m edges.
| Operation / Metric | Adjacency Matrix | Adjacency List |
|---|---|---|
| Space complexity | Θ(n²) | Θ(n + m) |
| Check if edge exists | O(1) — direct index lookup | O(deg(v)) — scan neighbor list |
| Enumerate neighbors of v | O(n) — scan entire row | O(deg(v)) — traverse list |
| Add an edge | O(1) | O(1) amortized |
| Matrix operations (Aᵏ, eigenvalues) | Natural — standard linear algebra | Requires conversion to matrix first |
| Best suited for | Dense graphs, spectral analysis | Sparse graphs, traversal algorithms |
Connection to Advanced Theory
The adjacency matrix is far more than a bookkeeping device. Its algebraic properties open doors to spectral graph theory, random walks, network centrality measures, and algebraic connectivity. The table below previews how the foundational concepts introduced in this lesson connect to more advanced topics you may encounter in graph theory, linear algebra, or data science courses.
| This Lesson | Advanced Extension |
|---|---|
| Adjacency matrix A | Laplacian matrix L = D − A, used to analyze connectivity and clustering |
| Walk counts via Aᵏ | Eigenvalue decomposition: Aᵏ = PΛᵏP⁻¹ enables efficient computation of large powers |
| Vertex degree | Degree centrality, betweenness centrality, and PageRank in network analysis |
| Weighted edges | Shortest-path algorithms (Dijkstra, Floyd–Warshall) and minimum spanning trees |
| Sparse vs. dense classification | Sparse matrix storage formats (CSR, CSC) in computational science |
One particularly elegant result is the connection between the eigenvalues of A and the structure of G. The largest eigenvalue λ₁ of the adjacency matrix satisfies δ ≤ λ₁ ≤ Δ, where δ and Δ are the minimum and maximum vertex degrees, respectively. Spectral methods exploit these eigenvalues to detect communities, estimate graph expansion, and even determine whether two graphs are isomorphic (under certain conditions). Thus, mastering adjacency representations is a prerequisite for virtually every advanced topic in network science.
Practice Problems
Summary & Key Concepts
A graph G = (V, E) models a network by abstracting entities as vertices and relationships as edges. Two vertices sharing an edge are called adjacent. The adjacency matrix A is an n × n matrix whose entry aᵢⱼ equals 1 (or the edge weight) when vertices vᵢ and vⱼ are connected and 0 otherwise. For undirected graphs, this matrix is symmetric; for directed graphs it is generally not. Row sums give vertex degrees (or out-degrees), while the entries of Aᵏ count walks of length k between vertex pairs.
An alternative representation, the adjacency list, stores only the neighbors of each vertex and uses Θ(n + m) space, making it ideal for sparse graphs. Dense graphs and analyses requiring matrix algebra—such as spectral methods, walk enumeration, and centrality computations—favor the matrix form. Together, these representations provide the computational foundation for all network algorithms studied in finite mathematics, from shortest paths and spanning trees to flow optimization and community detection.