Networks, Paths and Trees

Networks questions are visual and methodical: if you follow the steps carefully, they are some of the most reliable marks in the paper. This focus area was worth 3 marks in the sample HSC paper, and it leads straight into Network flow and Critical path analysis in Year 12.

• Network terms: vertex, edge, degree, weighted edge, directed edge, path, cycle, connected network, tree, spanning tree, minimum spanning tree, shortest path.
• Use networks to represent real systems: roads, pipes, cables, social links.
• Draw a network from a table or a map, with weighted and directed edges.
• Find a minimum spanning tree by any method, and use it to solve minimal connector problems.
• Find the shortest path in a network with up to 10 vertices.
• Explain when the shortest path is not the best path.

A network is a set of objects called vertices (dots, also called nodes) joined by lines called edges. The vertices might be towns and the edges roads, or the vertices computers and the edges cables.

• The degree of a vertex is the number of edges that meet there. A loop counts 2.
• The sum of the degrees of all vertices is always twice the number of edges, because each edge has two ends.
• A weighted network has a number on each edge, such as a distance, time or cost.
• A directed network has arrows on its edges, showing one-way travel, such as one-way streets or water flowing downhill.
• A network is connected if you can get from any vertex to any other along the edges.

Drawing a network from a table

A table can show the weight of the direct link between each pair of vertices. Draw one vertex for each place, then one edge for each entry, labelled with its weight. A dash or blank means there is no direct link. The positions of the vertices don't matter; only the connections and weights do. Try to place vertices so edges don't cross, which makes the network easier to read.

The network below is used for both worked examples. It shows six farms, P to U, and the cost in thousands of dollars to lay a water pipe directly between each pair.

There are 8 edges, so the degrees add to 16. Check: P has degree 2, Q 3, R 3, S 3, T 3 and U 2, and $2+3+3+3+3+2=16$.

• A path is a route along edges that does not repeat a vertex.
• A cycle is a path that returns to its starting vertex.
• A tree is a connected network with no cycles. A tree with $n$ vertices has exactly $n-1$ edges.
• A spanning tree is a tree that includes every vertex of the network.
• A minimum spanning tree is the spanning tree with the smallest total weight.

Minimal connector problems ask for the cheapest way to connect every location: pipes to every farm, cables to every building, paths to every campsite. The answer is a minimum spanning tree.

You may use any correct method. Two common ones are below.

Kruskal's method

1. List the edges from smallest to largest weight.
2. Add the smallest edge that does not make a cycle.
3. Repeat until there are $n-1$ edges.

Prim's method

1. Start at any vertex.
2. Add the smallest edge joining a vertex already in the tree to a vertex not yet in the tree.
3. Repeat until every vertex is in the tree.

Worked example: connecting the farms

Find the minimum cost to connect all six farms in the table above.

Using Kruskal's method, take the edges in order of weight:

The first 5 edges already connect all 6 vertices, so the tree is complete. (You can stop as soon as you have $n-1$ edges.)

The minimum cost is $25 000. Check with Prim's method from P: P–Q (5), Q–R (4), R–T (3), T–S (6), S–U (7), the same five edges and the same total. If two edges have equal weight, either may be chosen; the total will be the same even if the tree looks different.

The shortest path between two vertices is the path with the smallest total weight. For small networks you can list the possible routes, but a systematic method is safer:

1. Label the starting vertex 0.
2. For each vertex next to a labelled vertex, write the total weight to reach it. If a vertex can be reached more than one way, keep the smaller total.
3. Fix the vertex with the smallest temporary label and repeat from there, until you reach the destination.
4. Trace back along the edges that gave each final label.

Worked example: shortest path from P to U

Using the same network, find the shortest path from P to U.

Start at P (0). From P, Q is 5 and R is 8. Fix Q at 5. From Q, R could be $5+4=9$, but 8 is smaller, so keep 8; S is $5+9=14$. Fix R at 8. From R, T is $8+3=11$. Fix T at 11. From T, S could be $11+6=17$, worse than 14, and U is $11+11=22$. Fix S at 14. From S, U becomes $14+7=21$, better than 22. So U is 21.

Tracing back, the shortest path is P–Q–S–U with total weight 21. Notice that the route P–R–T–U, also three edges, has weight 22. Check every route, not just the ones that look direct.

Shortest is not always best

A shortest path minimises one quantity, such as distance. It may not be the best path in real life because of traffic, tolls, road quality, speed limits or safety. The shortest path also does not have to lie inside a minimum spanning tree: the spanning tree minimises the total length of all connections, not the trip between two particular points. Here the shortest path P–Q–S–U uses Q–S, which is not in the minimum spanning tree; the route through the tree is 25.

• Counting edges instead of vertices when deciding when a spanning tree is finished. Stop at $n-1$ edges.
• Adding an edge that makes a cycle in Kruskal's method.
• In Prim's method, choosing the smallest edge anywhere instead of the smallest edge touching the tree.
• Giving the total weight of the whole network instead of the tree.
• Missing a route when finding the shortest path by inspection.
• Ignoring arrows in a directed network: you can only travel the way the arrow points.
• Forgetting units: "$25 000", not "25", when weights are in thousands of dollars.

• Show your method: list the edges in the order you chose them, or draw the tree. A correct total with no working may not earn full marks.
• When asked to draw a minimum spanning tree, include every vertex and label every weight.
• For shortest path questions, name the path (for example P–Q–S–U) as well as the total.
• An explain question about the shortest path not being the best wants a reason in context, such as a toll road or heavy traffic.

• Network flow (Year 12): directed weighted networks become flow networks with capacities, and cuts.
• Critical path analysis (Year 12): activity networks use directed edges, and finds the longest path through the network using a similar forward scan.
• Formulas and equations: the sum of degrees equals twice the number of edges is a simple formula you can check with.