9.02 Network representations

We can use networks to investigate any group of things that have connections between them. We’re going to look at how the capitals of each Australian state and territory are connected by the road network.

Now let’s draw the major roads connecting these cities together as undirected edges (because you can go back and forth along the roads!), and remove the state names.

Now we can remove the underlying map, and are left with a network, with the cities as vertices and the connecting roads as edges:

The network can be simplified further if we only care about how the cities are connected and not how far it is between the cities, as shown below.

Now we can easily see all kinds of information:

• You can’t drive straight from Canberra to Perth without going through at least one other capital city along the way.
• If you’re in Hobart you can drive around but you’re never going to any other capital city.
• You can drive directly from Melbourne to Sydney or you can go via Canberra.

And that's only the beginning! It’s not to scale anymore, but that’s ok - here we are only interested in whether cities are connected. Sometimes these sorts of rough networks are called mud maps, because they’re the kind of rough sketch that you can draw in the mud with a stick! Later on we will talk about ways to represent scale in networks.

You will see this kind of network all around you once you know how to look for it. For example, here is the London tube map as a network:

This next network is a completely different application. This is the family tree for King Charles II of Spain:

Note that the edges have arrows. These show who is the parent and who is the child, so this is a directed network. There are seven vertices that don’t have any arrows pointing at them (can you find them all?), and every other vertex has exactly two edges pointing at them, one for their mother and one for their father. Try drawing out your own family tree as a directed network!

There are also times when we can represent the same idea two different ways. In this example, a small part of a city, containing seven blocks, needs to be serviced by a garbage collector. The garbage truck needs to travel along each side of each block.

If we replace every intersection with a vertex, we can use directed edges to represent the roads. The garbage truck then needs to travel along every edge to complete the route:

Or, we could replace each side of every road with a vertex, and connect the vertices with directed edges if we can travel from one to the other without making a right turn. The garbage truck then needs to travel to each vertex to complete the route:

Which one do you like best? Which one do you think is the most useful?

 

Equivalent Representations

Sometimes two networks that appear different are just two different representations of the same network. A single network has many representations, because the position of the vertices and the lengths of the edges are free to be changed. Play around with these applets to see the range of representations a network (both directed and undirected) can have:

Created with Geogebra

Created with Geogebra

As you’re moving the vertices around, think about the kinds of changes we can make, and the kinds of changes we can’t. Here are the most important things you may have already noticed:

• If two vertices start connected they stay connected.
• In directed graphs, arrows don’t reverse direction.
• If two vertices don’t start connected they stay disconnected.
• We don’t add or delete vertices or edges.

As long as we stick with those rules, moving the vertices around just like in the applets, we are only changing the representation of the network, not the network itself.

Practice questions

Question 1

Question 2

Question 3