Neural Sync Active

Week 7: Graphs & Matrices

Registry Synced

Week 7: Graphs & Matrices

3245 words

16 min read

2026-09-12

Reading compass

Now · TL;DR

Computational Thinking — Week 7: Graphs & Matrices

IITM’s CT Week 7 covers Graphs and Matrices.

TL;DR

Week 6 dealt with:

\text{records and mappings}

Week 7 moves to:

\boxed{ \text{objects + connections between objects} }

A graph represents entities as nodes and relationships as edges.

A matrix gives a compact numerical representation of structured relationships.

Core ideas:

vertex/node
edge
directed vs undirected graph
degree
paths and connectivity
matrix rows and columns
graph ↔ matrix representation
reading connections from a matrix

1. What is a graph?

A graph is a mathematical/computational structure consisting of:

vertices (nodes)
edges (connections)

Notation:

\boxed{ G=(V,E) }

where:

$V$ = set of vertices
$E$ = set of edges

2. Example

Suppose:

V=\{A,B,C\}

and:

E=\{\{A,B\},\{B,C\}\}.

Conceptually:


text
A --- B --- C

There is:

an edge between A and B
an edge between B and C
no direct edge between A and C

3. Real-world graph examples

Graphs can represent:

people and friendships
cities and roads
webpages and links
computers and network connections
courses and prerequisites
airports and flights

The graph abstraction ignores irrelevant details and focuses on:

\boxed{ \text{who is connected to whom} }

4. Vertex

A vertex is one entity in the graph.

Example:


text
A

could represent:

a person
a city
a computer
a course

depending on context.

5. Edge

An edge represents a relationship between two vertices.

Example:


text
A --- B

could mean:

A and B are friends
road connects A and B
computers A and B communicate

The interpretation depends on the application.

6. Undirected graph

An undirected edge has no orientation.

Notation:

\{A,B\}

or visually:


text
A --- B

If A is connected to B, B is also connected to A.

Examples:

friendship
two-way roads
physical cable connection

7. Directed graph

A directed edge has a direction.

Notation:

(A,B)

or:


text
A ---> B

This does not automatically imply:


text
B ---> A

Examples:

Instagram follow
webpage hyperlink
prerequisite
one-way road

8. Directed vs undirected

Undirected

A-B

means a symmetric relationship.

Directed

A\to B

means orientation matters.

This distinction becomes very important when reading matrix representations.

9. Neighbor / adjacency

Two vertices are adjacent if an edge directly connects them.

Example:


text
A --- B --- C

A and B are adjacent.

B and C are adjacent.

A and C are not directly adjacent.

10. Neighborhood

The neighborhood of a vertex is the collection of its adjacent vertices.

For:


text
A --- B --- C
      |
      D

neighbors of B are:

\boxed{ \{A,C,D\} }

11. Degree

In an undirected graph, the degree of a vertex is the number of incident edges.

Notation:

\deg(v)

Example:


text
A --- B --- C
      |
      D

Then:

\deg(B)=3.

12. Degree example

Graph:


text
A --- B
|     |
C --- D

Each vertex has degree:

2.

13. Isolated vertex

A vertex with degree:

0

is isolated.

Example:


text
A --- B      C

Then:

\deg(C)=0.

14. Directed degree

For directed graphs we distinguish:

In-degree

Number of incoming edges.

\deg^-(v)

Out-degree

Number of outgoing edges.

\deg^+(v)

15. Example


text
A ---> B ---> C
      ^
      |
      D

For B:

incoming from:

so:

\deg^-(B)=2.

Outgoing to:

so:

\deg^+(B)=1.

16. Path

A path is a sequence of vertices connected by edges.

Example:


text
A --- B --- C --- D

A path from A to D is:

A,B,C,D.

17. Path length

The length of a path is usually the number of edges traversed.

For:

A\to B\to C\to D

there are:

3

edges.

So path length:

\boxed{3}

18. Reachability

Vertex B is reachable from A if there exists a path from A to B.

In directed graphs, reachability depends on edge direction.

Example:


text
A ---> B ---> C

C is reachable from A.

But A is not necessarily reachable from C.

19. Connected graph

An undirected graph is connected if every vertex can reach every other vertex through some path.

Example:


text
A --- B --- C
      |
      D

All vertices belong to one connected structure.

20. Disconnected graph

Example:


text
A --- B     C --- D

There is no path between:

A

and:

C.

So the graph is disconnected.

21. Connected components

A disconnected graph can be divided into connected components.

For:


text
A --- B     C --- D     E

components are:

\{A,B\}

\{C,D\}

\{E\}

So there are:

3

components.

22. Cycle

A cycle is a path that returns to its starting vertex.

Example:


