David Watson reflects on why the new Mathematics Standard course is useful for students and explains how to teach the new Networks topic…
A problem
The problem presented by the new Mathematics Standard syllabus did not reveal itself straight away.
In preparation for the new Networks topic, I reviewed everything I could. I searched key words such as Kruskal’s Algorithm and Prim’s Algorithm in Google and reviewed the resources provided by NESA to support our programming and assessment.
In doing this work I was quickly reminded of my over-confidence while studying Network Theory at university. It was the beginning of this millennium and I was much younger and, perhaps, less wise. I was twenty-two years old and in my final year and I was amazed at how simple I found the concepts. I even remember thinking that, “I could score 100 in this course!”
Score 100, I did not.
Upon exploring these Networks concepts again now, I enjoyed feeling good at it. It was fun to experience success. Then, while exploring examples online and reviewing the syllabus further, I found the problem that I now consider the biggest danger in my programming for 2018…
It was all a very nice experience for me to return to my university days, to rediscover learning and knowledge I had thought lost or, at least, forgotten. Yet, in amongst the many applications listed in the syllabus, including travel times, power cabling and garbage bin routes, all of which made sense to me, I realised I needed to think on how to help Networks make sense for my students.
Not just make sense, but actually be useful!
To steal a metaphor from Dan Meyer, if Network Diagrams, Shortest Paths, Minimum Spanning Trees and Critical Paths are the aspirin, how do we create the headache?
So, what are we doing with Networks?
In this section, I will present some examples of approaches to introducing the new concepts and reflect on some teaching challenges that I encountered while learning about this content. At the end of the article, I will consider possible solutions to these teaching challenges.
Before you read any further, this article assumes the reader is comfortable to convert an image or table of a real world situation into a network diagram and to understand the language of Network Theory. If you need help at this level you might visit the Mathspace Essentials free, online textbook for a simple and concise explanation, as this is the first section for both the Mathematics Standard 1 (MS1) and Mathematics Standard 2 (MS2) pathways.
Konigsberg Bridge
In Mathematics Standard 2, one additional example is the Konigsberg Bridge problem. Images such as the one below are easily found via an internet search. The map of the city of Konigsberg in Prussia illustrates that the city, either side of the Pregel River and including two islands, includes seven bridges. The problem posed is whether a path can be drawn, with any starting point, so that all bridges are crossed exactly once.
Source https://en.wikipedia.org/wiki/Graph_theory#/media/File:Konigsberg_bridges.png
This bridge town and problem has many interesting elements, and essentially serves as an opportunity for students to investigate networks and practise their skills in modelling a real world situation. A possible diagram that models this situation is below. Click here to view image
The seven bridges are represented by edges and the four separate land sections are represented by vertices. The problem now becomes: “Is there a path that travels along each edge exactly once?” The answer becomes apparent after a few attempts.
It is interesting to note that Konigsberg is now called Kaliningrad and only five of the seven bridges still exist (only two in their original form). This can give rise to discussions about what this new situation does to the problem, and does it matter which of the five bridges are still in existence?
Konigsberg Bridge teaching challenge
My first teaching challenge with this new topic arose when I found it easier to ‘play’ with this problem using the original image than when I attempted to use the new diagram above. I was fortunate enough to have stumbled across the same point of view held by many of the students I have encountered in the current Mathematics General 2 course, seeing the creation of this diagram as a needless extra step.
So why draw a network?
Shortest Path
I will return to the question of drawing a network later. For now, we continue exploring, and look into the concept of Shortest Path and Minimum Spanning Trees. These are concepts that are required in both the MS1 and MS2 pathways.
The Shortest Path between two points is a fairly obvious concept if we consider the diagram below. We want to find the shortest path from vertex A to vertex B. This image is partway through the algorithm, and the numbers ‘12’, ‘15’ and ‘14’ in vertices ‘C’, ‘D’ and ‘E’ respectively represent the minimum distance to get to the first three vertices. The shortest path to ‘D’ is through ‘C’. Click here to view image.
From here we would write ‘27’ in vertex ‘F’, as the shortest distance to ‘F’ is through ‘D’. We would then write ‘31’ in vertex ‘B’, making the shortest distance from A to B equal to 31, with the shortest path being A>C>D>F>B.
Shortest Path teaching challenge
Similarly to the Konigsberg Bridge problem, I encountered my second teaching challenge here. This algorithm was effective; however, I wondered if it was particularly different to what students would do anyway? It was, in essence, an exhaustive method of solving the problem and I wondered if it was still a useful tool for students?
Minimum Spanning Trees
Once again, for now we push on and investigate Minimum Spanning Trees.
I discovered the definition: a set of edges with the minimum cost that connect all vertices together. This concept is, obviously, for weighted edges and also for undirected networks. Yet, the application felt a bit less apparent to me, and so I went searching. The syllabus provided a good recommendation of connecting towns, places or locations to a power station or phone network.
In an online search, the problem that arises most is the ‘Muddy City Problem’. This problem involves a city where the mayor has decided to pave some of the pathways between houses to allow driving access. The mayor hopes to allow for all houses to be accessed from any other house; however, the major also wants the minimum possible cost. Therefore, only the minimum spanning tree in the network will be paved. To view a diagram and free lessons for the Muddy City Problem click here.
The number of pavers in the image displays the cost of paving each road (this could be price, resources or time required, and so on). Prim’s Algorithm suggests we first select the shortest edge, and then continue by selecting the shortest ATTACHED edge. This continues until all vertices are included, and, of course, we avoid all loops. You may have already identified that there are many possible beginnings, as the more edges with equal costs in a network, the more likely we are to find equal solutions.
Kruskal’s Algorithm requires us to start with the smallest edge, and then select the next smallest edge, regardless of whether it is attached to the existing tree or not. Again we must avoid any loops. Regardless of where you begin, by the end of the process all distinct sections will link to make a tree.
A breakthrough
It was at this point that I began to see a solution to the teaching challenges outlined above. Not only were these algorithms both immediately helpful and relatively easy to follow, which was encouraging, but I noticed a key point that I thought I might be able to use. All three problems introduced above can be investigated without the use of Network Theory. They may require scaffolding for your class, but I found I could successfully introduce these problems to Stage 5 students, and all were intrigued and keen to “play” with the problem.
Critical Path Analysis
Now we move on to Critical Path Analysis, the first of two major skills required only by students following the MS2 pathway. When presented with a list of related tasks to complete a job, Critical Path Analysis supports us to analyse the situation, identify the shortest possible time taken to complete the list as well as the latest start time for certain steps without delaying the overall time.
This tool has a variety of applications. A simple one with an example I have created is baking some biscuits for afternoon tea. I enjoy this example because it could be just about any recipe, so students can create and analyse their own situation. The table below describes the steps involved, the prerequisites and the time for each step, as well as labels.
We are looking for the critical path, so we draw a network diagram, where the vertices represent a moment in time where you are available to start a new task (or tasks), and the edges represent the tasks themselves. Below is an analysis of the above table.
In the analysis, it is evident that making a cup of tea (Task G) could be started after 21 minutes, and still not delay the entire task. Mixing in eggs, flour and choc chips (Task D) could not begin until after 10 minutes.
The vertices are split in half and down the centre in my diagram (above), with the number on the left indicating the earliest time that jobs that begin from this vertex could begin. The space on the right of each vertex is reserved for the latest time that a task beginning at this vertex could begin without delaying the overall job. How to communicate this latest start time varies depending on the source you are reviewing, and by looking through a variety of textbooks as well as online industry explanations, I have seen a number of different forms of these vertices. These include circles being divided with a horizontal line, or even vertices divided into three parts.
Critical Path Analysis inspired me with applications relevant to students’ future areas of employment, as well as to their present daily lives. All we really need to consider are tasks that are dependent upon one another, and contribute to the completion of an overall job. Finally, and sometimes most challengingly, we are asking students to look for tasks that in some instances could be completed at the same time.
Maximum-Flow, Minimum-Cut Theorem
The final skill included in the new syllabus is the use of Maximum-Flow, Minimum-Cut Theorem. This is used to determine the maximum flow of something through a network. Considering the network from above from A to B, where A would be considered a source (where the flow originates from) and B considered a sink (where the flow ends). The question is what is the maximum flow that can get from A to B? The lines cutting though the diagram represent “cuts”, because they completely separate the source and the sink. Click here to view image.
The blue, curved line is the minimum cut, as it severs the connection between A and B and it cuts through a total of 19. If the numbers in this diagram represent the number of litres of water that can flow from one vertex to the next per minute, then this ‘19’ is the maximum flow per minute from A to B. The most that can flow into ‘B’ is clearly 24, and while we can easily ‘fill’ vertex ‘F’ with 4 litres per minute (min) and therefore maximise this edge (FB), there are only 15L/min worth of edges approaching ‘C’ and therefore we can only fill this with 15L per minute. This means that while CB is able to allow 20L/min to flow through, only 15L/min is available, giving us a total flow of 15 + 4 = 19.
Similar to the Critical Path Analysis, this strategy has some obvious applications, such as in the area of traffic flow, water and power. In addition, both problems are available to students to investigate without first being given the algorithms to solve. And I can feel a really pleasant headache.
So what to do about my challenges?
The question I was trying to solve while working through Network Theory was, breaking it right down, “Why?”
Not necessarily “Why is it in the course?”, although this is a question that would be answered as a result, but rather, why is it useful, and would I be able to help my students to see this usefulness? Again, if these tools are the aspirin, how could I give my students the headache?
The value of the Konigsberg Bridge problem is not discovering whether or not the bridges can be traversed without repetition, but rather, how can we prove and communicate that a solution does not exist, and why it does not exist. While ‘playing’ with the image might be more natural to students, investigating, discussing and communicating why there is no solution is best supported by the network diagram. The proof relates to the odd degree of each vertex, which is difficult to examine without first defining the vertices.
The students I have shared Shortest Path problems with have been able to investigate the problem, and generally find the solution. When subsequently shown the algorithm, the room filled with “ohhhhh”’s of realisation.
They were able to engage with the Muddy City Problem, order events in a critical path scenario and consider the maximum flow through a network. They often found solutions and could explain how they found them, yet had difficulty convincing me or themselves that this was definitely the maximum, shortest or best solution. Most importantly, their confused looks and questions of one another turned to smiles and satisfaction that there indeed was an easier and more effective way. Their headache had been relieved.
Final thoughts
Not only does allowing your students to investigate these problems first without the algorithm support them to discover the need for one, it provides a fantastic opportunity to apply problem-solving skills and communicate and justify their solutions. When an algorithm is introduced, these skills are able to be revisited and enhanced with a deep understanding of useful tools.
And that is a very useful aspirin.
David Watson is a Mathematics Head Teacher in a Sydney High School, experienced in leading teachers from all stages of their careers in syllabus analysis and program development as well as modernising and engaging the Mathematics classroom. He is a graduate of the University of Technology, Sydney and has worked in a variety of school settings, supporting students from a range of different socio-economic and cultural backgrounds. Since 2015, David has been a working party member for Lachlan Macquarie College, providing professional learning and networking opportunities for teachers as well as enrichment days for highly engaged students of Mathematics and Science.
s at the beginning of the music indicate that the black notes directly to the right of each of the Fs and Cs replace the normal Fs and Cs on the piano keyboard).
at the beginning of the music indicates that the black note directly to the left of each of the Bs (B flat) replaces the normal Bs on the piano keyboard.
For instance, when a politician describes a wind farm as:
