topic badge

9.02 Network representations

Lesson

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.

It’s hard to read the names of the cities, or even see where they are!

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.

We have added in three extra vertices (Katherine, Threeways, and Port Augusta) along the road from Adelaide to Darwin where it branches off to other cities. Without them we would have a single edge (road) connecting more than two vertices, which is not allowed.

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.

We have converted the map to a network!

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:

By only representing the information we care about (which stations are connected to which other stations and how), the map becomes easier to use.

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

People used to think this was a good idea.

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:

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

This diagram represents fibre optic cables connecting several cities.

  1. The edges are:

    The cities.

    A

    The roads.

    B

    The fibre optic cables.

    C

    The people who live in the cities.

    D

Question 2

Rabbits and squirrels both eat plants.

Foxes and hawks both eat rabbits and squirrels.

  1. Which of the following best represents this information?

    A

    B

    C

    D

    E

Question 3

An ice-cream shop offers a deal on Friday afternoons after school, selling two scoop flavour combinations for half price. The flavours to choose from in this deal are chocolate, lemon, raspberry, hazelnut, and vanilla.

Ellie has been trying each combination for several weeks. She has eaten chocolate with each other flavour, lemon with every flavour except vanilla, and has tried hazelnut and raspberry together.

  1. Draw the flavour combinations Ellie has already tried using a network.

  2. Which pairs of flavours has Ellie not tried yet?

Outcomes

MS2-12-8

solves problems using networks to model decision-making in practical problems

What is Mathspace

About Mathspace