Lesson 1 ~40 min Introduction to Networks · Path +90 XP

What a Network Is

A network throws away almost everything about a situation and keeps one thing: which items are connected to which. That looks like a severe loss of information, and it is exactly what makes networks useful.

Today's hook: A city train map shows no real distances, no real directions and no real shapes. Every line is straight, every angle is a multiple of $45$ degrees, and the whole thing is a lie about geography. It is also the single most useful map in the city.

0/5QUESTS

Think First

warm-up

Think of five people you know. Draw a dot for each one and join two dots whenever those two people have met. What does your picture tell you that a list of names could not?

Record your answer in your workbook.

The Big Idea

+5 XP to read

A network is a set of vertices, drawn as dots, and a set of edges, drawn as lines joining them. Where you place the dots and how you draw the lines carries no meaning at all. Only the joins are real.

$$\text{network} = \text{vertices} + \text{edges}$$

The words graph and network mean the same thing here, and so do vertex and node. Different fields settled on different words for identical objects, and you will meet all of them.

$\text{vertices} + \text{edges}$

This graph is not that graph

A graph in this topic has no axes and no scale. It has nothing to do with the graph of a function.

Position means nothing

Move a vertex anywhere you like. As long as the same pairs are joined, it is the same network.

Describe it by listing

Name the vertices, then list the edges as pairs. That description is complete on its own.

What You'll Master

objectives

Know

that a network, or graph, consists of vertices (also called nodes) joined by edges
that the terms graph and network are interchangeable, as are vertex and node
that a network can include a loop joining a vertex to itself, and more than one edge between the same pair of vertices

Understand

why the position of the vertices and the shape of the edges carry no information
why the same network can be drawn in many different-looking ways
why listing the vertices and the edges describes a network completely

Can Do

draw a network from a description of what is connected to what
describe a given network by listing its vertices and edges and counting each
decide whether two drawings represent the same network

Words You Need

vocabulary

NetworkA collection of objects joined by connections. Also called a graph.

VertexOne of the objects in a network, drawn as a dot. Also called a node. The plural is vertices.

EdgeA connection between two vertices, drawn as a line.

LoopAn edge joining a vertex to itself.

Multiple edgesTwo or more edges joining the same pair of vertices.

Two Words for One Object

+5 XP to read

Mathematicians call it a graph. Engineers, computer scientists and the people who build transport systems call it a network. They are the same object and the syllabus treats the two words as interchangeable.

The same doubling happens inside the object. The dots are called vertices by mathematicians and nodes by almost everyone else. Both are correct and both appear in exam questions.

One warning, and it is a real trap. The word graph has a completely different meaning in the rest of your mathematics course, where it means a curve drawn on a pair of axes. A graph in this topic has no axes, no scale and no coordinates. Nothing you know about the graph of $y = x^2$ transfers here.

This lesson uses network and graph interchangeably, deliberately, so that neither word comes as a surprise later.

What a Network Keeps

+5 XP to read

Take a map of five towns and the roads between them, and turn it into a network. A dot for each town, a line for each road.

Everything geographical disappears. The distance between towns is gone, because the length of a line means nothing. The direction is gone, because the position of a dot means nothing. The shape of the road is gone, because a curved line and a straight one say the same thing.

What survives is one fact per pair: is there a road, or not?

That sounds like a catastrophic loss. It is the point. Once everything else is stripped away, questions about connection become easy to see and easy to answer, and those are often the questions that matter. A commuter wants to know whether they can get from here to there and how many changes it takes, not how many kilometres the track covers.

The Same Network, Drawn Differently

+5 XP to read

Because position is meaningless, the same network can be drawn in enormously many ways.

Slide a vertex across the page and redraw its edges: same network. Curve an edge to avoid a crossing: same network. Rearrange four vertices from a square into a line: same network, as long as the same pairs are still joined.

So two pictures that look nothing alike may be the same graph, and this is not a rare curiosity. It is the normal situation, and Lesson 4 depends on it, because a graph that appears to have crossing edges may simply have been drawn badly.

The test is always the edge list. Two drawings represent the same network exactly when the same pairs of vertices are joined in both.

Loops and Repeated Edges

