AI HL · AHL 1
0 of 43 skills done
Adjacency matrices and degree
AHL 1.2
Screenshot and video to come
Press a vertex, then another, to add an edge. Press one vertex twice for a loop. Press an edge to remove it. Drag a vertex to move it.
Press a vertex, then another, to add an edge.
The graph has two edges between A and B. There is also a loop at C. Write down its adjacency matrix, with the vertices in the order A, B, C, D.
Have a go first. Then open the working one line at a time.
4 vertices: a 4 by 4 matrix
Rows and columns are in the order A, B, C, D. Entry in row i, column j is the number of edges between i and j.
Row A: [0, 2, 0, 0], row B: [2, 0, 1, 1], row C: [0, 1, 2, 1], row D: [0, 1, 1, 0]
A and B have two edges, so the entry is 2. The loop at C gives 2 on the diagonal.
\(\begin{pmatrix}0 & 2 & 0 & 0 \\ 2 & 0 & 1 & 1 \\ 0 & 1 & 2 & 1 \\ 0 & 1 & 1 & 0\end{pmatrix}\)
An undirected graph gives a symmetric matrix: the entry for AB equals the entry for BA.
A graph has adjacency matrix \(\begin{pmatrix}0 & 1 & 0 & 2 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 2 & 1 \\ 2 & 0 & 1 & 0\end{pmatrix}\), with rows and columns in the order A, B, C, D. Draw the graph. How many edges does it have?
Have a go first. Then open the working one line at a time.
AB: 1, AD: 2, BC: 1, CD: 1
Each entry above the diagonal says how many edges join that pair. Entries below repeat them.
C: 2, so one loop at C
A 2 on the diagonal is one loop. A, B and D have 0.
6 edges: AB, AD (2 edges), BC, a loop at C and CD
Two edges join A and D, drawn as two curves. The loop at C is drawn as a small circle on C.
The adjacency matrix of a graph, with rows and columns in the order A, B, C, D, E, is \(\begin{pmatrix}0 & 1 & 0 & 2 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 \\ 2 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0\end{pmatrix}\). List the vertices adjacent to B, and find the degree of A.
Have a go first. Then open the working one line at a time.
Row B: [1, 0, 1, 0, 0]
Adjacent vertices have a non-zero entry in the row.
A and C
The entries in columns A and C are non-zero.
0 + 1 + 0 + 2 + 1 = 4
The degree of a vertex is its row sum, because each entry counts edges.
The directed graph has adjacency matrix \(\begin{pmatrix}0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0\end{pmatrix}\). Rows are the vertex an edge is from and columns the vertex it goes to, in the order A, B, C, D. Find the out-degree and the in-degree of B.
Have a go first. Then open the working one line at a time.
Row B: [1, 0, 1, 0], sum 2
Row B lists the edges leaving B.
Column B: [1, 0, 0, 0], sum 1
Column B lists the edges arriving at B.
Out-degrees add to 6, in-degrees add to 6
Both totals equal the number of edges. The matrix is not symmetric.
A directed graph has adjacency matrix \(\begin{pmatrix}0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0\end{pmatrix}\), with rows and columns in the order P, Q, R, S. Rows are the vertex an edge leaves. Draw the graph. How many edges does it have?
Have a go first. Then open the working one line at a time.
P: to Q and R; Q: to P and R; R: to S; S: to P
A 1 in row P, column Q is an arrow from P to Q.
6 edges
P to Q and Q to P are two separate edges, drawn as curves either side. The matrix is not symmetric.