You are currently browsing the tag archive for the ‘graph theory’ tag.

telephone2

If you are a teacher then please also visit my new site: intermathematics.com for over 2000+ pdf pages of resources for teaching IB maths!

The Telephone Numbers – Graph Theory

The telephone numbers are the following sequence:

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496…

(where we start from n=0).

This pattern describes the total number of ways which a telephone exchange with n telephones can place a connection between pairs of people.

To illustrate this idea, the graph below is for n=4.  This is when we have 10 telephones:

telephone

Each red line represents a connection.  So the first diagram is for when we have no connections (this is counted in our sequence).  The next five diagrams all show a single connection between a pair of phones.  The last three diagrams show how we could have 2 pairs of telephones connected at the same time.  Therefore the 4th telephone number is 10.   These numbers get very large, very quickly.

Finding a recursive formula

The formula is given by the recursive relationship:

T(n) = T(n-1) + (n-1)T(n-2)

This means that to find (say) the 5th telephone number we do the following:

T(5) = T(5-1) + (5-1)T(5-2)

T(5) = T(4) + (4)T(3)

T(5) = 10 + (4)4

T(5) = 26

This is a quick way to work out the next term, as long as we have already calculated the previous terms.

Finding an nth term formula

The telephone numbers can be calculated using the nth term formula:

telephone7

This is going to be pretty hard to derive!  I suppose the first step would start by working out the total number of connections possible between n phones – and this will be the the same as the graphs below:

telephone3

These clearly follow the same pattern as the triangular numbers which is 0.5(n² +n) when we start with n = 1.  We can also think of this as n choose 2 – because this gives us all the ways of linking 2 telephones from n possibilities.  Therefore n choose 2 also generates the triangular numbers.

But then you would have to work out all the permutations which were allowed – not easy!

Anyway, as an example of how to use the formula to calculate the telephone numbers, say we wanted to find the 5th number:

We have n = 5.  The summation will be from k = 0 and k = 2 (as 5/2 is not an integer).

Therefore T(5) = 5!/(20(5-0)!0!) + 5!/(21(5-2)!1!) + 5!/(22(5-4)!2!)

T(5) = 1 + 10 + 15 = 26.

Finding telephone numbers through calculus

Interestingly we can also find the telephone numbers by using the function:

y = e0.5x2+x

 and the nth telephone number (starting from n = 1)  is given by the nth derivative when x = 0.

For example,

telephone5

So when x = 0, the third derivative is 4.  Therefore the 3rd telephone number is 4.

The fifth derivative of the function is:

telephone6

So, when x =0 the fifth derivative is 26.  Therefore the 5th telephone number is 26.

If you liked this post you might also like:

Fermat’s Theorem on the Sum of two Squares – A lesser known theorem from Fermat – but an excellent introduction to the idea of proof.

Unbelievable: 1+2+3+4…. = -1/12 ? A result that at first glance looks ridiculous – and yet can be shown to be correct.  How?

Essential resources for IB students:

1) Revision Village

Screen Shot 2021-05-19 at 9.55.51 AM

Revision Village has been put together to help IB students with topic revision both for during the course and for the end of Year 12 school exams and Year 13 final exams.  I would strongly recommend students use this as a resource during the course (not just for final revision in Y13!) There are specific resources for HL and SL students for both Analysis and Applications.

Screen Shot 2018-03-19 at 4.42.05 PM.png

There is a comprehensive Questionbank takes you to a breakdown of each main subject area (e.g. Algebra, Calculus etc) and then provides a large bank of graded questions.  What I like about this is that you are given a difficulty rating, as well as a mark scheme and also a worked video tutorial.  Really useful!

Screen Shot 2021-05-19 at 10.05.18 AM

The Practice Exams section takes you to a large number of ready made quizzes, exams and predicted papers.   These all have worked solutions and allow you to focus on specific topics or start general revision.  This also has some excellent challenging questions for those students aiming for 6s and 7s.

Essential Resources for IB Teachers

1) Intermathematics.com

Screen Shot 2021-08-21 at 1.07.49 PM

If you are a teacher then please also visit my new site.  This has been designed specifically for teachers of mathematics at international schools.  The content now includes over 2000 pages of pdf content for the entire SL and HL Analysis syllabus and also the SL Applications syllabus.  Some of the content includes:

  1. Original pdf worksheets (with full worked solutions) designed to cover all the syllabus topics.  These make great homework sheets or in class worksheets – and are each designed to last between 40 minutes and 1 hour.
  2. Original Paper 3 investigations (with full worked solutions) to develop investigative techniques and support both the exploration and the Paper 3 examination.
  3. Over 150 pages of Coursework Guides to introduce students to the essentials behind getting an excellent mark on their exploration coursework.
  4. A large number of enrichment activities such as treasure hunts, quizzes, investigations, Desmos explorations, Python coding and more – to engage IB learners in the course.

