HL Graph Theory 3.14+3.16

At the heart of the modern day search for knowledge: internet "search engines", lies Graph theory. Google's "PageRank" algorithm is a classic example.

The problems faced by many computer programmers, all specialisms combined, can often be facilitated by taking a 'Graph Theory' approach. It could be renamed: "The Theory of Networks". It is the study of relationships between objects and those "objects" could be anything: from cities, to airports, to business headquarters to connections between people (think Facebook Messenger, Instagram) etc.etc. Welcome to Graph Theory!


Teaching slides

Please find below some slides to help present and teach these ideas to students. You can click on the fullscreen "Presentation mode" from the tools on the right-hand side of this page:  to make the slide fill the screen. Keep clicking on the ARROW on the RIGHT until it is greyed out/it is no longer possible:   to see all the detail on each slide.


Student Notes sheet

Student Notes - Graph Theory 3.14 & 3.16  worksheet that students can use digitally or print off and annotate, as a summary of the keypoints accompanying/from the above presentation


IB exam style questions

Graph Theory - Introduction & Algorithms A exam style questions to test if you feel ready, or what you need to review, ahead of moving on to the new topic or your end of unit test/mocks/final exams!

SOLUTIONS and markscheme available here.



Syllabus

AHL 3.14 vertices, edges, degree of a vertex etc. Simple, weighted, directed graphs and subgraphs.
AHL 3.16 Kruskal's and Prim's algorithms for working out the minimal spanning tree. Chinese postman problem.


All materials on this website are for the exclusive use of teachers and students at subscribing schools for the period of their subscription. Any unauthorised copying or posting of materials on other websites is an infringement of our copyright and could result in your account being blocked and legal action being taken against you.