text
A --- B
|     |
D --- C

Cycle:

A\to B\to C\to D\to A.

23. Self-loop

An edge from a vertex to itself is a self-loop.

Conceptually:


text
A ↺

Whether self-loops are allowed depends on the graph definition/problem.

Do not assume unless specified.

24. Complete graph

A complete undirected graph connects every pair of distinct vertices.

Notation:

K_n.

For

n

vertices, number of edges:

\boxed{ \binom n2 = \frac{n(n-1)}2 }

This connects directly to Stats combinatorics and CT pairwise iteration.

25. Example

For:

K_4,

number of edges:

\binom42=6.

Every vertex has degree:

3.

26. Handshaking lemma

In any undirected graph:

\boxed{ \sum_{v\in V}\deg(v)=2|E| }

Why?

Every edge contributes:

1

to the degree of each endpoint.

So each edge is counted twice.

27. Example

Suppose degrees are:

2,3,1,2.

Sum:

2+3+1+2=8.

Therefore:

2|E|=8

so:

\boxed{|E|=4}.

28. Matrix

A matrix is a rectangular arrangement of values.

Example:

A= \begin{bmatrix} 1&2&3\\ 4&5&6 \end{bmatrix}

It has:

2 rows
3 columns

So its dimension is:

\boxed{2\times3}

29. Matrix entry

The entry in row

i

, column

j

is often written:

a_{ij}.

For:

A= \begin{bmatrix} 1&2\\ 3&4 \end{bmatrix},

a_{12}=2

and:

a_{21}=3.

30. Row vs column

In:

A= \begin{bmatrix} 1&2&3\\ 4&5&6 \end{bmatrix},

first row:

[1,2,3]

second column:

\begin{bmatrix} 2\\ 5 \end{bmatrix}

Be precise about row/column orientation.

31. Matrix as structured table of numbers

A matrix resembles a numerical table.

But in mathematics/computation, its position structure is especially important.

Each element is identified by:

(row,column).

32. Graph representation using a matrix

One major connection is the adjacency matrix.

Week 8 explicitly continues with adjacency matrices, but Week 7's graph + matrix topics set up this idea.

Suppose vertices:

A,B,C.

33. Example graph


text
A --- B
 \   /
   C

Every pair is connected.

Adjacency matrix:

\begin{bmatrix} 0&1&1\\ 1&0&1\\ 1&1&0 \end{bmatrix}

Rows and columns correspond to:

A,B,C.

34. Reading an adjacency-like matrix

Entry:

M_{ij}=1

can mean:

there is an edge from vertex $i$ to vertex $j$ .

Entry:

M_{ij}=0

means:

no edge.

This binary encoding turns graph structure into a matrix.

35. Undirected graph matrix symmetry

For an undirected graph:

i\text{ connected to }j

implies:

j\text{ connected to }i.

Therefore adjacency matrix is symmetric:

\boxed{ M_{ij}=M_{ji} }

36. Example

M= \begin{bmatrix} 0&1&0\\ 1&0&1\\ 0&1&0 \end{bmatrix}

Since:

M=M^T

in this sense, it can represent an undirected graph.

Graph:


text
A --- B --- C

37. Directed graph matrix

For:


text
A ---> B ---> C

matrix may be:

\begin{bmatrix} 0&1&0\\ 0&0&1\\ 0&0&0 \end{bmatrix}

This is not symmetric.

That is normal because directions differ.

38. Matrix row interpretation in directed graphs

For an adjacency matrix, a row can represent outgoing edges.

Example:

\begin{bmatrix} 0&1&1 \end{bmatrix}

for vertex A means A has outgoing edges to:

assuming row-as-source convention.

39. Row sum and degree

For a simple undirected graph with binary adjacency matrix:

\boxed{ \text{row sum} = \deg(v) }

Example row:

[0,1,1,0]

sum:

2.

So degree is:

2.

40. Directed row/column sums

Under the common convention:

M_{ij}=1

when edge:

i\to j,

then:

row sum = out-degree
column sum = in-degree

This is a useful graph-matrix connection.

41. Example

M= \begin{bmatrix} 0&1&1\\ 0&0&1\\ 1&0&0 \end{bmatrix}

Row 1 sum:

2

so vertex 1 has out-degree 2.

Column 1 sum:

1

so in-degree 1.

42. Diagonal entries

Entries:

M_{ii}

lie on the main diagonal.

In a simple graph without self-loops:

\boxed{ M_{ii}=0 }

for every vertex.

If a diagonal entry is 1, that may indicate a self-loop.

43. Matrix dimensions for graph

If graph has:

n

vertices, adjacency matrix is:

\boxed{ n\times n }

because every vertex is compared against every vertex.

