Overview
Many real problems are about points and the connections between them: computers joined by cables, cities joined by flight routes, rooms joined by hallways. A graph is the mathematical object that models all of these situations.
A graph is a collection of vertices (also called nodes) and edges. An edge is a connection between two vertices. We usually draw a graph with dots for vertices and lines for edges, but the graph itself is defined by its sets, not by any particular picture. Two drawings that look completely different can represent exactly the same graph.
Key Concepts:
- A graph is fully described by its set of vertices and its set of edges, e.g. V = {A, B, C, D, E, F, G, H} and E = {AB, AD, BD, CF, FG, GH, GE, HE}.
- Edges may be undirected (AB is the same as BA) or directed (AB goes from A to B only).
- Questions usually ask you to count paths or cycles, decide whether a graph is a tree, or read a graph from its adjacency matrix.
Key Concepts
Terminology
Take the undirected graph with vertices {A, B, C, D, E, F, G, H} and edges {AB, AD, BD, CF, FG, GH, GE, HE} as a running example.
- Path: a list of vertices in which each consecutive pair is joined by an edge. FGHE is a path from F to E.
- Simple path: a path with no repeated vertex. FGHEG is a path but not a simple one.
- Connected graph: there is a path between every pair of vertices. If you picked the graph up by any vertex, it would all come along.
- Connected components: the separate pieces of a graph that is not connected. The example has two: {A, B, D} and {C, E, F, G, H}.
- Cycle: a simple path except that it starts and ends at the same vertex. HEGH is a cycle. Listing the same loop from a different starting vertex (EGHE) or in the other direction (HGEH) still names the same cycle, so count each loop once.
- Complete graph: every possible edge is present. A graph with few edges is sparse; one with few edges missing is dense.
Directed Graphs
In a directed graph every edge has a direction. The edge XY can be used to travel from X to Y but not from Y to X unless YX is also an edge. Arrows on both ends of a line mean both directions are present, which behaves like an undirected edge. A directed graph with no cycles is called a DAG (directed acyclic graph).
For example, with vertices {A, B, C, D, E, F, G, H} and directed edges {AB, AD, DA, DB, EG, GE, HG, HE, GF, CF, FC}, there is exactly one directed path from G to C (G → F → C), but no directed path from C back to G.
Trees and Forests
- A tree is a connected graph with no cycles. Between any two vertices of a tree there is exactly one path.
- A tree with N vertices always has exactly N - 1 edges. A connected graph with N vertices and N - 1 edges must be a tree.
- A forest is a collection of disconnected trees.
- A weighted graph gives each edge a number (a cost or distance). A spanning tree is a subgraph that includes every vertex and forms a tree; a minimal spanning tree has the smallest total weight.
Adjacency Matrices
A graph with N vertices can be stored as an N × N grid. Label the rows and columns with the vertices in the same order. Put a 1 in row X, column Y if there is an edge from X to Y, and 0 otherwise. For an undirected graph the matrix is symmetric; for a directed graph it usually is not.
Counting paths with matrix powers
- M itself counts paths of length 1 (the edges).
- M2 counts paths of length 2: cell (i, j) of M2 is the number of two-edge routes from i to j.
- In general, Mp(i, j) is the number of paths of length p from vertex i to vertex j.
- To compute an entry of M2 by hand, multiply row i of M by column j of M and add: the sum counts every middle vertex k with edges i → k and k → j.
Examples
How many different cycles are in the directed graph with vertices {A, B, C, D, E} and edges {AB, BA, BC, CD, DC, DB, DE}?
List the edges leaving each vertex, then look for loops that return to their start without repeating a vertex in between.
- A → B, B → A: the cycle ABA.
- C → D, D → C: the cycle CDC.
- B → C → D → B: the cycle BCDB.
- E has no outgoing edges, so nothing that reaches E can come back.
There are 3 cycles.
Directed graph with vertices {A, B, C, D} and edges {AB, AD, BC, BD, CB, DC}.
Matrix M (row = from, column = to):
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 0 | 1 |
| B | 0 | 0 | 1 | 1 |
| C | 0 | 1 | 0 | 0 |
| D | 0 | 0 | 1 | 0 |
To find the number of paths of length 2 from A to C, multiply row A by column C: (0)(0) + (1)(1) + (0)(0) + (1)(1) = 2. The two paths are A → B → C and A → D → C.
Similarly, row A times column D gives (0)(1) + (1)(1) + (0)(0) + (1)(0) = 1, the single path A → B → D. Row B times column B gives (0)(1) + (0)(0) + (1)(1) + (1)(0) = 1, the path B → C → B.
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 0 | 1 |
| B | 1 | 0 | 0 | 1 |
| C | 1 | 0 | 0 | 0 |
| D | 0 | 1 | 1 | 0 |
The matrix is 4 × 4, so there are 4 vertices. Every 1 is an edge, read as row → column: the seven edges are {AB, AD, BA, BD, CA, DB, DC}. The graph is directed because the matrix is not symmetric (AB is present but CA has no matching AC).
Practice Problems
Problem 1 Junior
An undirected graph has vertices {A, B, C, D, E, F, G, H} and edges {AB, BC, DE, EF, FD, GH}. How many connected components does it have?
Solution
Group the vertices that can reach one another:
- AB and BC join A, B and C: component {A, B, C}.
- DE, EF and FD join D, E and F: component {D, E, F}. (This one contains the cycle DEFD.)
- GH joins G and H: component {G, H}.
No edge connects any two of these groups.
3 connected components
Problem 2 Junior
How many different cycles are there in the directed graph with vertices {A, B, C, D, E} and edges {AB, BC, CA, CD, DE, ED}?
Solution
Outgoing edges: A → B; B → C; C → A, D; D → E; E → D.
- Starting at A: A → B → C → A returns to A. Cycle ABCA.
- From C the other edge goes to D, and D → E → D returns to D. Cycle DED.
- Once you leave C for D you can never get back to A, B or C (D and E only point at each other), so there is no longer cycle that uses CD.
2 cycles
Problem 3 Intermediate
A directed graph has vertices {A, B, C, D} and edges {AB, AC, BC, BD, CD, DA}. How many different paths of length 2 are there from A to D?
Solution
A path of length 2 from A to D has the form A → X → D, so X must be reachable from A and must have an edge to D.
- From A you can go to B or C.
- B → D is an edge, so A → B → D works.
- C → D is an edge, so A → C → D works.
Using the adjacency matrix instead: row A = (0, 1, 1, 0) and column D = (0, 1, 1, 0), so M2(A, D) = 0 + 1 + 1 + 0 = 2.
2 paths
Problem 4 Intermediate
The adjacency matrix below represents a directed graph with vertices A, B, C, D (rows are the starting vertex, columns the ending vertex). How many different paths of length 3 are there from D back to D?
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 0 | 0 | 1 | 1 |
| C | 0 | 0 | 0 | 1 |
| D | 1 | 0 | 0 | 0 |
Solution
Read the edges from the matrix: AB, AC, BC, BD, CD, DA.
- D has only one outgoing edge, D → A, so every path from D starts D → A.
- From A the second edge goes to B or to C.
- The third edge must end at D. B → D is an edge, and C → D is an edge.
The length-3 paths from D to D are D → A → B → D and D → A → C → D. (The third possible path from D, D → A → B → C, ends at C, not D.)
2 paths
Problem 5 Senior
How many different cycles are there in the directed graph with vertices {A, B, C, D, E} and edges {AB, AC, BC, BD, CD, DE, EA}?
Solution
Outgoing edges: A → B, C; B → C, D; C → D; D → E; E → A.
- The only way back to A is through E, and the only way into E is from D. So every cycle must contain the segment D → E → A. That means every cycle passes through A, and we can count cycles by counting the simple routes from A to D.
- A → B → D: cycle ABDEA.
- A → C → D: cycle ACDEA.
- A → B → C → D: cycle ABCDEA.
- There is no route from C back to B and no other edge into D, so these are all of them.
3 cycles