+5 XP to read

Two features are worth naming now, because a famous problem later in this area needs them.

A loop is an edge that starts and finishes at the same vertex. In a network of flights it would be a route from an airport back to itself, which sounds useless, but in a network of web pages it is an ordinary page linking to itself.

A multiple edge is a second, separate edge joining a pair of vertices that are already joined. Two different bridges over the same river between the same two banks are two edges, not one, because a person can walk over either.

Multiple edges are not an oddity to be tidied away. The Königsberg bridge problem in Lesson 10 has two pairs of banks joined by two bridges each, and collapsing those pairs into single edges would destroy the problem.

A graph with no loops and no multiple edges is called a simple graph, and most of the graphs in this area are simple.

Describing a Network in Writing

+5 XP to read

A picture is convenient, but a network can be written down completely without one.

List the vertices, then list the edges as pairs. For the network in the diagram above:

Vertices: $A$, $B$, $C$, $D$, $E$ — five of them.

Edges: $AB$, $AE$, $AD$, $BC$, $CD$, $DE$ — six of them.

That description contains everything. Anyone given the two lists can draw the network, and although their drawing will probably not look like yours, it will be the same network.

Write each edge once. The edge $AB$ and the edge $BA$ are the same edge seen from the two ends, so listing both would double the count. A useful habit is to write each pair in alphabetical order and then list the pairs in order too, which makes an omission easy to spot.

Watch Me Solve It · 3 examples

Watch Me Solve It · From a description to a network

+15 XP per step

PROBLEM

Five students are in a study group. Ana has worked with Ben and with Cara. Ben has worked with Cara and with Dev. Eli has worked with Dev only. Draw the network and state the number of vertices and edges.

1

Choose what the vertices represent

The objects being connected are the five students, so each student is a vertex: $A$, $B$, $C$, $D$, $E$.
2

Read off the edges

$AB, \ AC, \ BC, \ BD, \ DE$

One edge per stated working relationship. "Ana has worked with Ben" and "Ben has worked with Ana" would be the same edge, so each pair is listed once.
3

Draw it

Place the five dots anywhere convenient and join the listed pairs. Any arrangement is correct, so choose one that keeps the lines from crossing if you can.
4

Count

Five vertices and five edges. Note that the two counts being equal here is a coincidence of this example and carries no meaning.

Answer$5$ vertices and $5$ edges, with edge list $AB$, $AC$, $BC$, $BD$, $DE$

Watch Me Solve It · Are these the same network?

+15 XP per step

PROBLEM

One drawing has vertices $P$, $Q$, $R$, $S$ arranged in a square with edges $PQ$, $QR$, $RS$, $SP$ and $PR$. Another has the same four vertices in a row, joined by $PQ$, $PR$, $PS$, $QR$ and $RS$. Are they the same network?

1

Write both edge lists in a comparable form

$\text{first: } PQ, PR, QR, RS, SP$

$\text{second: } PQ, PR, PS, QR, RS$

Each pair written with its letters in alphabetical order, and the pairs then sorted, so the two lists can be compared line by line.
2

Compare

Note that $SP$ and $PS$ are the same edge written from the two ends. Rewriting the first list gives $PQ$, $PR$, $PS$, $QR$, $RS$, which is identical to the second.
3

Conclude

The same pairs are joined in both, so the two drawings represent the same network despite looking different. The square arrangement and the row arrangement carry no information.

AnswerYes, both have edge list $PQ$, $PR$, $PS$, $QR$, $RS$

Watch Me Solve It · A network with a loop and a repeated edge

+15 XP per step

PROBLEM

A network has vertices $X$, $Y$ and $Z$. There are two separate edges joining $X$ and $Y$, one edge joining $Y$ and $Z$, and a loop at $Z$. Describe it and count the edges.

1

List the edges, keeping repeats separate

$XY, \ XY, \ YZ, \ ZZ$

The two edges between $X$ and $Y$ are different edges and are both listed. The loop is written as the pair $ZZ$.
2

Count

Four edges and three vertices. Writing $XY$ once would give three edges and would describe a different network.
3

Note what kind of graph it is

It has both a loop and a multiple edge, so it is not a simple graph. Nothing is wrong with it; simple is a description, not a requirement.

