A Level

A Level maths examples categorised by branch of mathematics.

Maths that is generally first seen at A Level (post-16) in the UK.

Categories

    [categories title_li=0 child_of=6]

Posts

Logarithm Laws

If you are studying logarithms it is reasonably safe to assume that you’re already reasonably familiar with index rules; those shortcuts that allow for swift calculation of exponents when dealing with equal bases. The log laws are really just a rearrangement of these.

First, multiplying. Since when you multiply terms with the same base you add the indices, the log of a product is equal to the sum of the logs of the factors of that product. This is best demonstrated starting with the index rule and working through an example.

\begin {aligned}a^m \times a^n &= a^{m+n} \\ 8 \times 16 &= 128 \\2^3 \times 2^4 &= 2^7 \\ \log_2{8} + \log_2{16} &= \log_2{128} \\ \log_a{m} + \log_a{n} &= \log_a{mn}\end{aligned}Index / log law for multiplication / addition

Second, division. As the inverse of multiplication this one is now hopefully easy to spot: subtracting the parts. The log of a quotient is equal to the difference between the logs of the dividend and the divisor (numerator and denominator).

\begin {aligned}\frac{a^m}{a^n} &= a^{m-n} \\ \log{\frac{m}{n}}&= \log{m} - \log{n}\end{aligned}Index / log law for division / subtraction

Using this rule for division it follows that we should be able to find the value of a logarithm of 1. As any value divided by itself is 1, choosing a value expressed in index form allows us to apply the previous rule.

\begin {aligned}\frac{a^b}{a^b} &= 1 \\ a^{b-b} &= 1 \\ \log_a{1} &= b-b \\ \log_a{1} &= 0 \end {aligned}The log of 1 in any base is 0

Terms with indices raised to a power are an extension of the multiplication of indices already described. This approach can be applied to the addition of logarithms:

\begin {aligned}(a^m)^n &= a^m \times a^m \times \ldots \times a^m \\ \log_a{m^n} &= \log_a{m} + \log_a{m} + \ldots + \log_a{m} \\ \log_a{m^n} &= n \log_a{m}\end {aligned}Powers in logarithms

Differentiation – Introduction

Differentiation is the process we use to find an expression for the rate of change of a function. This is most easily explained graphically.

[geogebra-activity material='wmpmrhzb' width=600 shiftdragzoom='false']

In the graphs above, the green curve shows a function with a point moving along it. The tangent at that (moving) point is shown. The blue curve shows the value of the gradient of that tangent as x changes.

By drawing tangents to a curve we can estimate the gradient at any point but this is time consuming for more than a couple of points, requires a well-drawn graph, and is inaccurate. Differentiation allows us to find a function that describes all of these tangents without having to draw them.

The result of differentiating is the derivative of the function. Because a derivative describes how one value is affected by a change in a variable we say that we find the derivative with respect to that variable. Differentiating the function that gives the green curve above results in the function that gives the blue curve. The blue curve is the gradient function of the green one.

For a graph of y against x the gradient is the derivative of y with respect to x, this is written as \frac{\mathrm{d}y}{\mathrm{d}x}. Using function notation, \frac{\mathrm{d}y}{\mathrm{d}x}=f'(x).

There are numerous applications of derivatives. One of the most easily understood is velocity. Velocity is the rate of change of displacement with respect to time, often written v=\frac{\mathrm{d}x}{\mathrm{d}t}=\dot{x}.

Graphs

There are two types of graph that exist in mathematics. The first form is the one with which most people are familiar; a representation of a relationship between variables (often x and y) expressed as a line or curve (as in figure 1). An example of the second form of graph is shown in figure 2. This second form represents relationships that are found in discrete mathematics. In discrete mathematics the set of elements is countable and has a one-to-one correspondence with either the set of positive integers, or a subset of the positive integers.

Figure 1: a plot of the function y = (x - 2)² + 1. A function graph as found in continuous mathematics.
Figure 1: a plot of the function y = (x – 2)² + 1. A function graph as found in continuous mathematics.

Your browser does not support the canvas element.
Figure 2: a graph showing relationships between vertices. A graph from discrete mathematics. Graphs of the sort that we find in discrete mathematics are useful for solving problems concerning configurations and relationships.

Graph Definitions

Graph
A visual representation of a set of vertices (nodes). Each member of X is represented as a vertex. Connections are represented by edges (arcs).
Vertex / Node
A point representing a member of the set.
Edge / Arc
A link between vertices. An edge must have a vertex at each end.
Loop
An edge with the same vertex at each end.
The basic parts of a graph: edges, vertices, and a loop.
The basic parts of a graph: edges, vertices, and a loop.
Degree (order) of a vertex
The number of edges meeting at the vertex.
Simple graph
Contains no loops and has no more than one edge between any pair of vertices.
Walk
Sequence of edges. The end of each edge (except the last) is the start of the next.
Trail
A walk with no repeated edges.
Path
A trail in which no vertex is repeated.
Cycle
A closed path. The end of the last edge joins the start of the first.
Hamiltonian Cycle
A cycle that visits every vertex
Connected
There is a path between every pair of vertices in a connected graph.
Tree
Simple connected graph with no cycles.
Digraph (directed graph)
Graph with at least one edge having a direction.
Complete graph
A simple graph with each pair of vertices connected by an edge.
Eulerian
An Eulerian graph is connected and the degree of every vertex is even.
Incidence Matrix
Matrix representation of a graph. Elements of the matrix show the number of edges connecting the vertices represented by the row and column of the matrix.
Isomorphic
Graphs are isomorphic if one can be deformed to make the other. The vertices can be moved and the edges straightened or bent to do this.
Planar graph
A graph that can be drawn such that no edges cross.
Bipartite graph (bigraph)
A graph joining two sets. Every edge starts in one set and ends in the other.

Order, Size and Degree

Graphs have an order equal to the number of vertices that they contain.

The size of a graph is equal to the number of edges.

Complete graphs have the maximum size for a given order, without loops. For a graph of order n the maximum size will be \dfrac {n}{2}\left( n-1\right).

The degree of a vertex is equal to the number of edges that enter or leave it.

The maximum vertex degree for a given order, n, of graph without loops, is n-1.

The sum of vertex degrees will be double the size of the graph as each edge has two ends. Consequently a graph cannot have an odd number of vertices with an odd degree.

Complete Graphs

A complete graph with 6 vertices.

A complete graph is a form of simple graph. Every pair of vertices must be connected by a single edge. Figure 1 shows an example of a complete graph for a set with 6 elements.

A complete graph with n vertices is given the notation K_n.

We may need to find out the total number of edges in this graph.

  1. List all the possible pairs of vertices :
    • AB, AC, AD, AE, AF
    • BC, BD, BE, BF
    • CD, CE, CF
    • DE, DF
    • EF
  2. Count the number of pairs.
  3. Each pair of vertices must have an edge connecting them so the number of pairs is equal to the number of edges.

Of course, with a set that has many more than 6 elements, you probably wouldn’t want to list all possible pairs. Thankfully there is another, easier way to work out the number of edges in a complete graph. We could calculate the (n-1)th triangle number. \sum_{r=1}^{n-1} r. Remember the binomial coefficient (you might have seen this in your Pure or Statistics lessons).

{^n}C_r = \left( \!\! \begin{array}{c} n \\ r \end{array} \!\! \right) = \frac{\displaystyle n!}{\displaystyle r!(n-r)!}

This binomial coefficient will give you the number of combinations of r elements from a set of n members.

For this example n=6 and p=2.

\begin{aligned}{^6}C_2 &= \frac{\displaystyle 6!}{\displaystyle 2!(6-2)!} \\ &= {\displaystyle \frac { 6 \times 5 \times 4 \times 3 \times 2 \times 1}{ 2 \times 1 \times 4 \times 3 \times 2 \times 1}} \\ &= {\displaystyle \frac { 6 \times 5}{2} } \\ &= 15 \end{aligned}

By using either the formula above, or by counting pairs, we see that the total number of possible pairs in the set is 15. This is the same as the total number of edges in the complete graph for that set.

Eulerian Graphs

An Eulerian graph is a connected graph in which each vertex has even order. This means that it is completely traversable without having to use any edge more than once. It is possible to follow an Eulerian cycle starting from any vertex, visiting every other vertex, using all arcs, and returning to the start point without ever repeating an edge. Each vertex will be visited a number of times equal to half its order.

Figure 1. An Eulerian graph with 6 vertices.
Figure 1. An Eulerian graph with 6 vertices.

Semi-Eulerian Graphs

A semi-Eulerian graph has two vertices of odd order. An Eulerian cycle is not possible, but it is semi-traversable. You can draw the graph starting at one of the vertices with odd order and ending at the other including all of the edges as you go round, without removing your pencil from the paper.

Networks

A network is a graph in which one or more edges is assigned a number, called its weight.

Perhaps the easiest way to think of this is to imagine a graph showing the main roads between towns. The number on the edges would normally represent the distance that you have to travel along that road. Figure 1 shows such a network.

Figure 1. Network diagram of road connections between major towns in southern England.
Figure 1. Network diagram of road connections between major towns in southern England.

This graph of roads connecting towns in southern England has had the distances in miles added to the edges that represent the routes. This makes the graph a network.

The numbers that correspond to each edge are called weights.

The discrete maths that is included at A Level contains two main applications of networks. These are:

  1. Minimum connector. The tree that connects all of the vertices in the set with the minimum weight when all included edges are summed.
  2. Shortest path The shortest path that connects any two vertices in the set.

Minimum Connector

The minimum connector problem gives a way to join every vertex in a network so that the total weight of the edges used is minimised.

Figure 1: Roads connecting towns in southern England

The towns in southern England are to be connected with a new fibre-optic cable system. The hub of the system is to be in London. What is the minimum length of cable needed to connect the towns?

There are two algorithms that we can use to solve this type of problem:

  1. Kruskal’s algorithm
  2. Prim’s algorithm

We will look at each of these individually and see the benefits of Prim’s algorithm for computational purposes.

Kruskal’s Algorithm

Kruskal’s algorithm finds the minimum spanning tree for a network.

Kruskal’s algorithm has the following steps:

  1. Select the edge with the lowest weight that does not create a cycle. If there are two or more edges with the same weight choose one arbitrarily.
  2. Repeat step 1 until the graph is connected and a tree has been formed.

Example

Finding the minimum spanning tree that follows the road network in southern England

Using Kruskal’s algorithm the minimum spanning tree is generated as follows (each selected edge is coloured red). Click or tap an image for a larger view.

Figure 1: Roads connecting towns in southern England
Figure 1: Roads connecting towns in southern England
Figure 2: Kruskal solution step 1
Figure 3: Kruskal solution step 2
Figure 4: Kruskal solution step 3
Figure 5: Kruskal solution step 4
Figure 6: Kruskal solution step 5

The solution for the minimum spanning tree contains the edges {(Bristol, Swindon), (Swindon, Oxford), (Oxford, Reading), (Reading, London), (Reading, Southampton)}. The total weight (distance) for the minimum solution is 27 + 30 + 40 + 40 + 42 = 179 \text{(miles)}.