Embedded Files
Summary
Summary
Lesson Goals
Lesson Goals
By the end of the lesson, students should be able to:
By the end of the lesson, students should be able to:
Define networks as a system of interconnecting objects
Describe networks using basic network terminology (vertices, edges, and degrees)
Construct network diagrams of simple networks, including from verbal instructions
Compare network diagrams in terms of their number of vertices and edges, as well as the degree of each of the vertices
Understand what is expected for their Vocabulary Journal ('Trip Log') and their presentation project
Syllabus Content
Syllabus Content
N1.1 Networks
Students:
identify and use network terminology: vertices, edges, paths, the degree of a vertex, directed networks and weighted edges
Working Mathematically
Working Mathematically
Represent networks in graphical form given images and verbal instructions (Communicating, Fluency)
Describe and compare the features of a network diagram using the terms vertex, edges and degrees (Communicating, Fluency)
Identify appropriate vertices and edges from descriptions of a range of networks (Understanding, Fluency, Communicating)
Use trial-and-error to find trails in network diagrams (Problem-Solving, Fluency)
Resources
Resources
Images of Real-World Networks (see Unit Preparation)
Königsberg Bridges Image printed on A4 or A3 paper (see Introduction)
Portable Whiteboards, Whiteboard Markers
Projector/Interactive Whiteboard
Graph Table Handout (see Introduction)
Laptops (for pairs, see Body)
Assessment Notification (see Conclusion)
Strategies Used
Strategies Used
Group/Individual Problem Solving (Trial-&-Error)
Class Discussion
Group/Class Vocabulary Activity (Table)
Describe & Draw Pair Activity
ICT Usage (Graph Drawing)
New Vocabulary
New Vocabulary
Networks
Networks
"A network is a group of system of interconnecting objects which can be represented as a diagram of connected lines (called edges) and points (called vertices). For example a rail network."
Image: London Tube Map
See Resources and Bonus Activities for examples.
Network Diagrams
Network Diagrams
"A network diagram is a representation of a group of objects called vertices that are connected together by lines called edges.
Also known as: network graph, graph
'Network diagram' should be used instead of 'graph', as it can be confused with graphs of functions.
Network diagrams are generally not drawn to scale.
Seven Bridges of Königsberg
Seven Bridges of Königsberg
The Seven Bridges of Königsberg connected two islands - Kneiphof and Lomse - to the mainland part of the city of Königsberg. A famous problem at the time was to find a walk through the city that would cross each of the bridges once and only once. This problem was proven to have no solution by Leonhard Euler in 1736.
Traversable Network
Traversable Network
A traversable network is a network that has a trail that includes every edge, i.e. one can trace a trail on the graph without repeating an edge or taking the pen off the paper. Connected networks are traversable if all of their vertices are of even degree, or if two and only two vertices are of odd degree (in this case, the trail begins at one of these vertices and ends at the other one).
Vertex/Vertices
Vertex/Vertices
"A vertex is a point in a network diagram at which lines of pathways (called edges) intersect or branch."
Also called: node, object, point
Image: Vertices shown in red
Not to be confused with vertices from Geometry (point where two lines meet, forming an angle).
The set of vertices can be labelled as such: V = {A, B, C, D, E} where, e.g. A, is the label of the vertex.
Edges/Arcs
Edges/Arcs
"In a network diagram, an edge refers to a line which joins vertices to each other.
Also called: arc, link, line
Image: Edges shown in blue
Not to be confused with edges from Geometry (line segment joining two vertices in a polygon or polyhedron).
Edges can cross each other without intersecting at a vertex. Two vertices can be connected to each other by multiple edges. Vertices may also be connected to itself by loops (i.e. the edge starts and ends at the same vertex).
The set of edges can be labelled as such: E = (A,B), (B,C), (A,C) where, e.g. (A,B), is the label of the edge joining vertices A and B.
Degree (of a vertex)
Degree (of a vertex)
The degree of a vertex is equal to the number of edges that connect to the vertex.
The degree of a vertex is either even or odd, determined by the number of edges attached to the vertex.
Loops count as one edge but contribute two to the degree of a vertex.
The degree of a vertex A can be written as such:
deg(A) = 3.
Lesson Details
Lesson Details
Unit Preparation
Unit Preparation
(Suggestion): Around the classroom, display on the walls different real-world examples of networks
Print off assessment notifications for each student, and prepare to group them into fours
Portable whiteboards should be provided to each table group
sydney-rail-network-map-5-jan.pdfhttps://transportnsw.info/document/4746/sydney-rail-network-map-5-jan.pdf Sydney rail network, from Transport NSW
https://upload.wikimedia.org/wikipedia/commons/b/b3/Connectome.jpg Connectome, from Wikimedia
https://upload.wikimedia.org/wikipedia/commons/c/c3/Internet_map_4096.png Internet Map, from Wikimedia
https://en.wikipedia.org/wiki/File:World_map_of_submarine_cables.png World Map of Submarine Cables, from Wikipedia
https://upload.wikimedia.org/wikipedia/commons/f/f8/Zodiac_Constellations.jpg Zodiac Constellations, from Wikimedia
https://upload.wikimedia.org/wikipedia/commons/thumb/7/70/Phylogenetic_tree.svg/800px-Phylogenetic_tree.svg.png Phylogenetic Tree, from Wikimedia
Orientation
Orientation
Working Mathematically: Problem Solving, Communicating, Understanding, Fluency
Class Discussion [10 min] [LIT]
Display the Königsberg Bridge Map on a screen, or print an A4 copy of the image for each table group. Alternatively, print out a large (A3) copy and gather the class around one table.
Direct students' attention to the map and present the following problem:
"Imagine you are standing somewhere in the city of Königsberg. Find a walk through this city that would cross each of the seven bridges once and only once."
Give students 5 minutes to use trial-and-error to find a possible walk. Afterwards, poll them if they were able to find one (if so, have students trace it out) (AFL).
Ask students how they would simplify the map, e.g. removing the buildings from the map. Have students volunteer to draw simpler diagrams on the main whiteboard, and keep iterating the diagrams until it has been reduced to points and lines (AFL).
Explain the following (and ask the follow-up questions (AFL)):
The points are called vertices (what do they represent?)
The lines are called edges (what do they represent, and what do they do?)
Königsberg Bridge Map - Details
Retrieved from Wikimedia at https://upload.wikimedia.org/wikipedia/commons/9/9d/Konigsberg_Bridge.pngBridges highlightedKönigsberg Bridge Map - Details
Modified map diagrams created in paint.net
Introduction
Introduction
Working Mathematically: Communicating, Fluency
Individual/Group Work (15 min) [LIT/NUM]
Project (or draw) the following six network diagrams (including the Konigsberg Bridges [6]) on the board, as well as the Graph Table (next to the diagrams).
Introduce students to the key terminology and their diagrammatic representations in network diagrams: vertex, edge and degree (even or odd) (see Vocabulary).
Scaffold the table-filling by completing the first two examples as a class, then instruct students to individually fill out the table. Encourage students to also draw the diagrams on their portable whiteboard so they can discuss it as a table group. During this time, monitor students' progress and provide additional explanations if requested (ask students to describe the key terminology (edge, vertex, degree) and to label the diagrams, e.g. using colours, if they are confused) (AFL).
While monitoring group-work, if groups have completed a row for a particular graph, ask them to verbally describe the graph using the key terminology, e.g. Graph 1 has 3 edges connecting 3 even-degree vertices (AFL).
Explain the following for Graph 5: a loop counts as 1 edge but contributes 2 to the degree of a vertex.
Explain the following for Graph 6: multiple edges can connect two vertices.
Once most of the groups have finished, ask groups to contribute their answers for each row (and fill out the table on the board as a class) (AFL). Once the table is completely filled, ask groups to answer the following questions (AFL):
What are some ways we could group these graphs into categories?
What are the similarities and differences between Graphs 1 & 2 versus Graphs 3 & 7?
What are the similarities and differences between Graphs 3 & 7 versus Graphs 4 & 6?
Graph Table - Details
Created in MS Word; print out for each student or instruct students to copy the table into their workbooksGraph Table - Details
Intro to Networks Table (Updated).docxBody
Body
Working Mathematically: Communicating, Fluency
Network Diagram Drawing (20 min) [LIT]
Instruct students to create an example network diagram on their portable whiteboard with 7 (or any other number of) vertices. Their diagrams should contain the following features:
Vertices - labelled alphabetically (e.g. A, B, C, ...)
Edges - each vertex should have an edge connected to it (i.e. no isolated vertices)
Degree - label each vertex with its degree number (there should be a mix of even and odd)
Multiple edges - between at least one pair of vertices, there should be multiple edges
Loop - for at least one vertex, it should have a loop (i.e. an edge that starts and ends at the same vertex)
Once completed and checked by the teacher (AFL), students should redraw the diagram into their workbooks. Each feature should be annotated with a short definition (see Example Network Diagram).
Example Network Diagram
Example Network Diagram
Network Describe & Draw (Pair-work) (if finished early) [LIT]
In pairs, students spend time drawing network diagrams in their workbooks (of 5-8 vertices). Afterwards, students take turns being either the instructor or the drawer.
Instructor: student selects a network diagram that they have created that they want the other student to draw.
The instructor must not show the other student what the diagram looks like; they may only verbally communicate details about the diagram.
E.g. there are 5 vertices (A, B, C, D, E); A is connected to B, ...
Drawer: using the instructions provided to them, the drawer tries to reconstruct the diagram on a laptop (using a graph drawing website).
The drawer CANNOT take notes; instead, they should continually ask for help from their instructor.
Once the drawer thinks they are complete, the instructor checks their laptop and verifies if their diagrams are a match.
If the diagrams match, the pair swap roles.
If the diagrams do not match, the instructor continues providing instructions.
Additional Challenges (Differentiation)
(if the activity is too easy for students)Additional Challenges (Differentiation)
The instructor is not allowed to state which vertices are connected to each other.
The instructor must give at least three different types of information (e.g. number of vertices, number of edges, a vertex connection, degree of a vertex).
The instructor must give their information/instructions in only one sentence.
The drawer must try to exactly match their drawing with the instructor's original diagram, including the correct relative positioning of vertices.
URL: https://mrpandey.github.io/graphPlayground/
Alternate website (for more exact network diagrams): http://graphonline.ru/
Conclusion
Conclusion
Working Mathematically: Communicating, Fluency
Class Questions (5 min) [LIT/NUM]
Final Task: Draw a simple network diagram on the board and ask students to answer the following questions by holding up a number of fingers (AFL):
How many vertices are there?
How many edges are there?
What is the degree of this vertex?
For each question, ask students to briefly explain how they worked out their answer (AFL).
Assessment Notification (10 min)
Inform students about the two assessment components that they will be assessed on (AOL) at the conclusion of Networks and Paths.
1. Trip Log (Individual)
1. Trip Log (Individual)
Students will individually create a document (online or offline, e.g. in a separate workbook or folder) that they will regularly update with vocabulary and related diagrams from Networks and Paths. Students will be awarded up to 20 marks for providing definitions and diagram examples for the following terminology:
Network, network diagram, vertex, edge, degree (of a vertex), loop, multiple edges, simple network, connected network, weighted edges, directed edges, walk, trail, cycle, path, tree, (minimum) spanning tree, Prim's algorithm, Kruskal's algorithm, Dijkstra's algorithm
The following is NOT ASSESSED, but it is recommended that student include the following:
Examples of real-world networks (either covered in class or researched)
Evidence of research and analysis for their group presentation project
2. Project Presentation (Group)
2. Project Presentation (Group)
At the end of Networks and Paths, students will conduct a group presentation, showcasing the research and analysis they have conducted on a real-world example of a network.
The presentation should explicitly feature the key terminology covered in Networks and Paths.
Additional details, including the marking guidelines, can be found here.
Homework/Follow-Up
Homework/Follow-Up
Students are highly encouraged to create and begin filling their Trip Log (Network, Network Diagram, Vertex, Edge, Degree), as well as to begin researching networks with their groups (AOL).
Homework:
Research real-world examples of networks (students will write their examples on the board at the start of the next lesson) - identify the possible benefits of analysing them as networks
Examples could include: social networks (e.g. Facebook); food webs; transport networks (e.g. Sydney Rail); computer cable networks; constellations; tree branches; local town map
See Resources to give students further ideas
Bonus Task: Find online sources that explain the Königsberg Bridge problem and why it is impossible to find a solution. Additionally, propose additional edges (or remove some) to make the problem solvable.
Image: Portrait of Leonhard Euler by Jakob Emanuel Handmann (1753), from Wikimedia
Google Sites
Report abuse