Neural Sync Active

Computational Thinking · Week 7 — Graphs & matrices

Registry Synced

Computational Thinking · Week 7 — Graphs & matrices

1101 words

6 min read

2026-08-16

Reading compass

Now · Week map

Week 7 — graphs & matrices

Quiz 2 scope: Weeks 1–8 per IITM May 2026 foundation courses. Source baseline: IITM BS admissions important-dates calendar · May 2026 cycle. Times on assessments are operational conventions — verify hall ticket.

Part of the Quiz 2 prep system · Weeks 1–8 index · Pattern atlas · Formula chains.

Week map

Vertices & edges → adjacency idea → matrix stores edge data → read cell

Classify → Represent → Execute → Trap-check

Recognize: Ask: What does matrix entry (i,j) usually mean?
Procedure: Sum or count cells meeting rule (nonzero, or equals 1). Row i entries are out-edges from i in directed graph.
Variations / traps: Watch for: Row vs column meaning swapped for directed edges.

Formula chain (compressed)

graph V,E → adjacency list/matrix → matrix[i][j] cell meaning.

Graph — G = (V, E) — vertices + edges
Adjacency list — neighbours of v — sparse graphs
Adjacency matrix — A[i][j] = 1 if edge — dense / quick lookup
Undirected — A symmetric — edge i–j = j–i
Degree — count incident edges — row/column sums

Open interactive formula desk · Week 7 tab.

Deep study

Computational Thinking · Week 7 — Graphs and matrices

Deep study for Quiz 2 week 7. Graphs model connections between vertices; matrices store grid or adjacency data in rows and columns.

Week map

Vertex and edge → directed vs undirected → adjacency matrix → matrix indexing → paths and degrees.

Graph notation

Vertex (node) → entity → labeled $v_1, v_2, \ldots$ or named A, B, C.
Edge → connection between two vertices → $(u, v)$ .
Undirected edge → $\{u, v\}$ — travel both ways.
Directed edge → $(u \to v)$ — one-way arrow from $u$ to $v$ .
Degree of vertex → number of edges incident → in directed graph: in-degree and out-degree separately.

Mini-example: vertices {A, B, C}, edges A—B, B—C. A has degree 1, B has degree 2, C has degree 1.

Path

Path → sequence of vertices where consecutive pairs are edges.
Simple path → no repeated vertices.

Path A→B→C exists above; A→C does not (no direct edge).

Adjacency matrix notation

For

n

vertices labeled

0..n-1

$M$ is $n \times n$ matrix.
$M[i][j] = 1$ (or weight) if edge from $i$ to $j$ exists; else $0$ .
Undirected graph → matrix symmetric: $M[i][j] = M[j][i]$ .

Mini-example: 3 vertices, edges 0—1 and 1—2 (undirected):


text
M = [0 1 0]
    [1 0 1]
    [0 1 0]

Row

i

lists neighbors of vertex

i

(out-neighbors if directed).

Matrix indexing

$M[i][j]$ → row $i$ , column $j$ → 0-based unless problem states 1-based.
Row $i$ → all $j$ values — outgoing from $i$ .
Column $j$ → all $i$ values — incoming to $j$ (directed).

Pattern families

Easy — Read graph from diagram

Count vertices and edges. List neighbors of one vertex. Identify directed vs undirected.

Medium — Build or read adjacency matrix

Fill matrix from edge list. Read

M[i][j]

for edge existence. Check symmetry for undirected.

Hard — Degree and path reasoning

Compute degree from matrix row sums. Determine if path exists of length 2 (via intermediate vertex). Spot isolated vertex (all zeros in row and column).

Worked mini-examples

Example 1 — Neighbors.

Triangle on {0,1,2} all connected. Each vertex degree 2.

Example 2 — Directed matrix.

Edge

0 \to 1

only:

M[0][1]=1

M[1][0]=0

. Not symmetric.

Example 3 — Row sum = out-degree.

Row [0, 1, 1, 0] sums to 2 — vertex has two outgoing edges (directed).

Example 4 — Path length 2.

M[0][1]=1

and

M[1][2]=1

implies path 0→1→2 exists (length 2).

Example 5 — Isolated vertex.

Row and column all zero — no edges incident.

Traps

0-based vs 1-based vertex labels in matrix.
Directed edge $i \to j$ does not imply $j \to i$ .
Counting self-loop $M[i][i]=1$ in degree twice wrongly in undirected mental model.
Confusing number of vertices with matrix size $n$ .
Path vs edge — path can use multiple edges.

Diagnostic (try yourself)

Graph with vertices {P, Q, R} and edges P—Q, Q—R. What is degree of Q?
Write adjacency matrix (0/1) for single undirected edge between vertices 0 and 1, no other edges ( $n=2$ ).
In directed graph, $M[2][5]=1$ . What does this mean?
How many edges in undirected graph if adjacency matrix has 6 ones above the diagonal?
Vertex with row sum 0 in directed adjacency matrix — what can you conclude?

ChatGPT prep archive

Chatty reference archive

Archived import for extra depth — complements the notes above, not official IITM material.

Core concepts

Graph: vertices (nodes) and edges (connections); may be directed or undirected.
Adjacency: whether edge exists between two vertices.
Matrix representation: rows and columns index vertices; cell encodes edge weight or count.
Undirected: matrix often symmetric; directed: row → column direction.

Notation & vocabulary

Cell	Meaning
M[i][j]	edge from i to j
0	no edge (often)
>0	weight or count

Pattern families

Easy — Count edges from matrix

Sum or count cells meeting rule (nonzero, or equals 1). Row i entries are out-edges from i in directed graph.

Medium — Directed vs undirected

Undirected: M[i][j]=M[j][i]. Directed: only one direction may have entry. Neighbor of i: scan row i or column i per definition.

Hard — Path of length 2

Two-step paths via intermediate vertex k: check pairs (i,k) and (k,j). Nested loops over k and j common in CT traces.

Drill these on the pattern atlas — filter to week 7.

Traps

Row vs column meaning swapped for directed edges.
Assuming symmetry without undirected statement.
Diagonal entries (self-loops) policy ignored.
Counting each undirected edge twice.

Retrieval prompts

What does matrix entry (i,j) usually mean?
How to tell undirected from matrix?
Where are out-edges of vertex i?

Practice loop

Read Deep study (if present) or core concepts once.
Recite the formula chain without looking.
Open one easy pattern on the interactive atlas for week 7.
Attempt without solutions; mark studied after an honest try.
Say one trap aloud before closing the tab.