IBDP Mathematics Applications & Interpretations HL Chapter21 Notes

graph theory

STUDY NOTES FOR MATHEMATICS – CHAPTER 15 – GRAPH THEORY

These notes have specially been curated by expert teachers to simplify and enlighten concepts given in IB Mathematics HL. The notes are comprehensive in nature and are sufficient to study the chapter in depth and one need not look for other resources beyond the notes provided on our website which can be accessed for free. The notes for Mathematics IBDP HL are available on our official website and can be downloaded for free. You are one click away from obtaining all that you need to score well in IB Mathematics HL.

All DP mathematics courses serve to accommodate the diverse range of needs, interests and abilities of students, and to fulfill the requirements of various university and career aspirations. The aims of these courses are to enable students to: develop mathematical knowledge, concepts, principles, logical, critical and creative thinking, employ and refine their powers of abstraction and generalization. Students are also encouraged to appreciate the international dimensions of mathematics and the multiplicity of its cultural and historical perspectives.

A graph or a network is a structure that shows the relationships between things of interest. These things of interest are depicted by points and the connections by lines. In undirected graphs, adjacent vertices are vertices connected by an edge and adjacent edges share a common vertex. Directed graphs contain arrows indicating the direction we can move along the arrows. This chapter will discuss the properties of graphs, such as simple, connected, disconnected, and weighted. The routes on graphs look at the different ways of moving from vertex to vertex along the edges of a graph, where the length of a route is the number of edges traversed. An adjacency matrix shows how the nodes of a network are connected. They can provide clear depictions of the one-step connections between vertices. However, there are limitations to adjacency matrices since they cannot show whether the route is efficient. Trees are connected, simple graphs with no cycles. A spanning tree of a graph is a tree that contains all the vertices of a graph. The minimum spanning tree is the spanning tree that has the minimum weight. Two algorithms are considered when finding minimum spanning trees: Kruskal’s algorithm and Prim’s algorithm.