You are here

Introduction to Graph Theory

Author: 
Pretti, J. P.
Issue Date: 
Wednesday, September 22, 2010
Description: 
This presentation will explore graph theory and its relationship to ICS4U. A graph is a mathematical structure usually drawn by connecting dots with lines. They are typically represented in a program using arrays and/or linked lists. Graphs are gentle to introduce, fun to draw and play with, and a wonderful example of the connection between mathematics andcomputer science. Graph theory is also rich with applications such as Facebook and the design of circuits. This talk will touch on using graphs in the classroom, on assignments, as an enrichment opportunity and for computing contest preparation.
Keywords: 
big-oh, algorithm analysis, Python adjacency, Python, algorithms, data structures, computing contest preparation, mathematical structure, graph theory
Education Levels: 
Middle School
High School
Intended Audience: 
Educator
Type: 
Instructional Material : Lecture/Presentation
Publisher: 
U of Waterloo CEMC Summer Institute 2009
URL: 
http://hdl.handle.net/2378/444
CSTA Classification: 

CT.L2-14

Examine connections between elements of mathematics and computer science, including binary numbers, logic, sets and functions.

CT.L3B-10

Decompose a problem by defining new functions and classes.

CPP.L3A-02

Use mobile devices/ emulators to design, develop, and implement mobile computing applications.

CPP.L3A-04

Apply analysis, design, and implementation techniques to solve problems (e.g., use one or more software lifecycle models).

CT.L3A-03

Explain how sequence, selection, iteration, and recursion are building blocks of algorithms.

CT.L3B-04

Evaluate algorithms by their efficiency, correctness, and clarity.

CC.L3C-01c

Program Analysis (AP Comp Sci A Topic III)

CC.L3C-01d

Standard Data Structures (AP Comp Sci A Topic IV)

CT.L3B-06

Compare and contrast simple data structures and their uses (e.g., arrays and lists).

CC.L3C-01e

Standard Algorithms (AP Comp Sci A Topic V)

Download this resource: