Graphs, minimum spanning trees and Dijkstra flashcards

Test yourself one card at a time: say the answer, flip, then mark it. Cards you know drop out; the rest come back until you know them. Your progress stays in this browser.

Degree (valency) of a vertex
The number of edge-ends at the vertex; a loop counts 2.
Path
A walk in which no vertex is visited more than once (so no edge is repeated).
Trail
A walk in which no edge is used more than once (vertices may be revisited).
Cycle
A closed path: it returns to its start vertex and no other vertex is repeated.
Simple graph
A graph with no loops and at most one edge joining any pair of vertices.
Tree; spanning tree
Tree: a connected graph with no cycles. Spanning tree: a subgraph that is a tree and contains every vertex.
Planar graph
A graph that can be drawn in a plane with no two edges crossing.
Isomorphic graphs
Graphs that are the same apart from how they are drawn: a one-to-one matching of vertices preserves every edge.
Eulerian / semi-Eulerian graph
Eulerian: a closed trail uses every edge once. Semi-Eulerian: a non-closed trail uses every edge once.
Distance (weight) matrix
A table with a row and column per vertex whose entries are arc weights; a dash means no direct arc.
Handshaking result
Sum of the degrees = 2 × number of edges (No — learn it)
Edges and degrees of the complete graph Kn
½n(n − 1) edges; every vertex has degree n − 1 (No — derive it)
Number of arcs in a spanning tree on n vertices
n − 1 (No — learn it)
Degree test for Eulerian and semi-Eulerian graphs
Connected + all degrees even ⇔ Eulerian; connected + exactly two odd vertices ⇔ semi-Eulerian (No — learn it)
Dijkstra trace-back test for arc XY
XY is on the shortest route if final(Y) − final(X) = weight of XY (No — learn it)
Dijkstra box: what goes where?
Top row: vertex, order of labelling, final value. Bottom: every working value, in the order written.
K4 drawn as a square with both diagonals: is it planar?
Yes — move one vertex inside the triangle of the other three and no edges cross.
Prim on a distance matrix: what do you write on the table?
Number the columns in the order the vertices join, cross out each new vertex's row, circle each chosen entry.
Adjacency matrix of an undirected graph: what shape?
Symmetric about the leading diagonal; row sums are degrees (with no loops); an entry 2 means two edges.
Adjacency matrix of a digraph
Row X, column Y counts arcs from X to Y, so it need not be symmetric.
Kruskal's algorithm
Sort arcs by weight; add each in turn unless it makes a cycle; stop at n − 1 arcs.
Prim's algorithm
Start at any vertex; repeatedly add the cheapest arc from a vertex in the tree to one not in it, until all vertices are in.
Dijkstra's algorithm
Start 0; from each new permanent vertex update smaller working values; make the smallest working value permanent; repeat; trace back.
Prim versus Kruskal
Prim's tree is always connected and needs no cycle check, and works directly on a matrix; Kruskal needs sorting and may build separate pieces.
Why must the number of odd vertices be even?
The degrees add to 2 × edges, an even number; an odd count of odd degrees would give an odd sum.
Does a minimum spanning tree give shortest routes between vertices?
No — it minimises total weight, not distances between particular pairs. Use Dijkstra for a shortest route.
Kruskal on the notes network (A–H), taking AB before EF at weight 7: which arc is rejected and what is the MST weight?
GH, BD, AC, DE, CD, EG added; AB 7 rejected (cycle A–B–D–C); EF added. Weight 36.
Prim from A on the same network: order of arcs?
AC, CD, DB, DE, EG, GH, EF — same tree as Kruskal, weight 36; GH 3 joins sixth.
Arcs SA 4, SB 9, AB 3, AT 11, BT 6. Shortest route S to T?
A 4; B 9 then 7; T 15 then 13. Route S–A–B–T, length 13.
How many edges does K7 have?
½ × 7 × 6 = 21 (each of 7 vertices has degree 6).
Degrees 4, 4, 3, 3, 2, 2: number of edges? Degrees 5, 4, 3, 3, 2, 2: possible?
18 ÷ 2 = 9 edges. The second sums to 19 (odd), so no such graph exists.
Prim from P on the six-village matrix of the notes: order of vertices and total?
P, Q, R, T, S, U using PQ 14, QR 12, RT 13, RS 16, SU 11: total 66 km.
MST of K6 with distinct weights: how many arcs are left out?
K6 has 15 arcs; the tree uses 5; so 10 are not used.
Kruskal: when exactly is an arc rejected?
Only when both ends are already connected through chosen arcs (it would close a cycle) — not just because one end is in the tree.
Prim: which arc first?
The cheapest arc leaving the given start vertex — not the cheapest arc in the whole network.
Dijkstra: when do you write a new working value?
Only when it is smaller than the current working value; list all improving values in order.
Dijkstra: tracing back the route
Show final(Y) − final(X) = weight XY for each arc, working back from the destination.
Showing two graphs are not isomorphic when degrees match
Find a structural difference, e.g. one has a triangle and the other does not.
Edges crossing in a drawing
This does not prove a graph is non-planar; try to redraw it without crossings.

Practise this topicNotes Questions (28)Test builder