Graphs, routing and linear programming

From bridges to networks

In the 1700s the city of Königsberg had seven bridges joining two islands and two river banks. People wondered whether they could walk across every bridge exactly once. In 1736 Leonhard Euler showed it was impossible, and to do so he ignored the shapes of the land and the lengths of the bridges. He kept only the land areas as points and the bridges as lines. That simplified picture is a graph, and Euler’s argument started graph theory.

Today graphs model road maps, flight routes, electric grids, social media friendships and the internet. The questions stay the same: can we visit everything, what is the shortest route, and what is the cheapest way to connect it all?

Graphs

A graph is a set of vertices joined by edges. The degree of a vertex is the number of edges at it. The degrees of a graph always add up to twice the number of edges.

That last fact is the handshake theorem: every edge has two ends, so it adds 2 to the total degree. If the degrees of a graph add up to 30, it has 15 edges. One consequence is that the number of vertices with odd degree is always even.

Some more words:

• Two vertices joined by an edge are adjacent. A loop joins a vertex to itself and adds 2 to its degree.
• A path is a sequence of edges from one vertex to another; a circuit is a path that ends where it began.
• A graph is connected if there is a path between every pair of vertices.
• A weighted graph has a number, such as a distance, cost or time, on each edge.

1. Euler and Hamilton

• An Euler circuit uses every edge once and returns to the start. It exists when a connected graph has all even degrees.
• An Euler path uses every edge once. It exists when exactly two vertices have odd degree.
• A Hamiltonian path visits every vertex once, and a Hamiltonian circuit also returns to the start.

The reason is simple. Each time a route passes through a vertex it uses two edges, one in and one out, so the degree must be even. Only the start and end of a path may be odd. In Königsberg the four land areas had degrees 5, 3, 3 and 3. All four were odd, so no walk could cross every bridge once.

An Euler route is about edges; think of a street sweeper or a mail carrier who must cover every street. A Hamiltonian route is about vertices; think of a delivery truck that must stop at every store. There is no simple degree test for Hamiltonian circuits, but every complete graph with 3 or more vertices has one.

The travelling salesperson problem

Finding the shortest Hamiltonian circuit in a weighted graph is the travelling salesperson problem. A complete graph with n vertices has (n − 1)! ÷ 2 different Hamiltonian circuits, so 5 cities give 4! ÷ 2 = 12 circuits, but 15 cities give over 43 billion. Checking every circuit, the brute force method, is exact but becomes impossible quickly.

The nearest-neighbour method is a fast shortcut: from the start, always go to the closest vertex not yet visited, and return to the start at the end. Suppose a courier leaves town P, and the distances in km are P–Q 15, P–R 25, P–S 40, Q–R 20, Q–S 35 and R–S 30. From P the closest is Q (15). From Q the closest unvisited is R (20). From R only S is left (30). Then return S–P (40). The route P–Q–R–S–P is 15 + 20 + 30 + 40 = 105 km. The method is quick, but it does not always find the shortest circuit.

2. Complete graphs and trees

The complete graph K(n) has an edge between every pair: n(n − 1) ÷ 2 edges. A tree is connected with no cycles, and with n vertices it has n − 1 edges.

The count for K(n) works like a handshake count: each of the n vertices joins the other n − 1, and each edge is counted twice. A round-robin league of 8 teams, where every team plays every other once, needs 8 × 7 ÷ 2 = 28 games.

A tree is the leanest way to connect vertices: removing any edge disconnects it, and adding any edge creates a cycle. A tree with 12 edges has 13 vertices. Family trees, folder systems on a computer and tournament brackets are trees.

3. Graph colouring

To colour a graph, give each vertex a colour so that adjacent vertices never share one. The least number of colours needed is the chromatic number.

• A complete graph K(n) needs n colours, because every vertex touches every other.
• A tree with at least one edge needs only 2.
• A circuit needs 2 colours if it has an even number of vertices and 3 if it has an odd number.

Colouring solves scheduling problems. Make each subject a vertex and join two subjects when some student takes both. Each colour is then an exam time slot, and the chromatic number is the fewest slots that avoid conflicts. The four colour theorem, proved in 1976 with a computer, says any map drawn on a flat surface can be coloured with at most 4 colours so that neighbouring regions differ.

4. Efficient networks

A spanning tree of a connected graph is a tree that includes every vertex. In a weighted graph, the one with the smallest total weight is the minimum spanning tree. It answers questions such as the cheapest way to lay cables or pipes so that every barangay is connected.

Kruskal’s algorithm finds a minimum spanning tree: keep taking the cheapest edge that does not form a cycle.

The steps are:

• List the edges from cheapest to most expensive.
• Take the cheapest edge.
• Take the next cheapest edge, unless it would form a cycle with the edges already chosen; then skip it.
• Stop when you have n − 1 edges for n vertices.