Answer$3$ vertices and $4$ edges: $XY$, $XY$, $YZ$ and the loop $ZZ$

Brain Trainer · 5 problems

Brain Trainer · Count and describe

5 problems

Five items about reading and describing networks. Write edge lists with each pair in alphabetical order.

1 A network has edges $AB$, $AC$, $AD$, $BC$. How many edges does it have?

Count the listed pairs.$4$
2 A network has edges $AB$, $AC$, $AD$, $BC$. How many vertices does it have?

Collect the distinct letters appearing anywhere in the list.$4$
3 Is the edge $PQ$ different from the edge $QP$?

The two names describe the same connection from the two ends.No, they are the same edge
4 What is another word for a vertex?

Different fields use different words for the same object.A node
5 Two drawings of a network look completely different. What decides whether they are the same network?

Position and edge shape carry no information.Whether the same pairs are joined

Complete in your workbook.

Multiple Choice · 5 questions

MC1

The two words

+10 XP

In this topic, the words graph and network:

MC2

What carries information

+10 XP

In a network diagram, which of these carries information?

MC3

Counting a described network

+10 XP

A network has edge list $PQ$, $PR$, $QS$, $RS$, $ST$. It has:

MC4

Multiple edges

+10 XP

Two towns are joined by two separate bridges. In a network model of the region, this should be drawn as:

MC5

Recognising the same network

+10 XP

Two drawings both have vertices $A$, $B$, $C$ and $D$. The first has edges $AB$, $BC$, $CD$; the second has edges $AB$, $BC$, $CD$, $DA$. The drawings:

Short Answer · 3 questions

Build a network from a description

+15 XP

SHORT ANSWER

Six sensors are installed in a building. Sensor $1$ can communicate directly with sensors $2$ and $3$. Sensor $2$ can also reach sensor $4$. Sensor $3$ can also reach sensors $4$ and $5$. Sensor $6$ can reach sensor $5$ only. Give the edge list for the network, state the number of vertices and edges, and explain why the positions of the sensors in the building do not appear in your answer.

Write your working in your book.

Same or different

+15 XP

SHORT ANSWER

Drawing $1$ shows vertices $W$, $X$, $Y$, $Z$ at the corners of a square, with edges around the outside and one diagonal from $W$ to $Y$. Drawing $2$ shows the same four vertices in a row with edges $WX$, $WY$, $WZ$, $XY$, $YZ$. Determine whether the two drawings show the same network, showing your comparison clearly.

Write your working in your book.

Model a situation twice

+15 XP

SHORT ANSWER

A small airline flies between four cities: Perth, Darwin, Cairns and Sydney. There are two daily flights between Perth and Sydney, one between Darwin and Cairns, one between Cairns and Sydney, and one between Darwin and Perth. Draw the network as a description, count the edges, and explain why a model that recorded only whether two cities are connected would answer a different question.

Write your working in your book.

Stretch Challenge · How many networks are there on four vertices?

+25 XP

CHALLENGE

Consider simple networks on four labelled vertices $A$, $B$, $C$ and $D$, with no loops and no multiple edges. Count how many different such networks exist, explaining your reasoning. Then work out the general answer for $n$ labelled vertices, and comment on how quickly it grows.

Quick Review

recap

Vertices and edges, and nothing else

A network is a set of vertices joined by edges. Position, length, direction and curvature carry no information, so only the list of joined pairs is real.

Graph and network are the same word

So are vertex and node. But a graph here has no axes and no scale, and shares nothing but its name with the graph of a function.

One network, many pictures

Two drawings represent the same network exactly when the same pairs of vertices are joined. Put every pair into alphabetical order before comparing the lists.

Loops and repeats are allowed

A loop joins a vertex to itself and a multiple edge is a second connection between the same pair. Both are needed for the Königsberg problem later.

Your Badges

0 of 6

First Steps

3-Day Streak

3 in a Row

Lesson Ace

Stretch Seeker

Daily Warrior

Mark lesson as complete

Tick when you've finished Learn, Practice and the Stretch. Earns +90 XP and +25 coins.

Introduction to Networks (Path) index · Maths subject page