Computer Science · Grade 11

Active learning ideas

Introduction to Graph Theory

Active learning works because graph theory relies on visual and kinesthetic models of relationships. Students need to touch, draw, and compare representations to grasp why matrices and lists exist, and how density changes their usefulness. These hands-on activities let students experience the difference between abstraction and application in real time.

• Ontario Curriculum Expectations
• CS.HS.A.3
• CS.HS.A.4

• 20–45 min
• Pairs → Whole Class
• 4 activities

Activity 01

• Concept Mapping
• 30 min · Pairs

Pairs: Social Network Graph Build

Students pair up to list 10 classmates and their friendships, drawing nodes and edges on paper. They convert the drawing to an adjacency matrix, then an adjacency list. Pairs discuss which representation is clearer for their graph.

Explain how graphs can model real-world relationships and networks.

Facilitation Tip

During the Social Network Graph Build, circulate to gently redirect pairs when they confuse nodes and edges, asking them to point to each on their poster before adding labels.

What to look for

Present students with a simple diagram of a social network (e.g., 4 people with a few friendships). Ask them to: 1. List all the nodes. 2. List all the edges. 3. Draw the adjacency matrix for this network. 4. Write the adjacency list for one specific person.

• Understand
• Analyze
• Create
• Self-Awareness
• Self-Management

Activity 02

• Concept Mapping
• 45 min · Small Groups

Small Groups: Transportation Model Challenge

Groups sketch a city map with intersections as nodes and roads as edges. They represent it using both matrix and list formats, then trace a route between two points. Groups share findings on efficiency.

Compare different graph representations and their suitability for various problems.

Facilitation Tip

In the Transportation Model Challenge, provide sticky notes in two colors to force students to mark directed edges differently from undirected ones.

What to look for

Provide students with a scenario: 'Imagine you are designing a subway map for a small city.' Ask them to: 1. Identify what the nodes and edges would represent. 2. Briefly explain why an adjacency list might be more efficient than an adjacency matrix for this scenario.

• Understand
• Analyze
• Create
• Self-Awareness
• Self-Management

Activity 03

• Concept Mapping
• 20 min · Whole Class

Whole Class: Representation Debate

Display sample graphs of varying sizes on the board. Class votes on best representation per graph, justifying choices. Follow with quick sketches to test ideas.

Construct a simple graph to represent a social network or transportation system.

Facilitation Tip

For the Representation Debate, assign roles to each small group to ensure balanced participation, such as a matrix advocate, a list advocate, and a neutral moderator.

What to look for

Pose the question: 'When would an adjacency matrix be a better choice than an adjacency list for representing a network, and vice versa?' Facilitate a class discussion where students justify their reasoning with specific examples, considering factors like graph density and the types of operations they might perform.

• Understand
• Analyze
• Create
• Self-Awareness
• Self-Management

Activity 04

• Concept Mapping
• 25 min · Individual

Individual: Digital Graph Creator

Students use free online tools like Graphviz to input a simple network, generate matrix and list views, and note differences in output files.

Explain how graphs can model real-world relationships and networks.

Facilitation Tip

With the Digital Graph Creator, demonstrate how to toggle edge direction in the tool so students see the visual cue for directed vs undirected graphs.

What to look for

Present students with a simple diagram of a social network (e.g., 4 people with a few friendships). Ask them to: 1. List all the nodes. 2. List all the edges. 3. Draw the adjacency matrix for this network. 4. Write the adjacency list for one specific person.

• Understand
• Analyze
• Create
• Self-Awareness
• Self-Management

A few notes on teaching this unit

Teach graph theory by alternating between concrete construction and reflective comparison. Start with physical models like posters or sticky notes so students feel the weight of each representation choice. Then, contrast matrices and lists in a side-by-side analysis, asking students to calculate space and access time for the same graph in both forms. Research shows this cycle of build-compare-justify deepens understanding more than lectures alone. Avoid rushing into formal notation before students have built intuition through drawing and discussion.

Successful learning looks like students confidently choosing between adjacency matrices and lists based on graph properties, and articulating why one representation fits a given scenario better than the other. They should also justify their choices using concrete examples from their activities, showing they understand both utility and trade-offs.

---

Watch Out for These Misconceptions

• During the Social Network Graph Build, watch for students who treat graphs as abstract puzzles rather than real-world models.

  Ask each pair to share one way their social network example connects to a real-world application, like friend recommendations or spam detection, to shift focus to utility.

• During the Representation Debate, watch for students who assume adjacency matrices are always easier to use.

  Provide a large sparse graph on the board and ask groups to time how long it takes to find a neighbor using the matrix vs a list, making the trade-offs tangible through live comparison.

• During the Transportation Model Challenge, watch for students who ignore direction in one-way streets or train routes.

  Require students to use arrows on their maps and explicitly label which edges are directed, then ask them to explain how ignoring direction would break their model.

---

Methods used in this brief

• Concept Mapping