Graph information models: adjacency matrices and counting paths

In this lesson you will learn

Recognise vertices, edges and degrees of a graph; tell directed and weighted graphs apart.
Turn an adjacency matrix into a drawing and back, and count its 1s.
Count the paths in a one-way road scheme with the “add the incoming numbers” method, also through a given vertex or avoiding it.
List all routes from a weighted table and choose the shortest.

A metro map, the roads between towns, friendships between classmates, web pages and the links between them — all of them contain objects and connections between the objects. The model of such a structure is a graph. In the 2025–2026 entrance exams in Azerbaijan (group I, informatics) every paper had a graph task: the number of 1s in a matrix, or the number of paths by a matrix or a road scheme. In both 2026 exams this task was coded, so the answer had to be written as a number with no options to choose from.

In the lesson “Tree information models” we saw that a tree is a graph without cycles. Now we work with general graphs — graphs with cycles, directions and weights.

A graph: vertices and edges

Definition

Graph

A graphic information model made of vertices and edges that join pairs of vertices. Vertices stand for objects and edges for the connections between them.

Vertex — an object (a town, a person, a page); edge — a line joining two vertices. Vertices joined by an edge are adjacent.
Directed graph — edges are arrows and you may move only in the direction of the arrow (one-way roads).
Weighted graph — every edge carries a number (weight): a distance, a price, a time.
Degree of a vertex — the number of edges at the vertex. A path is a sequence of vertices joined edge by edge; a path that returns to its start is a cycle.

deg(A₁) + deg(A₂) + … + deg(Aₙ) = 2 · m

where:

deg(Aᵢ)the degree of the i-th vertex
mthe number of edges

The “handshake” rule: every edge belongs to two vertices and is counted twice in the sum of degrees. So the sum of degrees is always even.

m = n · (n − 1) / 2m = n · (n − 1) / 2

where:

nthe number of vertices
mthe number of edges in a complete graph

A complete graph: every two vertices are joined (for example, every team plays every other team once).

Tasks 1–4: degrees and edges

1) Find the degree of every vertex and the number of edges of the graph in the picture below.
2) The degrees of a graph’s vertices are 4, 3, 3, 2, 2. How many edges does it have?
3) Can each of 5 friends be friends with exactly 3 of the others?
4) 6 teams play a tournament in which every team plays every other team once. How many games will there be?

Show solution

1) A — 2, B — 3, C — 3, D — 2, E — 2. The sum is 12 = 2 · m → m = 6 (AB, AC, BC, BD, CE, DE).
2) m = (4 + 3 + 3 + 2 + 2) / 2 = 14 / 2 = 7.
3) No: the sum of degrees would be 5 · 3 = 15, an odd number, but it always equals 2 · m, which is even.
4) A complete graph: m = 6 · 5 / 2 = 15 games.

The adjacency matrix

Definition

Adjacency matrix

An n × n table for a graph with n vertices: where row X meets column Y you write 1 if X and Y are joined by an edge and 0 if they are not. It is a special case of the “object–object” table from the lesson “Table information models: solving logic puzzles with tables”.

Every edge gives two 1s in the matrix: the edge AB appears both in row A and in row B. The number of 1s in a row is the degree of the vertex.

undirected graph: N₁ = 2 · m directed graph: N₁ = m

where:

N₁the number of 1s in the adjacency matrix
mthe number of edges (arrows)

In a directed graph the arrow X → Y gives a 1 in one cell only, where row X meets column Y; such a matrix is usually not symmetric.

Tasks 5–6: 1s in the matrix

5) How many 1s are in the adjacency matrix of the graph in the picture? What does the number of 1s in each row show?
6) The rows of an undirected graph’s adjacency matrix contain 4, 3, 3, 2 and 2 ones. How many edges does the graph have, and which row belongs to the vertex of the greatest degree?

Show solution

5) N₁ = 2 · 6 = 12. The number of 1s in a row is the degree of the vertex: row A has 2, B 3, C 3, D 2, E 2.
6) The 1s add up to 4 + 3 + 3 + 2 + 2 = 14 = 2 · m → m = 7. The vertex of the greatest degree (4) is in the first row.

Task 7: splitting a graph into two

The adjacency matrix of the graph in the picture contains x ones. After the dashed edges are removed and the graph is split into two graphs, their adjacency matrices contain y ones in total. Find x − y.
A) 3 B) 12 C) 6 D) 18 E) 24

Show solution

Count the edges: 5 on the left, 4 on the right, 3 between them — 12 in all. x = 2 · 12 = 24.
After the cut, 5 + 4 = 9 edges remain: y = 2 · 9 = 18.
x − y = 24 − 18 = 6. Shortcut: x − y = 2 · (edges cut) = 2 · 3 = 6.
Answer: C.

Counting paths: “add the incoming numbers”

A scheme of one-way roads is a directed graph. If it has no cycles (you cannot leave a town and come back to it), it is easy to count how many ways lead from A to every town. Every way into a town passes through one of the towns that send an arrow into it, so the numbers of those towns are added up.

N(X) = N(Y₁) + N(Y₂) + … + N(Yₖ), N(A) = 1

where:

N(X)the number of different paths from A to X
Y₁, …, Yₖall vertices that send an arrow (a direct road) into X

Write 1 at the start; the number at every vertex is the sum of the numbers at the tails of the arrows coming into it.

