Adjacency Matrices and Tables in Graph Theory
Adjacency Matrices
- Adjacency matrices are a fundamental tool in graph theory, used to represent the structure of a graph in a compact, mathematical format.
- For a graph with $n$ vertices, an adjacency matrix is an $n \times n$ square matrix where each entry $a_{ij}$ represents the connection between vertices $i$ and $j$.
In an unweighted graph:
- $a_{ij} = 1$ if there is an edge from vertex $i$ to vertex $j$
- $a_{ij} = 0$ if there is no edge from vertex $i$ to vertex $j$
For undirected graphs, the adjacency matrix is symmetric, meaning $a_{ij} = a_{ji}$ for all $i$ and $j$.
Consider the undirected graph above.
Its adjacency matrix would be:
\[ A = \begin{bmatrix} 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 \end{bmatrix} \]
NoteThe diagonal entries of an adjacency matrix for a simple graph (without self-loops) are always 0.
Walks in Graphs
- A walk in a graph is a sequence of vertices and edges, starting and ending at a vertex, where each edge in the sequence is incident to the vertices immediately preceding and following it.
- The length of a walk is the number of edges in the sequence.
k-length Walks
- One of the powerful properties of adjacency matrices is their ability to reveal information about walks in the graph.
- Specifically, when we raise an adjacency matrix $A$ to the power $k$, the resulting matrix $A^k$ provides information about k-length walks:
- The entry $(A^k)_{ij}$ gives the number of walks of length exactly $k$ from vertex $i$ to vertex $j$.
Using the adjacency matrix from the previous example, let's calculate \( A^2 \):
\[ A^2 = \begin{bmatrix} 2 & 1 & 2 \\ 1 & 1 & 3 \\ 3 & 1 & 2 \end{bmatrix} \]
The entry \( A^2_{12} = 1 \) indicates that there is 1 walk of length 2 from vertex 1 to vertex 2.
TipTo find the number of walks of length $k$ or less between two vertices, you can sum the corresponding entries in $A, A^2, A^3, ..., A^k$.
Weighted Adjacency Tables
- While adjacency matrices are useful for unweighted graphs, weighted adjacency tables are used when edges have associated weights or costs.
- These weights could represent distances, costs, time, or any other quantifiable attribute of the connection between vertices.
- A weighted adjacency table is similar to an adjacency matrix, but instead of binary values, it contains the weights of the edges.
Consider a weighted graph representing a network of cities where the weights represent the distances (in kilometers) between them:
Graph Representation
The cities (vertices) are:
1 - A
2 - B
3 - C
4 - D
The edges (connections) and their corresponding weights (distances in km) are:
- A → B (5 km)
- A → C (10 km)
- B → C (3 km)
- B → D (7 km)
- C → D (2 km)
Weighted Adjacency Table
| Vertex | A | B | C | D |
|---|---|---|---|---|
| A | 0 | 5 | 10 | $\infty$ |
| B | 5 | 0 | 3 | 7 |
| C | 10 | 3 | 0 | 2 |
| D | $\infty$ | 7 | 2 | 0 |
Explanation:
- Each row and column represent a vertex.
- The diagonal elements are 0, indicating no self-loops.
- If there is no direct edge between two vertices, we use ∞ (infinity) to indicate no direct connection.
Transition Matrices
- A transition matrix is a special type of adjacency matrix used in the context of Markov chains and other probabilistic models.
