PGDDSA Study · Semester 1

Core Titles

Key headlines and terms for quick recall

Adjacency matrix $A$ (size $n \times n$ , $a_{ij}=1$ if edge)
Incidence matrix $B$ ( $n \times m$ )
Circuit matrix
Cut-set matrix
Path matrix
$A^k[i][j]$ counts walks of length $k$ from $i$ to $j$

Basic Idea

What it is, why it matters, how it works

Why represent a graph as a matrix?

Matrices let us apply linear algebra to graphs — count walks, find connected components, study spectra, run algorithms.

Adjacency matrix $A$

For a graph on $n$ vertices, $A$ is the $n \times n$ matrix where $A_{ij} = \begin{cases} 1 & \text{if } (v_i, v_j) \in E \\ 0 & \text{otherwise} \end{cases}$ For undirected graphs, $A$ is symmetric. For weighted graphs, store the weight instead of 1.

Key fact. $A^k_{ij}$ counts the number of walks of length $k$ from $v_i$ to $v_j$ .

Incidence matrix $B$

Rows = vertices, columns = edges. For undirected graph: $B_{ij} = 1$ if $v_i$ is incident to edge $e_j$ , else 0. For digraph: $+1$ for tail, $-1$ for head.

Circuit (cycle) matrix

Rows = fundamental circuits, columns = edges. Entry is 1 if the edge is in the circuit. Useful in network analysis.

Cut-set matrix

Rows = fundamental cut-sets, columns = edges. Entry 1 if the edge crosses the cut.

Path matrix

$P_{ij} = 1$ if there is a path from $v_i$ to $v_j$ (the transitive closure of $A$ ). Computed by repeatedly OR-ing $A, A^2, A^3, \dots$ or by Warshall's algorithm.

Why this matters in Data Science

Graph neural networks operate on adjacency matrices. PageRank, spectral clustering and recommender systems use eigenvectors of $A$ or the Laplacian $L = D - A$ .

Mind Map

Visual structure of the concept

MATRIX REPRESENTATIONS
├── Adjacency A  (n × n)
│   ├── Aᵢⱼ = 1 if edge
│   ├── Undirected ⇒ symmetric
│   ├── Aᵏ counts walks of length k
│   └── Laplacian  L = D − A
├── Incidence B (n × m)
│   ├── Undirected: 1 if vertex on edge
│   └── Directed: −1 tail / +1 head
├── Circuit matrix
├── Cut-set matrix
└── Path matrix (transitive closure of A)

Exam Q&A

Part A (2 marks) and Part B (20 marks) style questions

Part A (2 marks each)

Q1. Define adjacency matrix of a graph. For a graph on $n$ vertices, the $n \times n$ matrix $A$ with $A_{ij} = 1$ if there is an edge between $v_i$ and $v_j$ , else 0.

Q2. What does $A^2_{ij}$ represent? The number of walks of length 2 from $v_i$ to $v_j$ .

Q3. Difference between incidence and adjacency matrix. Adjacency is vertex × vertex; incidence is vertex × edge.

Q4. For an undirected graph, what property does $A$ have? $A$ is symmetric.

Part B (20 marks)

Q. Describe the matrix representations of a graph — adjacency, incidence, circuit and path matrix. Take the graph $G$ with $V = \{1,2,3,4\}$ and edges $\{(1,2),(2,3),(3,4),(4,1),(1,3)\}$ and write its adjacency and incidence matrices. Use $A^2$ to count walks of length 2 from vertex 1.

(i) Adjacency matrix. $V$ × $V$ . Entry $A_{ij} = 1$ if $\{i, j\}$ is an edge.

$A = \begin{pmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix}$

(Vertex 1 is adjacent to 2, 3, 4; vertex 2 to 1, 3; vertex 3 to 1, 2, 4; vertex 4 to 1, 3.)

(ii) Incidence matrix. $V$ × $E$ . Label edges $e_1=(1,2), e_2=(2,3), e_3=(3,4), e_4=(4,1), e_5=(1,3)$ .

$B = \begin{pmatrix} 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 \end{pmatrix}$

(iii) Circuit matrix — rows index fundamental circuits (cycles), columns index edges. For each cycle, mark the edges in it. The cycle $1{-}2{-}3{-}1$ uses $e_1, e_2, e_5$ , giving row $(1,1,0,0,1)$ , and so on.

(iv) Path matrix is the transitive closure of $A$ (here all entries become 1 since $G$ is connected).

Walks of length 2 from vertex 1. Compute the first row of $A^2$ :

$A^2_{1,1} = \sum_k A_{1k} A_{k1} = 0\cdot 0 + 1\cdot 1 + 1\cdot 1 + 1\cdot 1 = 3$ (walks $1\to 2\to 1$ , $1\to 3\to 1$ , $1\to 4\to 1$ ).

$A^2_{1,2} = \sum_k A_{1k} A_{k2} = 0 + 0 + 1 + 0 = 1$ (walk $1\to 3\to 2$ ).

$A^2_{1,3} = 0 + 1 + 0 + 1 = 2$ (walks $1\to 2\to 3$ and $1\to 4\to 3$ ).

$A^2_{1,4} = 0 + 0 + 1 + 0 = 1$ (walk $1\to 3\to 4$ ).

So from vertex 1 there are 3 closed, 1 to vertex 2, 2 to vertex 3, 1 to vertex 4 — total of 7 walks of length 2.

Matrix Representation of Graphs