1
Draw the graph
If a matrix or a list is given, draw the picture first: a 1 in row X, column Y → an arrow from X to Y.
2
Start
Write 1 at the start vertex.
3
Add
Pick a vertex whose incoming neighbours are all counted and add their numbers. Repeat until every vertex is done.
4
Answer
The number at the finish is the answer. When there are few paths, list them to check.

	B	C	D	E	F
A	1	1	1	0	0
B	0	0	1	0	1
C	0	0	0	1	0
D	0	0	0	1	1
E	0	0	0	0	1
F	0	0	0	0	0

The adjacency matrix of a directed graph (row — from, column — to)

Task 8: counting paths from a matrix

Using the adjacency matrix (the table above), in how many different ways can you get from vertex A to vertex F?

Show solution

Arrows: A → B, A → C, A → D, B → D, B → F, C → E, D → E, D → F, E → F (9 ones — 9 arrows).
N(A) = 1; N(B) = N(A) = 1; N(C) = N(A) = 1; N(D) = N(A) + N(B) = 2; N(E) = N(C) + N(D) = 3; N(F) = N(B) + N(D) + N(E) = 1 + 2 + 3 = 6.
Check: ABF, ABDF, ABDEF, ACEF, ADF, ADEF — 6 paths.
Answer: 6.

The numbers are the numbers of paths from A to each town; every number is the sum of the numbers of the towns that send an arrow into it.

Task 9: from A to K

The picture shows a scheme of roads between towns; each road may be used only in the direction of its arrow. In how many different ways can you get from town A to town K?

Show solution

The order matters: B and D must be counted before C, and C before E.
A = 1; B = A = 1; D = A = 1; C = A + B + D = 3; E = B + C = 4; F = C + D = 4; G = E = 4; H = E + F = 8; K = G + H + F = 4 + 8 + 4 = 16.
Answer: 16.

N(A → K, D-dən keçməklə) = N(A → D) · N(D → K)

where:

N(A → D)the number of paths from A to D
N(D → K)the number of paths from D to K (write 1 at D and count again)

Paths through a given vertex: every choice for the first part combines with every choice for the second, so the counts multiply.

Tasks 10–11: through D and avoiding C

For the same scheme: 10) How many paths from A to K pass through town D? 11) How many paths do not pass through town C?

Show solution

10) N(A → D) = 1 (only A → D). Write 1 at D and count from D: C = 1, E = C = 1, F = C + D = 2, G = E = 1, H = E + F = 3, K = G + H + F = 1 + 3 + 2 = 6 (B cannot be reached from D, so its number is 0). Answer: 1 · 6 = 6.
11) Delete C (N(C) = 0) and count again: B = 1, D = 1, E = B = 1, F = D = 1, G = 1, H = E + F = 2, K = G + H + F = 1 + 2 + 1 = 4. Answer: 4. Check: 16 − 4 = 12 paths pass through C.

The shortest route: a weighted graph

A weighted graph is often given as a table: a cell holds the length of the direct road between two towns, and an empty cell means there is no direct road. To find the shortest route, draw the graph from the table, list all routes without repeating towns, and add up their lengths. Careful: the shortest route is not always the one with the fewest roads. For large graphs there is Dijkstra’s algorithm — see the lesson “Graphs and graph algorithms”.

	P	Q	R	S	T
P		5	9	14
Q	5		3		11
R	9	3		4	8
S	14		4		2
T		11	8	2

Lengths of the direct roads between the towns P, Q, R, S, T, km (an empty cell means no direct road)

Task 12: the shortest route

According to the table, how many kilometres long is the shortest route from town P to town T?
A) 16 B) 13 C) 15 D) 11 E) 14

Show solution

All 9 routes that do not repeat towns:
P–Q–T = 5 + 11 = 16; P–Q–R–T = 5 + 3 + 8 = 16; P–Q–R–S–T = 5 + 3 + 4 + 2 = 14;
P–R–T = 9 + 8 = 17; P–R–S–T = 9 + 4 + 2 = 15; P–R–Q–T = 9 + 3 + 11 = 23;
P–S–T = 14 + 2 = 16; P–S–R–T = 14 + 4 + 8 = 26; P–S–R–Q–T = 14 + 4 + 3 + 11 = 32.
The shortest is P–Q–R–S–T = 14 km, even though it uses four roads.
Answer: E.

Interactive

Loading simulation…

Dijkstra’s algorithm finds the shortest distances without listing every route: at each step it “closes” the vertex with the smallest distance and updates the distances of its neighbours. Starting from A you end with: C 2, B 3 (A → C → B; the direct road A → B is 4), I 6, D 8, H 9, E 10, F 12, G 13. Tap a vertex to see the path to it.

Key points

A graph consists of vertices and edges; edges may be directed (arrows) and weighted (numbers).
The sum of degrees = 2 · edges; a complete graph has n · (n − 1) / 2 edges.
In an adjacency matrix every undirected edge gives two 1s and every arrow of a directed graph one 1; the 1s in a row give the degree.
On one-way roads: N(start) = 1, and every vertex = the sum of the vertices sending arrows into it.
“Through D” — N(A → D) · N(D → end); “avoiding X” — write 0 at X and count again.
The shortest route: list and add up all routes; the shortest route may not have the fewest roads.

Check yourself

12 questions. Every correct answer earns XP.

1 / 12

In the adjacency matrix of an undirected graph, the cell where row X meets column Y holds 1. What does it mean?