Unit 12 — Graph Theory

Lesson 1 — Vertices, edges, paths and cycles

Division: Elementary and above. This whole lesson is pencil-and-paper work. It is everything the ACSL Elementary Graph Theory test asks, and it is the starting point for every other division.

Vertices and edges

A graph is a set of vertices (points, also called nodes) and a set of edges (connections between two vertices). ACSL writes a graph as two sets:

• the vertices, {A, B, C, D};

• the edges, {AB, AC, BC, AD, DB}, where AB is the edge between A and B.

Here is one way to draw this graph:

    A
   /|\
  C | D
   \|/
    B

The drawing does not matter, only the two sets do: you could put the letters anywhere and bend the lines, and it would still be the same graph. When you draw a graph from its sets, draw a dot for each vertex first, then one line for each edge.

In this lesson the edges have no direction: DB is the same edge as BD, and you can walk along it either way. Such a graph is undirected. The ACSL Elementary test uses undirected graphs only.

Degree

The degree of a vertex is the number of edges that touch it. In the graph above, A touches AB, AC and AD, so A has degree 3. B also has degree 3, and C and D have degree 2.

A handy check. Every edge has two ends, so adding up all the degrees gives twice the number of edges. Here 3 + 3 + 2 + 2 = 10, and the graph has 5 edges.

Paths and simple paths

A path is a list of vertices in which each vertex is joined to the next one by an edge. Its length is the number of edges it uses, which is one less than the number of letters.

In the graph {AB, AC, BC, AD, DB}:

• BD is a path of length 1 from B to D;

• BAD is a path of length 2 from B to D;

• BACBD is a path of length 4, but it visits B twice.

A simple path is a path that never repeats a vertex. BD and BAD are simple paths; BACBD is not.

