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$.
ExampleConsider 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.
- For a strongly-connected graph (where there's a path between any two vertices), we can construct a transition matrix by normalizing each row of the adjacency matrix so that the sum of each row equals 1.
To construct a transition matrix:
- Start with the adjacency matrix
- For each row, divide each entry by the sum of that row
Consider the directed graph above.
Its adjacency matrix is:
\[ A = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{bmatrix} \]
The corresponding transition matrix would be:
\[ T = \begin{bmatrix} 0 &\frac{1}{2} &\frac{1}{2} \\\frac{1}{2} & 0 &\frac{1}{2} \\\frac{1}{2} &\frac{1}{2} & 0 \end{bmatrix} \]
NoteTransition matrices are crucial in understanding Markov chains, which model sequences of possible events where the probability of each event depends only on the state in the previous event.
PageRank Algorithm
- The PageRank algorithm, developed by Google founders Larry Page and Sergey Brin, is a famous application of adjacency matrices and transition matrices in graph theory.
- It's used to rank web pages in Google's search engine results.
At its core, PageRank models the web as a directed graph where:
- Vertices represent web pages
- Edges represent hyperlinks between pages
The algorithm uses a slightly modified version of a transition matrix, where:
- Each entry represents the probability of moving from one page to another
- A damping factor is introduced to model the probability of a user randomly jumping to any page
A simplified version of the PageRank calculation:
- Start with a graph of web pages and their links.
- Create the adjacency matrix $A$.
- Normalize $A$ to create a transition matrix $T$.
- Modify $T$ with a damping factor d (typically 0.85): $M=d \cdot T+(1−d) \cdot \frac{1}{n}J$ where J is an n×n matrix of all 1's, and n is the number of pages.
- Find the principal eigenvector of $M$ (usually through iteration).
- The resulting vector gives the PageRank scores for each page.
Students often confuse the PageRank algorithm with a simple count of incoming links. While incoming links are important, PageRank also considers the importance of the pages those links come from.
Connection to Markov Chains
The concepts of adjacency matrices and transition matrices in graph theory are closely linked to the study of Markov chains in probability theory.
A Markov chain can be represented as a weighted directed graph, where:
- Vertices represent states
- Edges represent transitions between states
- Edge weights represent transition probabilities
Understanding the relationship between graphs and Markov chains is crucial for many applications in computer science, operations research, and data analysis.