There is also a lot more.  I think this could save teachers 200+ hours of preparation time in delivering an IB maths course – so it should be well worth exploring!

Essential Resources for both IB teachers and IB students

1) Exploration Guides and Paper 3 Resources

Screen Shot 2021-12-01 at 1.19.14 PM

I’ve put together a 168 page Super Exploration Guide to talk students and teachers through all aspects of producing an excellent coursework submission.  Students always make the same mistakes when doing their coursework – get the inside track from an IB moderator!  I have also made Paper 3 packs for HL Analysis and also Applications students to help prepare for their Paper 3 exams.  The Exploration Guides can be downloaded here and the Paper 3 Questions can be downloaded here.

The Chinese Postman Problem

There is a fantastic pdf resource from Suffolk Maths which goes into a lot of detail on this topic – and I will base my post on their resource.   Visit their site for a more in-depth treatment.

The Chinese Postman Problem was first posed by a Chinese mathematician in 1962.  It involved trying to calculate how a postman could best choose his route so as to mimise his time.  This is the problem that Kuan Mei-Ko tried to solve:

chinesepost1

How could a postman visit every letter on the graph in the shortest possible time?

Solving this requires using a branch of mathematics called graph theory, created by Leonard Euler.  This mathematics looks to reduce problems to network graphs like that shown above.  Before we can solve this we need to understand some terminology:

chinesepost3

Above we have 3 graphs.  A graph which can be drawn without taking the pen off the paper or retracing any steps is called traversable (and has a Euler trail).  Graph 1 is not traversable.  Graph 2 is traversable as long as you start at either A or D, and Graph 3 is traversable from any point that you start.  It turns out that what dictates whether a graph is traversable or not is the order of their vertices.

Looking at each letter we count the number of lines at the vertex.  This is the order.  For graph 1 we have 3 lines from A so A has an order of 3.  All the vertices on graph 1 have an order of 3.  For graph 2 we have the orders (from A, B, C, D, E in turn) 3, 4, 4, 3, 2.  For graph 3 we have the orders 4,4,4,4,2,2.

This allows us to arrive at a rule for working out if a graph is traversable.

If all orders are even then a graph is traversable.  If there are 2 odd vertices then we can find a traversable graph by starting at one of the odd vertices and finishing at the other.  We need therefore to pair up any odd vertices on the graph.

Next we need to understand how to pair the odd vertices.  For example if I have 2 odd vertices, they can only be paired in one way.  If I have 4 vertices (say A,B,C,D) they can be paired in 3 different ways (either AB and CD or AC and BD or AD and BC) .  The general term rule to calculate how many ways n odd vertices can be paired up is (n-1) x (n-3) x (n-5) … x 1.

So now we are ready to actually solve the Chinese Postman Problem.  Here is the algorithm:

chinesepost4

So, we can now apply this to the Chinese Postman Problem below:

chinesepost1

Step 1:  We can see that the only odd vertices are A and H.

Step 2:  We can only pair these one way (AH)

Step 3 and 4: The shortest way to get from A to H is ABFH which is length 160.  This is shown below:

 chinesepost5

 Step 5 and 6: The total distance along all the lines in the initial diagram is 840m.  We add our figure of 160m to this.  Therefore the optimum (minimum) distance it is possible to complete the route is 1000m.

Step 7:  We now need to find a route of distance 1000m which includes the loop ABFH (or in reverse) which starts and finishes at one of the odd vertices.  One solution provided by Suffolk Maths is ADCGHCABDFBEFHFBA.  There are others!

The Bridges of Konigsburg

Graph theory was invented as a method to solve the Bridges of Konigsburg problem by Leonard Euler.  This was a puzzle from the 17oos – Konigsburg was a Russian city with 7 bridges, and the question was, could anyone walk across all 7 without walking over any bridge twice.  By simplifying the problem into one of connected lines, Euler was able to prove that this was in fact impossible.

If you like this post you might also like:

Knight’s Tour – This puzzles dates over 1000 years and concerns the ways in which a knight can cover all squares on a chess board.

Game Theory and Tic Tac Toe – Tic Tac Toe has already been solved using Game Theory – this topic also brings in an introduction to Group Theory.

telephone2

The Telephone Numbers – Graph Theory

