Adjacency matrix and incidence matrix with an example

### Adjacency Matrix and Incidence Matrix: Explanation with Example

#### **Adjacency Matrix**
An adjacency matrix is a square matrix used to represent a graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

- For an undirected graph:
  - \( A[i][j] = 1 \) if there is an edge between vertex \( i \) and vertex \( j \), otherwise \( A[i][j] = 0 \).
  - The matrix is symmetric.

- For a directed graph:
  - \( A[i][j] = 1 \) if there is a directed edge from vertex \( i \) to vertex \( j \), otherwise \( A[i][j] = 0 \).

#### **Incidence Matrix**
An incidence matrix represents the relationship between vertices and edges in a graph. It is a \( |V| \times |E| \) matrix, where:
- \( V \) is the set of vertices, and \( E \) is the set of edges.
- For an undirected graph:
  - \( I[i][j] = 1 \) if vertex \( i \) is connected to edge \( j \).
- For a directed graph:
  - \( I[i][j] = -1 \) if vertex \( i \) is the tail of edge \( j \), \( 1 \) if it is the head, and \( 0 \) otherwise.

---

### Example

Consider the following undirected graph with 3 vertices (\( V = \{1, 2, 3\} \)) and 3 edges (\( E = \{e_1, e_2, e_3\} \)):

```
Vertices: 1, 2, 3
Edges:
e1: (1, 2)
e2: (2, 3)
e3: (3, 1)
```

#### **Adjacency Matrix**
Since the graph is undirected, the adjacency matrix is symmetric:

\[
A =
\begin{bmatrix}
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0
\end{bmatrix}
\]

Explanation:
- \( A[1][2] = A[2][1] = 1 \) because there is an edge \( e_1 \) between vertices 1 and 2.
- \( A[2][3] = A[3][2] = 1 \) because there is an edge \( e_2 \) between vertices 2 and 3.
- \( A[3][1] = A[1][3] = 1 \) because there is an edge \( e_3 \) between vertices 3 and 1.
- Diagonal elements are \( 0 \) since there are no loops.

#### **Incidence Matrix**
The incidence matrix for the graph is:

\[
I =
\begin{bmatrix}
1 & 0 & 1 \\
1 & 1 & 0 \\
0 & 1 & 1
\end{bmatrix}
\]

Explanation:
- The rows represent vertices \( 1, 2, 3 \), and the columns represent edges \( e_1, e_2, e_3 \).
- For \( e_1 \), vertices \( 1 \) and \( 2 \) are connected, so \( I[1][1] = I[2][1] = 1 \).
- For \( e_2 \), vertices \( 2 \) and \( 3 \) are connected, so \( I[2][2] = I[3][2] = 1 \).
- For \( e_3 \), vertices \( 3 \) and \( 1 \) are connected, so \( I[3][3] = I[1][3] = 1 \).

---

### Summary Table

| **Matrix Type** | **Size**         | **Representation** |
|------------------|------------------|---------------------|
| Adjacency Matrix | \( |V| \times |V| \) | Pairwise vertex connectivity |
| Incidence Matrix | \( |V| \times |E| \) | Vertex-edge relationships    |

---

### Questions to Explore
1. How does the adjacency matrix differ for weighted graphs?
2. How can adjacency matrices be used for finding the shortest path?
3. What are the key applications of incidence matrices in network analysis?
4. Can incidence matrices represent directed graphs with weights?
5. How do these matrices help in determining the degree of vertices?

**Tip:** Understanding these matrices helps in analyzing properties like connectedness, cycles, and paths in graphs. They are foundational tools in graph theory and network analysis.

Explore the concept of adjacency and incidence matrices with a clear explanation and example. Learn how to represent graphs using these matrices, including the relationships between vertices and edges. Suitable for high school students studying graph theory.

Math Problem Statement

Solution

Ask a new question for Free

By Image

Math Problem Analysis

Mathematical Concepts

Formulas

Theorems

Suitable Grade Level

Related Recommendation