Weighted and directed networks

Weights on edges, one-way edges, turning a table or a map into a network diagram, and reading a network back into a table.

A plain network tells you that two places are linked. Real decisions usually need more: how far, how long, how much, and whether you can go both ways. Weights and arrows add exactly that.

Weighted networks

A weighted network has a number on each edge, called its weight. The weight might be a distance in kilometres, a travel time in minutes, a cost in dollars or a pipe length in metres. The question tells you which.

The weight is not the length of the line on the page. A network diagram is about connections, so a $30$ km road may be drawn shorter than a $14$ km one. Always read the number, never the ruler.

From a table to a network

Networks are often stored as a table. Each row and column is a vertex, and the cell where they meet holds the weight of the edge between them. A dash (or a blank) means there is no direct edge.

km	Pe	Bl	CH	Pa	Li
Pe	–	17	–	–	30
Bl	17	–	14	14	22
CH	–	14	–	11	–
Pa	–	14	11	–	22
Li	30	22	–	22	–

Example 1●

The table shows approximate road distances between five western Sydney centres: Penrith (Pe), Blacktown (Bl), Castle Hill (CH), Parramatta (Pa) and Liverpool (Li). Draw the network and find the total length of all the roads.

Vertices: Pe, Bl, CH, Pa, Li

Draw one vertex for each row. Spread them out roughly like a map so edges don't cross more than they need to.

Edges: Pe–Bl $17$, Pe–Li $30$, Bl–CH $14$, Bl–Pa $14$, Bl–Li $22$, CH–Pa $11$, Pa–Li $22$

The table is symmetric (row Bl, column Pe is the same as row Pe, column Bl), so each road appears twice. Only read the cells above the diagonal.

Total $= 17 + 30 + 14 + 14 + 22 + 11 + 22 = 130$ km

Add each road once.

The network from Example 1. Weights are road distances in kilometres.

Directed networks

A directed network has arrows on its edges. You can only travel along an edge in the direction of its arrow. One-way streets, water flowing downhill, a bus loop and "follows" on social media are all directed. Two places can have arrows both ways with different weights. Going uphill takes longer than coming down.

In a table for a directed network, the row is where you start and the column is where you finish. The table is usually not symmetric.

One-way streets around a shopping centre. Weights are driving times in minutes.

Example 2●●

Using the one-way street network above, find the quickest time (a) from A to D (b) from D to A.

From A: A → B ($3$ min)

Follow the arrows out of A. The only way out is A to B.

A → B → D $= 3 + 3 = 6$ min; A → B → C → D $= 3 + 4 + 2 = 9$ min

From B you can go straight to D, or via C. Compare them.

(a) $6$ minutes, via B

Choose the smaller.

D → E → A $= 5 + 2 = 7$ min

From D the arrows go to E or to B. From B there is no arrow back to A, so the B branch is a dead end for this trip.

(b) $7$ minutes, via E

Different routes, different times. Direction matters.

From a map to a network

To turn a map into a network, keep the connections and throw away everything else: the shape of the roads, the scale and the compass directions. Ask three questions:

What are the vertices? (towns, rooms, intersections)
What counts as an edge? (a direct road, a door, a cable)
What is the weight, and is any edge one-way?

Two different-looking diagrams can be the same network. If they have the same vertices joined by the same edges with the same weights, they are equivalent, even if one is stretched or twisted.

InteractiveNetworks and their tables

Try this

In Explore, tap a road and find both of its cells in the table. Then switch to one-way streets. Why does B → D have a different number from D → B?

Switch to Build from the table and draw every edge for both networks. Use Check my network to see what you missed.

Your turn

In the one-way network, what is the quickest time from E to C?

Show the working

From E the arrows go to A ($2$) or B ($6$). E → A → B → C $= 2 + 3 + 4 = 9$ min. E → B → C $= 6 + 4 = 10$ min. Quickest: $9$ minutes via A and B.

Flashcards

Weight

A number on an edge: distance, time or cost

Directed network

Edges have arrows and can only be travelled one way

Directed network table

Row = start, column = finish

Practice

On a network diagram, the length of an edge as drawn tells you:
Using the table of western Sydney distances, how far is it from Castle Hill to Parramatta?
How many edges in the western Sydney network meet at Blacktown?
A table for a directed network is not symmetric. This is because:
Every number in a symmetric distance table (both sides of the diagonal) adds up to $520$ km. What is the total length of the roads?
In the one-way network, what is the quickest time from B to A, in minutes?
Which situation is best modelled by a directed network?
Exam style: In the one-way network, how many arrows leave vertex B?
Exam style: A delivery van drives Penrith → Blacktown → Parramatta → Castle Hill → Blacktown on the western Sydney network. How far does it travel?

km	Pe	Bl	CH	Pa	Li
Pe	–	17	–	–	30
Bl	17	–	14	14	22
CH	–	14	–	11	–
Pa	–	14	11	–	22
Li	30	22	–	22	–

km	Pe	Bl	CH	Pa	Li
Pe	–	17	–	–	30
Bl	17	–	14	14	22
CH	–	14	–	11	–
Pa	–	14	11	–	22
Li	30	22	–	22	–

km	Pe	Bl	CH	Pa	Li
Pe	–	17	–	–	30
Bl	17	–	14	14	22
CH	–	14	–	11	–
Pa	–	14	11	–	22
Li	30	22	–	22	–