Because a spanning tree is a tree, it always has exactly one edge fewer than the number of vertices, which tells you when to stop.

5. Linear programming

Linear programming maximizes or minimizes a linear objective subject to linear constraints. The best value occurs at a corner of the feasible region, so test the corners.

To maximize P = 3x + 2y with x + y ≤ 4, x ≥ 0, y ≥ 0, test (0, 0), (4, 0) and (0, 4). The largest value is P = 12 at (4, 0).

A fuller problem shows the method. A bakery makes x trays of pandesal and y trays of ensaymada. It has oven time for at most 40 trays a day, so x + y ≤ 40, and enough flour for 2x + y ≤ 60. Profit is ₱50 a tray of pandesal and ₱40 a tray of ensaymada, so P = 50x + 40y, with x ≥ 0 and y ≥ 0.

• Graph the constraints. The shaded region where all of them hold is the feasible region.
• Find its corners: (0, 0), (30, 0), (0, 40), and where x + y = 40 meets 2x + y = 60. Subtracting the first equation from the second gives x = 20, so y = 20.
• Test each corner: P(0, 0) = 0, P(30, 0) = 1,500, P(0, 40) = 1,600 and P(20, 20) = 1,800.

The bakery earns the most, ₱1,800, by making 20 trays of each.

Solved examples

Follow each one line by line. The steps stay the same when the numbers change, so cover the steps and try it yourself.

Example 1: Euler path or circuit

Question: A graph has edges A–B, A–C, B–C, B–D and C–D. Does it have an Euler circuit or an Euler path?

1. Count the degree of each vertex. A = 2, B = 3, C = 3, D = 2.
2. Check the sum. 2 + 3 + 3 + 2 = 10, twice the 5 edges.
3. Count the odd vertices. B and C are odd, so there are exactly two.
4. Apply the rule. Two odd vertices give an Euler path that starts at one and ends at the other: B, A, C, B, D, C.

Answer: It has an Euler path but no Euler circuit.

Example 2: Kruskal’s algorithm

Question: The links are A–B 4, A–C 2, B–C 5, B–D 3, C–D 6. Find the minimum spanning tree.

1. Sort the edges by cost. A–C 2, B–D 3, A–B 4, B–C 5, C–D 6.
2. Take the cheapest edges. A–C, then B–D. Neither forms a cycle.
3. Keep going until n − 1 edges. 4 vertices need 3 edges. A–B joins the two pieces, so that makes 3.
4. Add the costs. 2 + 3 + 4 = 9.

Answer: The tree is A–C, B–D, A–B, with a total cost of 9.

Example 3: Linear programming

Question: Maximize P = 4x + 3y subject to x + y ≤ 6, x ≤ 4, x ≥ 0, y ≥ 0.

1. Find every corner of the region. (0, 0), (4, 0), (0, 6), and where x = 4 meets x + y = 6, which is (4, 2).
2. Test each corner in P. (0, 0) gives 0. (4, 0) gives 16. (0, 6) gives 18. (4, 2) gives 16 + 6 = 22.
3. Pick the largest. 22 is the highest.

Answer: The maximum is P = 22 at (4, 2).

Common mistakes

• Forgetting to halve the degree sum. The number of edges is half the total degree.
• Mixing up Euler and Hamilton. Euler covers every edge; Hamilton visits every vertex.
• Accepting an Euler circuit with odd vertices. A circuit needs every degree even; a path allows exactly two odd ones.
• Taking an edge that closes a cycle in Kruskal’s algorithm. Skip it, even if it is cheap.
• Assuming nearest neighbour is optimal. It is fast, not guaranteed to be shortest.
• Testing only some corners. Find every corner of the feasible region, including intersections of constraint lines.

Where you will meet this

• Transport and delivery. Route planning for jeepneys, couriers and garbage trucks uses Euler and Hamiltonian ideas.
• Utilities. Electric, water and fibre networks are designed as minimum spanning trees.
• Scheduling. Exam and class timetables come from graph colouring.
• Business. Production and diet planning use linear programming.

Key terms

Graph

A set of vertices joined by edges.

Degree

The number of edges meeting at a vertex.

Euler circuit

A circuit that uses every edge exactly once.

Hamiltonian circuit

A circuit that visits every vertex exactly once.

Tree

A connected graph with no cycles; n vertices and n − 1 edges.

Chromatic number

The fewest colours needed so that adjacent vertices differ.

Summary

• The degrees add up to twice the number of edges.
• A connected graph has an Euler circuit if all degrees are even, and an Euler path if exactly two are odd.
• Hamiltonian circuits visit every vertex; nearest neighbour finds a good one quickly, and K(n) has (n − 1)! ÷ 2 of them.
• K(n) has n(n − 1) ÷ 2 edges and chromatic number n; a tree has one fewer edge than vertices.
• Kruskal’s algorithm takes the cheapest edges that form no cycle.
• In linear programming, the best value is at a corner of the feasible region.