This is exactly like nested pair iteration.

44. Graph ↔ nested-loop connection

An adjacency matrix essentially stores information for every pair:

(i,j).

Nested iteration:


text
for each i:
    for each j:

naturally visits every matrix cell.

So CT Weeks 4 and 7 connect directly.

45. Matrix traversal

Conceptually:


text
for each row i:
    for each column j:
        process M[i][j]

This is a nested loop.

For an:

m\times n

matrix, number of cells is:

\boxed{mn}

46. Example

Matrix:

\begin{bmatrix} 2&4\\ 5&7\\ 1&3 \end{bmatrix}

has:

3\times2=6

entries.

A full traversal processes six cells.

47. Sum of matrix entries

Algorithm:


text
total = 0

for each row:
    for each entry:
        total = total + entry

For:

\begin{bmatrix} 1&2\\ 3&4 \end{bmatrix},

sum:

1+2+3+4=10.

48. Row sums

For:

M= \begin{bmatrix} 1&2&3\\ 4&5&6 \end{bmatrix},

row sums:

6,\ 15.

One outer loop per row, one inner loop over columns.

49. Column sums

Column sums:

1+4=5

2+5=7

3+6=9.

The traversal ordering may differ depending on algorithm.

50. Matrix transpose intuition

Transposing a matrix swaps rows and columns.

If:

A= \begin{bmatrix} 1&2&3\\ 4&5&6 \end{bmatrix},

then:

A^T= \begin{bmatrix} 1&4\\ 2&5\\ 3&6 \end{bmatrix}.

So:

(A^T)_{ij}=A_{ji}.

51. Symmetric matrix

A square matrix is symmetric if:

\boxed{ A=A^T }

equivalently:

a_{ij}=a_{ji}.

Undirected adjacency matrices are a key example.

52. Matrix and table distinction

Both have rows and columns, but:

Table

Rows often represent heterogeneous records.

Example:


text
Name | City | Score

Matrix

Entries are usually treated as elements of a uniform rectangular numerical structure.

This distinction matters computationally.

53. Graph representation choices

A graph can be represented in multiple ways.

Conceptually:

visual diagram
edge list
adjacency list
matrix

Week 7 focuses on graph/matrix foundations; adjacency matrices are developed further in Week 8.

54. Edge-list intuition

Graph:


text
A --- B
B --- C

could be stored as:


text
(A,B)
(B,C)

This directly stores existing edges.

55. Matrix intuition

The same graph can be represented by checking every pair:

\begin{array}{c|ccc} & A&B&C\\ \hline A&0&1&0\\ B&1&0&1\\ C&0&1&0 \end{array}

This uses:

n^2

cells.

56. Sparse graph intuition

A sparse graph has relatively few edges compared with all possible pairs.

Example:

1000

vertices but only:

1200

edges.

An adjacency matrix still has:

1000^2=1,000,000

cells.

Most would be zero.

57. Dense graph intuition

A dense graph has many of the possible edges.

For an undirected simple graph, maximum edges:

\binom n2.

When actual edge count is close to that, the graph is dense.

Matrices can become comparatively natural for dense graphs.

Common mistake: vertex vs edge

Vertices are objects.

Edges are relationships.

Do not say:

A-B is a vertex.

It is an edge connecting vertices A and B.

Common mistake: path must be direct

A and C can be connected by a path even if there is no direct edge.

Example:


text
A --- B --- C

No edge:

A-C.

But path exists:

A-B-C.

Common mistake: directed edge is reversible

If:

A\to B,

do not assume:

B\to A.

Direction matters unless reverse edge is explicitly present.

Common mistake: degree in directed graph

Do not collapse in-degree and out-degree if the question distinguishes them.

A vertex may have:

\deg^-=5

and:

\deg^+=1.

Common mistake: path length = number of vertices

Path:

A-B-C-D

contains:

4

vertices but:

\boxed{3}

edges.

Path length is generally measured in edges.

Common mistake: disconnected means no edges

A disconnected graph may contain many edges.

Example:


text
A---B---C     D---E

Each component contains edges.

The issue is absence of paths between components.

Common mistake: matrix index reversal

a_{ij}

means:

\boxed{ \text{row }i,\text{ column }j }

not the reverse.

This becomes especially important for directed adjacency matrices.

Common mistake: every square matrix is symmetric

No.

Example:

\begin{bmatrix} 0&1\\ 0&0 \end{bmatrix}

is square but not symmetric.

Square only means:

\text{rows}=\text{columns}.

Common mistake: undirected adjacency matrix not symmetric

If an undirected simple graph's adjacency matrix has:

M_{ij}=1

but:

M_{ji}=0,

something is inconsistent.

An undirected edge must appear in both mirrored positions.

