AN1–AN4 - Graphs and networks as models | OCR A-Level Further Mathematics B (MEI)

Replace a complicated setting by points, connections and, when needed, weights. AN1 supplies the graph language, AN2 models relationships and legal moves, and AN3 and AN4 turn those graphs into networks that describe distances, costs or capacities.

Read vertices, arcs and node orders

At a meeting, could exactly three people each shake hands an odd number of times, while everybody else shakes hands an even number of times? A graph lets us answer without listing every possible meeting.

You already know

A model retains the features needed for a question and leaves out irrelevant detail. A set lists distinct objects; an unordered pair does not distinguish $AB$ from $BA$ .

Represent each person by a point and each handshake by a connection. The drawing's shape and the lengths of its lines do not matter unless the model assigns meaning to them. Lines crossing on the page do not create a new junction unless a vertex is marked there.

Graph language

A graph has vertices, also called nodes, joined by arcs, also called edges. The order of a node, or degree, is the number of arc ends incident with it. In an undirected graph a loop contributes two ends at its node; parallel arcs are counted separately.

A walk follows consecutive arcs and may revisit vertices. A path has no repeated vertices. A cycle is a closed path, with its start repeated only at the end. These words describe connections, not how straight the drawing looks.

Each undirected arc contributes two arc ends. Hence the sum of node orders is twice the number of arcs. The even orders contribute an even sum, so the odd orders must also add to an even number: there must be an even number of odd-order nodes.

Counting arc ends

For an undirected graph with $m$ arcs and node orders $d_1,\ldots,d_n$ ,

\sum_{i=1}^{n}d_i=2m

Consequently, the number of nodes of odd order is even.

Not in the formula booklet: learn it.

Count from the arc list if a drawing is crowded. Each listed arc increases the order of both its endpoints by one.

Worked example 1: count the node orders

Question. A graph has vertices $A,B,C,D,E$ and arcs $AB,AC,BC,CD,DE$ . Find all node orders and check the arc-end result.

Plan. Count incidences at each vertex, then add them.

\begin{aligned} d_A&=2,\quad d_B=2,\quad d_C=3,\quad d_D=2,\quad d_E=1 &&\text{count incident arcs}\\ \sum d_i&=2+2+3+2+1=10 &&\text{sum orders}\\ 2m&=2(5)=10 &&\text{five arcs} \end{aligned}

Why this step? Counting each arc at both ends prevents confusing the number of arcs with the sum of the orders.

Answer. The orders are $2,2,3,2,1$ , and their sum is twice the five arcs.

Check. Exactly two nodes, $C,E$ , have odd order.

Add only the arc $AE$ . Exactly its two endpoints change order.

Worked example 2: add one connection

Question. Add $AE$ to the preceding graph. Find the new orders and identify the odd-order nodes.

Plan. Increase the two endpoint orders by one and leave the others unchanged.

\begin{aligned} d_A&=3,\quad d_B=2,\quad d_C=3,\quad d_D=2,\quad d_E=2 &&\text{only }A,E\text{ change}\\ \sum d_i&=3+2+3+2+2=12 &&\text{new sum}\\ 2m&=2(6)=12 &&\text{one more arc} \end{aligned}

Why this step? Adding one arc changes the parity of two orders, so it cannot create an odd number of odd-order nodes.

Answer. The orders are $3,2,3,2,2$ ; the odd-order nodes are $A,C$ .

Check. The order sum rises by two, exactly as the arc-end count predicts.

The handshake puzzle is already settled: three odd-order people is impossible, because the count of odd-order nodes must be even.

Watch out

Wrong: $\sum d_i=m$ . Each undirected arc contributes an end at both endpoints, including two ends for a loop. Correct: $\sum d_i=2m$ ; after adding $AE$ , the six arcs give order sum $12$ .

Count both ends of each arc in the next graph.

Distinguish the main graph types

A graph can have several descriptions at once. A tree is connected; it can also be bipartite. A complete graph has every permitted pair joined, rather than merely enough connections to reach every vertex.

Simple and directed graphs

A simple graph has no loops and no more than one arc joining any pair of distinct vertices. A digraph has directed arcs, so an arrow from $A$ to $B$ permits that direction and does not automatically permit $B$ to $A$ .

The following descriptions tell you which connections are present and how they fit together.

Term	Meaning
Connected	A path joins every pair of vertices in an undirected graph.
Complete	Every pair of distinct vertices is joined in a simple graph.
Tree	A connected undirected graph with no cycles.
Bipartite	The vertices can be split into two disjoint sets so every arc joins different sets.

In a bipartite graph, the sets need not have equal sizes, and not every possible cross-set arc has to be present. A triangle cannot be bipartite: alternating sets around its three arcs would force the last arc to join two vertices in the same set.

[DIAGRAM: asset_name: Four graph types; asset_slug: graph_types_gallery; caption: Graph types describe connections and directions, while a crossing without a marked vertex adds no node; description: Four labelled panels show a complete simple graph on four vertices with crossing diagonals but no central vertex, a tree on five vertices, a connected bipartite graph with two visibly separated vertex sets, and a digraph with arrowed arcs. Every vertex is a clearly drawn circle.]
Graph types describe connections and directions, while a crossing without a marked vertex adds no node

