Learning objectives
By the end of this week you can:
- 1 Decide connectivity and find connected components.
- 2 Explain Euler and Hamilton paths and when they exist.
- 3 Color graphs, compute simple chromatic numbers and apply coloring to scheduling.
- 4 Use the properties of trees: n vertices, n − 1 edges, unique paths.
- 5 Present your semester project clearly in five minutes.
★ the wow moment
Four colors are enough for any map, and the proof needed a computer.
The four color theorem was proved in 1976 by checking about 1,500 cases by computer, the first famous computer-assisted proof. Graph coloring also schedules your exams and assigns CPU registers in every compiler.
Topics
- Paths, connectivity, components
- Euler and Hamilton paths
- Graph coloring and chromatic number
- Trees and spanning trees
- Project demo day
Before class
- Skim Rosen 10.4, 10.8, 11.1 (20 minutes is enough; we go through it together).
- Bring paper and a pen: part of every lecture is solving by hand.
In industry
-
Scheduling
Exam timetables: courses are vertices, shared students are edges, time slots are colors.
-
Compilers
Register allocation colors an interference graph so that variables share CPU registers safely.
-
File systems and data
Folders, JSON documents and HTML pages are trees; Huffman trees compress files.
Lab 13: Coloring an Exam Timetable
Build the conflict graph of real courses and color it greedily to produce an exam schedule.
due Fri, Jan 1 · 23:59 · 100 points · opens in week 15
Go deeper
Tags:connectivityEulerHamiltoncoloringchromatic numbertreespanning treeproject