Common mistake: diagonal entries as ordinary edges

In a simple graph with no self-loops:

M_{ii}=0.

Do not count diagonal entries as connections between distinct vertices.

Common mistake: edge count from matrix

For an undirected graph, summing all adjacency-matrix entries counts each ordinary edge twice.

So:

\boxed{ |E| = \frac12 \sum_{i,j}M_{ij} }

for a simple undirected binary adjacency matrix.

69. Example

M= \begin{bmatrix} 0&1&1\\ 1&0&0\\ 1&0&0 \end{bmatrix}

Sum entries:

4.

Therefore edges:

\frac42=2.

Indeed:


text
B --- A --- C

has 2 edges.

70. Directed edge count from matrix

For a directed graph without special complications, each directed edge appears once.

So:

\boxed{ |E|=\sum_{i,j}M_{ij} }

for a binary directed adjacency matrix.

No division by 2.

71. Matrix traversal trace

Suppose:

M= \begin{bmatrix} 1&0\\ 1&1 \end{bmatrix}

Algorithm:


text
C = 0

for each row i:
    for each column j:
        if M[i][j] == 1:
            C = C + 1

There are three 1s.

So:

\boxed{C=3}

72. Graph-degree trace from matrix

Suppose:

M= \begin{bmatrix} 0&1&1&0\\ 1&0&1&1\\ 1&1&0&0\\ 0&1&0&0 \end{bmatrix}

Row sums:

2,3,2,1.

Thus degrees:

\boxed{ 2,\ 3,\ 2,\ 1 }

Check handshaking:

2+3+2+1=8.

Therefore:

|E|=4.

73. Graph representation as abstraction

Suppose four people have dozens of attributes.

For a friendship problem, we may throw away:

height
marks
address
age

and keep only:


text
person A connected to person B?

That is computational abstraction:

\boxed{ \text{keep only structure relevant to the problem} }

74. Week 7 master map


text
GRAPH
│
├── vertices
├── edges
├── directed / undirected
├── degree
├── path
├── reachability
├── connectivity
└── cycles
        ↓
MATRIX REPRESENTATION
│
├── rows / columns
├── entries aᵢⱼ
├── n × n for graph
├── symmetry for undirected graphs
└── row/column sums encode degree

75. Weeks 5–7 progression


text
Week 5
List
↓
ordered sequence

Week 6
Table / Dictionary
↓
structured records + lookup

Week 7
Graph / Matrix
↓
relationships between entities

So CT is gradually introducing different structures suited to different kinds of information.

76. Connection to Maths 1

Maths 1 Week 10–11 covered graph theory more mathematically.

CT Week 7 approaches graphs as a computational representation of data and relationships.

The concepts overlap:

vertices
edges
paths
matrices

but CT's emphasis is on how algorithms represent and process them.

77. What you should actually master

By the end of CT Week 7, you should be able to:

Define a graph.
Distinguish vertices and edges.
Distinguish directed and undirected graphs.
Identify adjacent vertices.
Calculate degree in an undirected graph.
Distinguish in-degree and out-degree.
Identify paths and their lengths.
Understand reachability.
Distinguish connected and disconnected graphs.
Identify connected components.
Recognize cycles.
Understand matrix rows, columns and entries.
Determine matrix dimensions.
Traverse a matrix using nested iteration.
Understand how a matrix can encode graph connections.
Recognize symmetry for undirected adjacency matrices.
Use row sums to infer degrees.
Avoid double-counting undirected edges in matrix form.

If these are comfortable, Computational Thinking Week 7 is under control.

Quick Recall & Flashcards

Test your active recall before proceeding to practice problems. Format:

Question :: Answer.

Week 7 Diagnostic: In a graph G = (V, E), if |V| = 5, what is the dimension of its adjacency matrix? :: Answer: B — An adjacency matrix has rows and columns corresponding to each vertex, so it is a |V| x |V| matrix (5 x 5).
Week 7 Diagnostic: In an undirected graph, what property does the adjacency matrix always have? :: Answer: B — Since undirected edges are bidirectional ((u, v) = (v, u)), the adjacency matrix is symmetric.

Practice & Self-Check

Attempt these diagnostic questions to verify your operational understanding.

Question 1

In a graph G = (V, E), if |V| = 5, what is the dimension of its adjacency matrix?

MCQ

3 Unit Assessment

A. 5 x 1

B. 5 x 5

C. 10 x 10

D. 5 x 2

Question 2

In an undirected graph, what property does the adjacency matrix always have?

MCQ

3 Unit Assessment

A. It is upper-triangular

B. It is symmetric across the main diagonal (A[i][j] = A[j][i])

C. All diagonal elements are 1

D. It is strictly non-zero