For a complete simple graph on $n$ vertices, every vertex has order $n-1$ , so there are $n(n-1)/2$ arcs. A tree on $n$ vertices has $n-1$ arcs: starting from one vertex, adding each new vertex by one connecting arc builds a connected graph without a cycle. These counting results are not in the formula booklet.

Key idea

Connected means every vertex is reachable; complete means every pair is directly joined. A tree connects all vertices while containing no cycle.

Use the definitions rather than the drawing's appearance.

Model eligibility with a bipartite graph

For an allocation problem, one vertex set can represent people and the other tasks. Draw an arc precisely when that person is eligible for that task. This records possibilities, not an allocation already made.

Matching

A matching is a selection of arcs with no shared endpoints. In a people-to-tasks graph, it assigns each selected person to one distinct task. A complete assignment of all people needs one selected arc at every person vertex.

For a small graph, an assignment can be found or ruled out by inspection. Do not assume that several arcs at a person mean several simultaneous assignments are allowed.

[DIAGRAM: asset_name: Eligibility and a matching bottleneck; asset_slug: graph_matching_models; caption: Removing one eligibility arc leaves two people competing for the same sole task; description: Two bipartite graphs have people A, B, C on the left and tasks P, Q, R on the right. The first has arcs AP, AQ, BQ, CQ, CR and highlights matching AP, BQ, CR. The second removes AP, leaving task P isolated, and highlights the size-two matching AQ, CR. Arcs BQ and CQ show the competition for task Q.]
Removing one eligibility arc leaves two people competing for the same sole task

Worked example 3: make a complete assignment

Question. People $A,B,C$ can do tasks as follows: $A$ can do $P,Q$ ; $B$ only $Q$ ; $C$ can do $Q,R$ . Model the possibilities and give a complete assignment.

Plan. Use people and tasks as the two vertex sets, then satisfy the most restricted person first.

\begin{aligned} \text{arcs}&=\{AP,AQ,BQ,CQ,CR\} &&\text{eligibility only}\\ B&\longmapsto Q &&\text{only option for }B\\ A&\longmapsto P,\qquad C\longmapsto R &&\text{distinct remaining tasks} \end{aligned}

Why this step? Allocating $Q$ casually to $A$ would leave $B$ without an available task, despite a complete assignment existing.

Answer. The bipartite graph has the five listed arcs; $AP,BQ,CR$ is a complete matching.

Check. Every chosen arc is permitted and no chosen arcs share an endpoint.

Remove only the eligibility arc $AP$ . Two people now compete for one possible task.

Worked example 4: explain why a complete assignment fails

Question. With $AP$ removed, determine whether all three people can be assigned distinct tasks.

Plan. Inspect the available tasks for $A$ and $B$ , and exhibit the largest possible assignment.

\begin{aligned} A&\longmapsto Q\text{ only},\qquad B\longmapsto Q\text{ only} &&\text{restricted pair}\\ \text{at most one of }A,B&\text{ can be assigned} &&\text{task }Q\text{ used once}\\ \{AQ,CR\}&\text{ is a matching of size }2 &&\text{attains the upper limit} \end{aligned}

Why this step? Counting three people and three tasks is insufficient: the pattern of eligibility can prevent a full assignment.

Answer. A complete assignment is impossible; the largest matching has size $2$ .

Check. The exhibited matching uses two distinct people and two distinct tasks.

Adding costs to these eligibility arcs would turn the graph into an allocation network. Eligibility tells you what is allowed; a weight could tell you how expensive each allowed assignment is.

Watch out

Wrong: $\{AQ,BQ,CR\}$ is a complete matching. The arcs $AQ$ and $BQ$ share task $Q$ , so it would be assigned twice. Correct in the original graph: $\{AP,BQ,CR\}$ , whose endpoints are all distinct.

Check both sets of endpoints when forming the next assignment.

Model legal moves with a state graph

Vertices need not represent physical places. They can represent whole states of a puzzle, with an arc for a permitted move. Then a solution is a path from the initial state to the target state.

A rower must ferry a goat and a cabbage across a river. The boat carries the rower and at most one item; the rower may cross alone. The goat and cabbage cannot be left together on a bank without the rower.

Write a state as $(f,g,c)$ , with $0$ meaning the left bank and $1$ the right. Keep only safe states. An arc must change the rower's bank and may change the bank of at most one item that began beside the rower.

[DIAGRAM: asset_name: A river-crossing state graph; asset_slug: graph_river_states; caption: Every edge is one legal crossing; a three-edge path transfers both items safely; description: Six vertices are labelled 000, 101, 001, 111, 010 and 110 around a cycle. Consecutive edges represent legal crossings for a rower, goat and cabbage when the rower can carry one item or travel alone. The path 000 to 110 to 010 to 111 is highlighted, with move labels goat across, rower returns alone, cabbage across. The excluded unsafe states 011 and 100 are stated below the diagram.]
Every edge is one legal crossing

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Core Pure

Mechanics (Major and Minor)

Statistics (Major and Minor)

Modelling with Algorithms

Numerical Methods

Extra Pure

Further Pure with Technology

AN1–AN4 - Graphs and networks as models

Read vertices, arcs and node orders

Distinguish the main graph types

Model eligibility with a bipartite graph

Model legal moves with a state graph

Continue this lesson.

Learn faster with Nova