Learning objectives
By the end of this week you can:
- 1 Model real problems as simple graphs, multigraphs and directed graphs.
- 2 Use degree and the handshake theorem.
- 3 Recognize complete, cycle, wheel, cube and bipartite graphs.
- 4 Represent graphs with adjacency lists and matrices and choose between them.
- 5 Decide whether two graphs are isomorphic using invariants.
★ the wow moment
Google Maps, LinkedIn and your compiler all see the world as G = (V, E).
Cities and roads, people and connections, variables and conflicts: one abstraction, dozens of billion-dollar products. This week you learn the vocabulary; in the lab you load a real network and query it.
Topics
- Graph models
- Degree, handshake theorem
- Special graphs and bipartite graphs
- Adjacency lists and matrices
- Graph isomorphism and invariants
Before class
- Skim Rosen 10.1–10.3 (20 minutes is enough; we go through it together).
- Bring paper and a pen: part of every lecture is solving by hand.
In industry
-
Navigation
Route planning runs shortest-path algorithms on graphs with millions of vertices.
-
Social networks
Friend suggestions, influence and communities are graph problems.
-
Dependencies
Package managers (pip, npm) resolve dependency graphs; build systems order them.
Lab 12: Graphs from Scratch
Build adjacency lists and matrices, verify the handshake theorem, test bipartiteness and compare with networkx.
due Fri, Dec 25 · 23:59 · 100 points · opens in week 14
Go deeper
- Discrete Mathematics: An Open Introduction (Oscar Levin) · Chapter 4, graph theory
- Mathematics for Computer Science (Lehman, Leighton, Meyer) · Chapters 11–12, graphs
- Graph Online · draw and explore graphs
Tags:graphdegreehandshakebipartiteadjacencyisomorphism