Konigsberg was a city in what was known as Prussia (modern day Kaliningrad, Russia). A river runs through the city with two islands situated in the river. Seven briges connect the islands to the mainland and to each other. The Swiss mathematician Leonhard Euler posed the question of whether it was possible to walk a path across all bridges crossing each bridge once and only once. This was the beginning of the mathematics field called graph theory which is the same topic as Networks.
As the first lesson in this topic, the students will participate in an activity where they will explore a physical area in a fictitious scenario and draw a map based on their exploration. Students have an intuitive understanding of maps even when represented in a network, but not a formal understanding of the different ways that networks can be used and analysed. In this lesson they are introduced to the terminology used in networks to prepare them for the following lessons which cover spanning trees and shortest path searches.
Students can draw a network for a given scenario where the vertices and edges represent some item or concept of significance in the scenario.
Students identify and use network terminology: vertices, edges, paths, the degree of a vertex, directed networks and weighted edges.
Blu-Tack or sticky tape
Note: the lesson activity and the island cards resource are taken from CS Unplugged's activity on finite state automata. The lesson activity has been modified to remove computer science concepts.
This activity requires an open area where the students can move around. Desks and chairs should be placed along the walls to create an open space in the classroom.
There are 7 island cards, each one designating a different island in the scenario. Attach the island cards to various desks in the lesson area. The islands can be placed anywhere but it is best to spread them out evenly around the area.
Students will need a paper and pen or pencil to draw out a map as they move around.
0 - 10
Teacher explains the premise of this activity:
Students are pirates searching for Treasure Island. There are a number of islands in the area but students will start off only aware of their starting island. At each island there is a card showing two ships that depart from that island, each ship going to a different destination. Students choose one of the two ships and then move to the island that ship is going to. Students should progressively draw a map of their travel as they move from island to island.
Teacher models what the students should do as they travel from island to island:
Draw circles for the departing island and the destination island and connect them with a line. Label the circles with the island names. Draw an arrow on the line from the departing island to the destination island to indicate the direction of travel.
Students listen to instructions for the activity
10 - 30
In order to prevent students just following each other, teacher should allocate the students in turn to start from one of these islands: Pirates' Island, Shipwreck Island, Musket Hill, and Dead Man's Island.
Instruct any student who reaches Treasure Island to go back to their starting place and take alternate paths to see if they can complete the map. The map is complete when there are two lines going out of every island except for Treasure Island.
Students start from their allocated starting position and move from island to island based on their choices.
Students draw a map of their travel as they progress.
30 - 55
Display an example of the completed map of islands.
Introduce the terminology for the Networks topic [LIT]:
Network and directed network
Vertex and vertices
Edge
Path
Instruct students to compile their own glossary of terms for this topic. Include diagrams where appropriate.
Students compile glossary of terms
Network and directed network
Each student has drawn a network. The line between two islands show that a ship travels between those islands, and the direction of travel is shown by an arrow. This makes it a directed network because the direction of travel is important.
Vertex
An island in the network diagram is represented by a circle known as a vertex. In this example, the vertex represents a physical location in the scenario but it can be used to represent objects other than locations. The plural of vertex is vertices.
Edge
The line connecting two vertices is called an edge. In our example, the edge is the line between two islands indicating that it is possible to travel directly from one island to the other. Our example also has directions on all of the edges to show the direction of travel. In other network diagrams, an edge could represent the distance between two points or the time it takes to travel from one point to another and they may not have direction.
Path
A path is the sequence of edges when you move from one vertex in the network to another vertex.
Compare your network diagram to that of another student. Have you placed all of the islands in the same place?
In a network diagram, the relative positions of the vertices are not important. The important aspect of a network diagram is the connections between vertices. If two network diagrams show the same vertices connected to each other then they represent the same network regardless of where the vertices are placed.
Find an example of a network in a real life context and draw the network diagram for that scenario.
On your diagram, label the vertices and edges
Identify if your network is directed or not
Draw a path from one vertex to another vertex that passes through at least two other vertices. Is there an alternate path from the starting point to the end point?
Suggestions for networks:
rail network
road links between major cities and towns
students enrolled in different subjects