The telephone numbers are the following sequence:

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496…

(where we start from n=0).

This pattern describes the total number of ways which a telephone exchange with n telephones can place a connection between pairs of people.

To illustrate this idea, the graph below is for n=4.  This is when we have 10 telephones:

telephone

Each red line represents a connection.  So the first diagram is for when we have no connections (this is counted in our sequence).  The next five diagrams all show a single connection between a pair of phones.  The last three diagrams show how we could have 2 pairs of telephones connected at the same time.  Therefore the 4th telephone number is 10.   These numbers get very large, very quickly.

Finding a recursive formula

The formula is given by the recursive relationship:

T(n) = T(n-1) + (n-1)T(n-2)

This means that to find (say) the 5th telephone number we do the following:

T(5) = T(5-1) + (5-1)T(5-2)

T(5) = T(4) + (4)T(3)

T(5) = 10 + (4)4

T(5) = 26

This is a quick way to work out the next term, as long as we have already calculated the previous terms.

Finding an nth term formula

The telephone numbers can be calculated using the nth term formula:

 

telephone7

 This is going to be pretty hard to derive!  I suppose the first step would start by working out the total number of connections possible between n phones – and this will be the the same as the graphs below:

telephone3

These clearly follow the same pattern as the triangular numbers which is 0.5(n² +n) when we start with n = 1.  We can also think of this as n choose 2 – because this gives us all the ways of linking 2 telephones from n possibilities.  Therefore n choose 2 also generates the triangular numbers.

But then you would have to work out all the permutations which were allowed – not easy!

Anyway, as an example of how to use the formula to calculate the telephone numbers, say we wanted to find the 5th number:

We have n = 5.  The summation will be from k = 0 and k = 2 (as 5/2 is not an integer).

Therefore T(5) = 5!/(20(5-0)!0!) + 5!/(21(5-2)!1!) + 5!/(22(5-4)!2!)

T(5) = 1 + 10 + 15 = 26.

Finding telephone numbers through calculus

Interestingly we can also find the telephone numbers by using the function:

y = e0.5x2+x

 and the nth telephone number (starting from n = 1)  is given by the nth derivative when x = 0.

For example,

telephone5

So when x = 0, the third derivative is 4.  Therefore the 3rd telephone number is 4.

The fifth derivative of the function is:

telephone6

So, when x =0 the fifth derivative is 26.  Therefore the 5th telephone number is 26.

If you liked this post you might also like:

Fermat’s Theorem on the Sum of two Squares – A lesser known theorem from Fermat – but an excellent introduction to the idea of proof.

Unbelievable: 1+2+3+4…. = -1/12 ? A result that at first glance looks ridiculous – and yet can be shown to be correct.  How?

IB Revision

Screen Shot 2018-03-19 at 4.35.19 PM

If you’re already thinking about your coursework then it’s probably also time to start planning some revision, either for the end of Year 12 school exams or Year 13 final exams. There’s a really great website that I would strongly recommend students use – you choose your subject (HL/SL/Studies if your exam is in 2020 or Applications/Analysis if your exam is in 2021), and then have the following resources:

Screen Shot 2018-03-19 at 4.42.05 PM.pngThe Questionbank takes you to a breakdown of each main subject area (e.g. Algebra, Calculus etc) and each area then has a number of graded questions. What I like about this is that you are given a difficulty rating, as well as a mark scheme and also a worked video tutorial.  Really useful!

Screen Shot 2019-07-27 at 10.02.40 AM

The Practice Exams section takes you to ready made exams on each topic – again with worked solutions.  This also has some harder exams for those students aiming for 6s and 7s and the Past IB Exams section takes you to full video worked solutions to every question on every past paper – and you can also get a prediction exam for the upcoming year.

I would really recommend everyone making use of this – there is a mixture of a lot of free content as well as premium content so have a look and see what you think.

Website Stats

  • 8,464,864 views

About

All content on this site has been written by Andrew Chambers (MSc. Mathematics, IB Mathematics Examiner).

New website for International teachers

I’ve just launched a brand new maths site for international schools – over 2000 pdf pages of resources to support IB teachers.  If you are an IB teacher this could save you 200+ hours of preparation time.

Explore here!

Free HL Paper 3 Questions

P3 investigation questions and fully typed mark scheme.  Packs for both Applications students and Analysis students.

Available to download here

IB Maths Super Exploration Guide

A Super Exploration Guide with 168 pages of essential advice from a current IB examiner to ensure you get great marks on your coursework.

Available to download here.

Recent Posts

Follow IB Maths Resources from Intermathematics on WordPress.com