Computer Science · Grade 11 · Algorithmic Foundations and Complexity · Term 1

Introduction to Graph Theory

Explore basic graph concepts, including nodes, edges, and common graph representations (adjacency matrix, adjacency list).

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

About This Topic

Graph theory introduces students to nodes, also called vertices, and edges that connect them. These structures model real-world relationships, such as friendships in social networks or routes in transportation systems. Students learn common representations: adjacency matrices, which use a grid to show connections, and adjacency lists, which pair each node with its neighbors. They compare these methods and see how matrices suit dense graphs while lists work well for sparse ones.

This topic fits into the algorithmic foundations unit by building skills in abstraction and modeling. Students construct graphs to solve problems like finding shortest paths, which prepares them for complexity analysis later. It connects computer science to everyday networks, fostering computational thinking through visualization of data structures.

Active learning shines here because graph concepts start abstract but become concrete when students draw and manipulate them. Pairing physical models with digital tools helps students test representations hands-on, spot patterns in real data, and discuss trade-offs collaboratively. This approach makes theory memorable and equips students to apply graphs confidently.

Key Questions

1. Explain how graphs can model real-world relationships and networks.
2. Compare different graph representations and their suitability for various problems.
3. Construct a simple graph to represent a social network or transportation system.

Learning Objectives

• Identify the components of a graph: nodes (vertices) and edges.
• Compare and contrast the adjacency matrix and adjacency list representations for a given graph.
• Explain how graph theory can model relationships in a social network or a transportation system.
• Construct an adjacency matrix and an adjacency list for a simple, undirected graph.
• Analyze the suitability of adjacency matrices versus adjacency lists for representing sparse versus dense graphs.

Before You Start

Introduction to Data Structures

Why: Students need a basic understanding of how data can be organized and stored to grasp different graph representations.

Basic Programming Concepts (Variables, Arrays)

Why: Familiarity with variables and arrays is essential for understanding how adjacency matrices and lists are implemented in code.

Key Vocabulary

Node (Vertex)	A fundamental unit in a graph, representing an entity or a point. In a social network, a node could be a person; in a map, it could be a city.
Edge	A connection between two nodes in a graph, representing a relationship or a path. An edge can signify friendship between people or a road between cities.
Adjacency Matrix	A square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or in the same edge.
Adjacency List	A collection of lists, one for each vertex in the graph. Each list contains all the vertices adjacent to the vertex.
Graph Representation	The method used to store graph data in computer memory, such as an adjacency matrix or an adjacency list.

Watch Out for These Misconceptions

Common Misconception

Graphs are just for math puzzles, not real computer science applications.

What to Teach Instead

Graphs model networks in software like social media algorithms or GPS routing. Hands-on activities where students build personal examples reveal practical uses, shifting focus from abstraction to utility through peer sharing.

Common Misconception

Adjacency matrices are always easier than lists.

What to Teach Instead

Matrices grow large for sparse graphs, while lists save space. Group comparisons of sample graphs highlight trade-offs, helping students evaluate based on graph density during collaborative problem-solving.

Common Misconception

All edges are the same, ignoring direction.

What to Teach Instead

Directed edges matter in one-way streets or follows on social media. Drawing both types in pairs clarifies differences, with discussions reinforcing when direction impacts representation choices.

Active Learning Ideas

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.

30 min·Pairs

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.

45 min·Small Groups

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.

20 min·Whole Class

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.

25 min·Individual

Real-World Connections

• Google Maps uses graph theory to find the shortest or fastest routes between locations, representing intersections as nodes and roads as edges.
• Social media platforms like Facebook or LinkedIn model user connections as graphs, where users are nodes and friendships or connections are edges, enabling features like friend suggestions.
• Network engineers use graph theory to design and analyze computer networks, representing routers and servers as nodes and network links as edges to optimize data flow and identify potential bottlenecks.

Assessment Ideas

Quick Check

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.

Exit Ticket

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.

Discussion Prompt

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.

Frequently Asked Questions

How do adjacency matrices differ from adjacency lists in graph theory?

Adjacency matrices use a square grid where rows and columns represent nodes, with 1s or weights showing edges; they are simple for dense graphs but memory-intensive. Adjacency lists store each node's neighbors in a linked structure, ideal for sparse graphs as they use less space. Students compare them by building both for the same network to see suitability firsthand.

What real-world examples work best for introducing graph theory?

Social networks with friends as edges, transportation systems with roads connecting cities, or web pages linked by hyperlinks. Start with familiar contexts like a class friendship map to engage students, then scale to larger systems. This builds relevance and eases into formal representations.

How can active learning help students grasp graph representations?

Active methods like drawing graphs on paper or using interactive tools let students manipulate nodes and edges directly, comparing matrix and list formats side-by-side. Small group challenges to model real networks reveal pros and cons through trial and error. Discussions after building solidify understanding, turning passive recall into applied skill.

What tools support teaching graph theory in grade 11 computer science?

Free options include Draw.io for visuals, Python with NetworkX for coding graphs, or GeoGebra for interactive demos. Pair these with paper sketches for low-tech entry. Assign tasks where students export representations to compare formats, blending analog and digital for comprehensive practice.