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 e=n(n−1)2e = \frac{n(n-1)}{2}.
  • 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 nn vertices is written KnK_n. Each of its vertices has degree n−1n - 1.

In a complete graph, every vertex is joined to every other vertex.

Key idea

The number of edges in a complete graph

e=n(n−1)2e = \frac{n(n-1)}{2}

Each of the nn vertices has degree n−1n - 1, so the degree total is n(n−1)n(n-1); halving it gives the number of edges. In a round-robin competition every team plays every other team once, so the draw is KnK_n 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.

Interactive

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

  1. Decide what the vertices are

    Usually the places, people or teams.

  2. 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.

  3. 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.

  4. Draw it clearly

    Place the vertices so that edges cross as little as possible, and label every vertex and weight.

  5. 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

  • Simple familiar

The table lists the walking tracks in a national park and their lengths.

Track betweenLength (km)
Ranger station and Lookout2.5
Ranger station and Waterfall4.0
Ranger station and Creek camp3.5
Lookout and Waterfall2.0
Waterfall and Creek camp3.0
Waterfall and Bush camp4.5
Creek camp and Bush camp2.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?

5 steps

Try it yourself first, then check the working one step at a time.

Method

  1. One vertex for each place, person or intersection.

  2. One edge for each connection: arrows only if the connection is one-way, and weights if a number is attached.

  3. 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

  • Simple familiar

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?

4 steps

Try it yourself first, then check the working one step at a time.

Method

  1. A round-robin of nn teams is modelled by the complete graph KnK_n.

  2. Number of games =n(n−1)2= \frac{n(n-1)}{2}.

  3. The results digraph has one arrow per game, from the winner to the loser.

Watch out for

  • 6×5=306 \times 5 = 30 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?

Choose one answer

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 KnK_n joins every pair of its nn vertices and has n(n−1)2\frac{n(n-1)}{2} edges — also the number of games in a round-robin of nn 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.

Lesson 2 of 80% read

Save your progress with a free account