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:

\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.