Lesson 2 of 8 · 18 min
Types of graphs and network diagrams
Recognise complete, bipartite, directed and weighted graphs, and construct a network diagram for a real situation such as walking tracks, a social network, one-way streets or a round-robin.
What you will be able to do
- Recognise complete graphs and count their edges with .
- Recognise bipartite graphs, directed graphs (digraphs), weighted graphs and networks.
- Construct a network diagram to represent a practical situation.
- Choose the kind of graph that suits a situation.
Graphs model all sorts of situations: tracks between camp sites in a national park, a social network, a town centre where some streets are one-way, the results of a round-robin competition. Each situation needs a slightly different kind of graph.
This lesson names the kinds of graph, then uses them to draw networks for real situations.
Definition
Complete graph
A complete graph is a simple graph in which every pair of vertices is joined by exactly one edge. The complete graph on vertices is written . Each of its vertices has degree .
In a complete graph, every vertex is joined to every other vertex.
Key idea
The number of edges in a complete graph
Each of the vertices has degree , so the degree total is ; halving it gives the number of edges. In a round-robin competition every team plays every other team once, so the draw is and this is also the number of games.
Eight teams play a round-robin, each team playing every other team once. How many games are played?
Definition
Bipartite graph
In a bipartite graph the vertices split into two groups, and every edge joins a vertex in one group to a vertex in the other. No edge joins two vertices of the same group. Bipartite graphs model pairings: students and the sports they play, workers and the jobs they can do.
Edges only run between the two groups, from a student to a sport.
Definition
Directed graph (digraph)
In a directed graph, or digraph, each edge has a direction, shown by an arrow. Use a digraph when a connection works only one way: a one-way street, a person who follows someone on social media without being followed back, or a game result — an arrow from the winner to the loser.
Results of a four-team round-robin. Each arrow points from the winner to the loser.
In the round-robin digraph, how many games did Bardon win?
Definition
Weighted graphs and networks
A weighted graph has a number, called a weight, on each edge: a distance, a travel time, a cost or a capacity. A graph or weighted graph that models a real situation is called a network — a road network, a rail network, a network of walking tracks.
The weights are track lengths in kilometres. Which place has the highest degree, and what is the total length of all the tracks?
Constructing a network diagram
Decide what the vertices are
Usually the places, people or teams.
Decide what an edge means
A road, a track, a friendship, a game, a cable. Draw one edge for each connection — two edges if there are two separate connections.
Decide on arrows and weights
Arrows if a connection goes only one way, or records who beat whom. Weights if a number belongs to each connection.
Draw it clearly
Place the vertices so that edges cross as little as possible, and label every vertex and weight.
Check it
Count the edges against the information given, and check that the degree total is twice the number of edges.
Worked example
Drawing a network of walking tracks
The table lists the walking tracks in a national park and their lengths.
| Track between | Length (km) |
|---|---|
| Ranger station and Lookout | 2.5 |
| Ranger station and Waterfall | 4.0 |
| Ranger station and Creek camp | 3.5 |
| Lookout and Waterfall | 2.0 |
| Waterfall and Creek camp | 3.0 |
| Waterfall and Bush camp | 4.5 |
| Creek camp and Bush camp | 2.5 |
(a) Construct a network diagram to represent the tracks.
(b) Which place has the highest degree, and what does that degree tell a walker?
(c) What is the total length of the tracks?
Step 1: Choose the vertices
One vertex for each place — Ranger station, Lookout, Waterfall, Creek camp and Bush camp. Spread them out so the edges will not crowd each other.
Step 2: Draw one edge for each track
The seven rows give seven edges. Write each length on its edge, which makes the diagram a weighted graph, or network.
The tracks can be walked in either direction, so the edges have no arrows.
Step 3: Check the diagram
Degrees: Ranger station 3, Lookout 2, Waterfall 4, Creek camp 3, Bush camp 2. The total is . ✓
If the degree total is not twice the number of rows, an edge has been missed or drawn twice.
Step 4: Read off the highest degree
The Waterfall has degree 4. Four tracks meet there, so from the Waterfall a walker can set off in four directions.
Step 5: Add the weights
km
Try it yourself first, then check the working one step at a time.
Answer
(a) Five vertices, one for each place, joined by seven edges, one for each track, each labelled with its length. (b) The Waterfall, with degree 4: four tracks meet there. (c) 22 km.
Method
One vertex for each place, person or intersection.
One edge for each connection: arrows only if the connection is one-way, and weights if a number is attached.
Check: the degree total is twice the number of connections.
Watch out for
Leaving the weights off, which throws away the information the network is for.
The finished network for the worked example. Each edge is a track, labelled with its length in kilometres.
Worked example
A round-robin competition as a complete graph
Six schools — Ashgrove, Bardon, Chermside, Durack, Everton Park and Ferny Grove — enter a futsal round-robin, in which every school plays every other school once.
(a) Each school is a vertex and each game is an edge. What kind of graph models the draw?
(b) How many games are played?
(c) The results are recorded as a digraph with an arrow from the winner to the loser. There are no draws. How many arrows does the digraph have, and what is the total number of wins?
Step 1: Identify the graph
Every pair of schools is joined by exactly one game, and no school plays itself. That is the complete graph on 6 vertices, .
Step 2: Count the games from each school's point of view
Each school plays the other 5, so every vertex has degree 5 and the degree total is .
Step 3: Halve the total
Each game was counted twice, once by each school, so there are games.
This is the complete-graph formula with .
Step 4: Turn the games into arrows
Every game has exactly one winner, so each of the 15 edges becomes one arrow from winner to loser: 15 arrows. Each arrow leaving a vertex is one win, so the wins add to 15.
Try it yourself first, then check the working one step at a time.
Answer
(a) The complete graph . (b) 15 games. (c) 15 arrows, and the wins add to 15.
Method
A round-robin of teams is modelled by the complete graph .
Number of games .
The results digraph has one arrow per game, from the winner to the loser.
Watch out for
counts every game twice. Halve it.
Putting arrows at both ends of an edge: each game has one winner, so it gets one arrow.
In a social network, each person is a vertex. A mutual connection, such as being friends, is an edge with no arrow. A connection that can be one-sided, such as following someone online, is an arrow — and two people who follow each other get a pair of opposite arrows.
Ali follows Bea and Cal. Bea follows Ali. Dee follows Bea and Cal. Cal follows nobody. In the digraph of who follows whom, how many arrows are there?
A council map shows which streets in a town centre are one-way. Which kind of graph best models the streets, with intersections as vertices?
Common mistake
Arrows that say the wrong thing
Draw arrows only for one-way connections. A two-way street is an edge with no arrow, or a pair of opposite arrows — never a single arrow. In a round-robin results digraph, each game gets exactly one arrow, from the winner to the loser.
Summary
A complete graph joins every pair of its vertices and has edges — also the number of games in a round-robin of teams.
A bipartite graph has two groups of vertices, with edges only between the groups.
A directed graph (digraph) uses arrows for one-way connections: one-way streets, followers, game results.
A weighted graph has a number on each edge. A graph that models a real situation is a network.
To construct a network diagram: choose the vertices, draw one edge per connection, add arrows and weights where needed, then check the degree total.
Finished the lesson?
Try the 4 quick checks above and the lesson completes itself, or mark it complete now.