Example 1 (from ACSL's Elementary handout). List all simple paths of length 3 starting from vertex C.

Grow the paths one step at a time, trying the neighbours in alphabetical order, and never step onto a letter already in the path.

From C the only first steps are A and B, because CD is not an edge. The answer is CABD, CADB, CBAD, CBDA: four simple paths. This book lists paths in alphabetical order, separated by a comma and a space.

Example 2. List all simple paths from B to D, of any length. Grow paths from B in the same way, and stop a path as soon as it reaches D.

The answer is BAD, BCAD, BD.

Example 3. How many simple paths of length 2 does the graph have in all? In the Elementary division a path and its reverse are different paths: ABD goes from A to D, and DBA goes from D to A. A path of length 2 is a middle vertex with two different neighbours, one on each side. A has 3 neighbours, so it is the middle of 3 × 2 = 6 paths (BAC, BAD, CAB, CAD, DAB, DAC); B is also the middle of 6; C and D are each the middle of 2 × 1 = 2. The total is 6 + 6 + 2 + 2 = 16.

Connected graphs

A graph is connected when there is a path from every vertex to every other vertex. Picture the vertices as beads and the edges as strings: a connected graph stays in one piece when you pick it up by any bead. Our graph is connected. If the edges AC and BC were missing, C would be on its own, and the graph would fall into two pieces: {C} and {A, B, D}.

Cycles

A cycle is a path that comes back to where it started, and is simple apart from that: no vertex repeats except the first one, which is also the last. It is written with its start letter twice, once at each end, like ABDA.

• In an undirected graph a cycle has at least 3 different vertices. ABA just walks along one edge and back, so it is not a cycle.

• The same cycle can be written from any of its vertices: ABDA, BDAB and DABD are one cycle.

• A cycle can be travelled in two directions: ABDA and ADBA go round the same triangle, opposite ways.

How the Elementary division counts cycles. ACSL's Elementary handout counts a cycle once in each direction: ABDA and ADBA are two cycles, but ABDA and BDAB are the same one. So in an undirected graph the number of cycles is always even.

Example 4 (from ACSL's Elementary handout). Find all the cycles in the graph {AB, AC, BC, AD, DB}.

Look for the loops in the drawing: triangle ABC, triangle ABD, and the big loop A–C–B–D round the outside. Write each one starting from its alphabetically first letter, in both directions:

There are 6 cycles.

Cycles through one vertex. A question may ask for the cycles that start and end at a given vertex. Write each one from that vertex, in both directions. For vertex B in this graph: BACB, BADB, BCAB, BCADB, BDAB, BDACB. They are the same 6 cycles, each written from B, in alphabetical order.

Complete graphs

A complete graph has an edge between every pair of vertices. Drawn as a polygon, it is the polygon with all of its diagonals.

Count the edges in two ways. Handshakes: each of the V vertices has an edge to the V − 1 others, and that counts every edge twice (once from each end), so there are V × (V − 1) ÷ 2 edges. Polygon: V sides plus the diagonals. A pentagon has 5 sides and 5 diagonals: 10 edges.

A complete graph with 6 vertices has 6 × 5 ÷ 2 = 15 edges, which is also the number of handshakes when 6 people each shake hands with everybody else once.

Traversable graphs

A graph is traversable when you can draw it without lifting your pencil, going along every edge exactly once. (You may pass through a vertex as many times as you like.)

The most famous example is the Seven Bridges of Königsberg. The city had two islands and seven bridges, and people wondered whether they could walk across every bridge exactly once. As a graph, the four land areas are vertices and the bridges are edges, and the degrees are 3, 3, 5 and 3. In 1735 Leonhard Euler proved it cannot be done, with this rule.

The traversability rule. A graph is traversable exactly when:

1. every vertex that has an edge is in one connected piece, and

2. the number of vertices with an odd degree is 0 or 2.

If there are 2 odd vertices, the walk must start at one of them and finish at the other. If there are none, it can start anywhere, and it finishes where it started.

Why? Each time the walk passes through a vertex, it uses one edge in and one edge out: two edges. Only the start and the finish can have a spare edge.

Königsberg has 4 odd vertices, so it is not traversable.

Watch out: the first condition matters. Two separate triangles, {AB, AC, BC, DE, DF, EF}, have every degree equal to 2, so no odd vertices at all, but you cannot jump from one triangle to the other without lifting your pencil. They are not traversable. A vertex with no edges at all (degree 0) does not matter: there is nothing to draw there.

Back to the park

The paths are {AB, AE, BC, BE, CD, DE}.

Question 1, the rake. The degrees are A 2, B 3, C 2, D 2 and E 3, and the park is in one piece. Exactly two vertices, B and E, have odd degree, so yes: Ms. Okafor can rake every path once, if she starts at B and finishes at E (or the other way round). One such walk is B, A, E, B, C, D, E.

Question 2, the jog. The loops that pass through A are the triangle A–B–E and the big loop A–B–C–D–E. Each can be run in two directions, and written from A:

ABCDEA, ABEA, AEBA, AEDCBA

There are 4 loops. (The loop B–C–D–E does not pass through A, so it does not count here.)

Question 3 needs Lesson 2.

Elementary checklist. You can now:

• read a graph from its vertex set and edge set, and draw it;

• find the degree of a vertex;

• list the simple paths of a given length from a vertex, or between two vertices;

• count simple paths, where a path and its reverse count as two;

• list and count cycles, counting each cycle once in each direction;

• count the edges of a complete graph;

• decide whether a graph is traversable, and where the walk must start and finish.

That is the whole Elementary test. Exercises 1 to 6 are an Elementary mock test: try all six in 30 minutes, as in the real contest. Exercises 7 to 9 are extra Elementary practice. Junior, Intermediate and Senior students continue with Lessons 2 and 3.

Lesson 2 — Directed graphs and adjacency matrices

Division: Junior and above.

Directed graphs

In a directed graph every edge has an arrow. The edge AB goes from A to B: a path may use it from A to B, but not from B to A. A two-way connection needs two edges, AB and BA. A directed graph is written just like an undirected one, as a vertex set and an edge set; the question says which kind it is.

Here is the directed graph {AB, AD, BC, CB, CD, DA}, with its arrows drawn as >, <, v and ^:

A -----> B
^ |      ^ |
| v      | v
D <----- C

Read it edge by edge: A to B along the top, C to D along the bottom, and two arrows on each side: A down to D and D up to A on the left, B down to C and C up to B on the right. A sketch like this is only a help: the edge set is the real definition, so always read the question's edge set.

Cycles, counted once

From Junior up, ACSL follows its Graph Theory wiki page, which counts each cycle once: "HEGH and EHGE are different ways to identify the same cycle". The direction you travel it in does not make a new cycle.

• Undirected graphs. The graph {AB, AC, BC, AD, DB} of Lesson 1 has 3 cycles: ABCA, ABDA and ACBDA. (The Elementary handout counted 6, because it counts both directions.)

• Directed graphs. A cycle must follow the arrows, so it can only be travelled one way anyway. In a directed graph a cycle may have just 2 vertices: if both AB and BA are edges, ABA is a cycle.

Example 1. Count the cycles of the directed graph {AB, AD, BC, CB, CD, DA}. A good way not to miss any: for each vertex in alphabetical order, find the cycles whose smallest letter is that vertex.

• Smallest letter A: ABCDA (along AB, BC, CD, DA) and ADA.

• Smallest letter B: BCB.

• Smallest letter C or D: none new (CDC would need the edge DC, which is not there).

There are 3 cycles.

Example 2 (ACSL's wiki sample). The directed graph {AB, BA, BC, CD, DC, DB, DE} has the cycles ABA, BCDB and CDC: 3 cycles.

Watch out: always read which way a question counts. In this book, Elementary questions count a cycle in each direction, and Junior, Intermediate and Senior questions count it once; every question also says so in words.

The adjacency matrix

An adjacency matrix is a table with one row and one column for each vertex, in alphabetical order. The entry in row i, column j is 1 if there is an edge from i to j, and 0 if not.

For the directed graph {AB, AD, BC, CB, CD, DA}:

Things to notice:

• The 1s in row A are the edges leaving A; the 1s in column A are the edges arriving at A.

• The number of 1s in a row is the vertex's out-degree, and in a column its in-degree.

• An undirected edge AB is an edge both ways, so it puts a 1 in row A, column B and in row B, column A. The matrix of an undirected graph is symmetric about its diagonal, and each row total is the vertex's degree.

• A loop AA, an edge from a vertex to itself, puts a 1 on the diagonal.

A question may also give you the matrix and ask for the graph: every 1 is an edge, from its row letter to its column letter.

Counting paths with the matrix

From Junior up, "the number of paths of length p" means the number of ways to walk along exactly p edges, and the walk may repeat vertices and edges. (This is different from the Elementary division's simple paths, so every question says which it means.)

Paths of length 2. A path of length 2 from i to j goes i → k → j through some middle vertex k. It exists when both M(i, k) and M(k, j) are 1, that is, when M(i, k) × M(k, j) is 1. So the number of paths of length 2 from i to j is

M(i, A) × M(A, j) + M(i, B) × M(B, j) + M(i, C) × M(C, j) + M(i, D) × M(D, j)

which is row i of M times column j of M: multiply the matching entries, then add. Doing this for every i and j is matrix multiplication, and the result is written M².

Example 3. How many paths of length 2 go from A to C? Row A is 0 1 0 1, and column C is 0 1 0 0 (read down the C column). Multiply matching entries: 0 × 0 + 1 × 1 + 0 × 0 + 1 × 0 = 1. The one path is A → B → C.

The whole of M²:

M²(A, A) is 1: the path A → D → A, which comes back to its start. That is allowed here.

Paths of length 3. Multiply again: M³ = M² × M, row of M² times column of M. M³(A, B) is row A of M², 1 0 1 0, times column B of M, 1 0 1 0: 1 + 0 + 1 + 0 = 2. The two paths are A → D → A → B and A → B → C → B.

Row totals. The total of row i of M^p is the number of paths of length p that start at i, going anywhere. Row A of M² adds up to 2: ABC and ADA.

Example 4, back to the park (question 3). The dog walks the undirected park graph {AB, AE, BC, BE, CD, DE}, and a walk of 3 minutes is a path of length 3 that may repeat. With the vertices in the order A B C D E, row A of M is 0 1 0 0 1, and so is column A. M² row A is 2 1 1 1 1, and M³(A, B) = row A of M² times column B of M (1 0 1 0 1) = 2 + 0 + 1 + 0 + 1 = 4. The four walks are ABAB, ABCB, ABEB and AEAB.

Components, trees and forests

A graph that is not connected falls into pieces called connected components. The undirected graph {AB, AD, BD, CF, FG, GH, GE, HE} has two: {A, B, D} and {C, E, F, G, H}. A vertex with no edges at all is a component on its own, so always check the vertex set for letters that no edge mentions. (This book asks about components in undirected graphs only.)

A tree is a connected graph with no cycles. There is exactly one simple path between any two of its vertices, and a tree with N vertices always has exactly N − 1 edges. Build one vertex at a time and you can see why: the first vertex needs no edge, and every later vertex needs exactly one edge to join on.

A forest is a graph made of separate trees. Each tree has one edge fewer than its vertices, so a forest with N vertices and E edges is made of N − E trees.

Weighted graphs and the cheapest path

Division: Intermediate and above.

In a weighted graph every edge has a number, its weight or cost, such as a distance or a ticket price. This book writes the weight straight after the edge: AB3 is an edge between A and B with weight 3. (An adjacency matrix still shows 1 for an edge and 0 for no edge, whatever its weight.)

The cost of a path is the total of its edge weights. To find the cheapest path between two vertices in a small graph, list every simple path between them and add up each one.

Example 5. In the undirected graph {AB3, AC1, BC1, BD4, CD6}, find the cheapest path from A to D.

The cheapest path is ACBD, with cost 6, even though it uses the most edges.

Spanning trees

A spanning tree of a connected graph keeps all the vertices and just enough edges to make a tree: V − 1 of them. Every connected graph has at least one. To count them in a small graph, remember that a spanning tree must break every cycle.

Example 6. The square {AB, BC, CD, AD} has 4 edges and 4 vertices, so a spanning tree keeps 3 edges. Removing any one of the 4 edges leaves a path through all four vertices, so there are 4 spanning trees. Removing two edges would leave only 2, too few.

When the weights matter, the minimal spanning tree is the spanning tree with the smallest total weight: the cheapest way to keep every vertex connected.

Directed acyclic graphs

A directed graph with no cycles is called a DAG (directed acyclic graph). Remember that in a directed graph ABA is a cycle when both AB and BA are edges. {AB, AC, BC} is a DAG; {AB, BC, CA} is not, because of ABCA. To test a graph, try to follow arrows from each vertex back to itself.

Longer paths and loops

For longer paths, keep multiplying: M⁴ = M³ × M, or M⁴ = M² × M², which is less work.

Example 7 (in the style of ACSL's wiki sample). In the directed graph {AA, AB, BC, CA}, how many paths of length 2 or 4 go from A to C? The loop AA puts a 1 in row A, column A, and a path may use it any number of times.

M² has rows 1 1 1, 1 0 0 and 1 1 0. M⁴ = M² × M² has row A equal to 3 2 1. So there is 1 path of length 2 (ABC) and 1 of length 4 (AAABC), and the answer is 1 + 1 = 2.

Lesson 3 — Graphs in Python

Division: Junior and above.

Letters and positions

A program keeps the vertices as a string of letters in alphabetical order, such as "ABCD", and refers to each vertex by its position in that string: A is 0, B is 1, and so on. The function spot finds a letter's position with a loop.

The adjacency matrix as a list of lists

The matrix is a list of rows, and each row is a list of numbers, just like the grids of Unit 3: matrix[r][c] is row r, column c. Start with every entry 0, then put in a 1 for each edge. For an undirected graph, each edge sets two entries.

Run it from this unit's folder:

python assets/l1.py < assets/l1/1.in

The input is the graph of Lesson 1, and the rows end degree 3, degree 3, degree 2, degree 2. assets/l1/3.in holds the park, where B and E have degree 3.

Multiplying matrices

M² is found entry by entry: row i of the first matrix times column j of the second, multiplying matching entries and adding them up. That is three loops, one inside another: i for the row, j for the column, and k for the position along them.

Run it from this unit's folder:

python assets/l2.py < assets/l2/1.in

The input is the graph above with p = 2, and the output is the M² table of Lesson 2. assets/l2/2.in asks for p = 3, and assets/l2/3.in has a loop AA.

Listing simple paths with recursion

A simple path grows one vertex at a time, never onto a letter it already has: exactly the table method of Lesson 1. The function extend does it with recursion (Unit 2). It gets the path so far as a string. If the path is long enough, it prints it; otherwise it tries every neighbour of the last letter that is not already in the path, and calls itself on the longer path. Trying the neighbours in alphabetical order prints the paths in alphabetical order.

Run it from this unit's folder:

python assets/l3.py < assets/l3/1.in

It prints the four paths of Example 1 and then total: 4. assets/l3/3.in asks for the paths of length 4 from A in the park, and assets/l3/4.in asks for paths too long to exist, so it prints only total: 0. Use it to check your Elementary answers.