Lecture Notes on Graphs
Read: Lehman, Leighton, and Meyer: 10.1, 10.2, 10.4, 10.6, 10.8. 12.1, 12.3, 12.7, 12.8, 12.11.
Notes on graphs in general (pdf)
Notes on topological sorting (pdf)
Graphs
We will see what graphs are. Graphs consist of nodes and edges between nodes.
We will see simple graphs (edges are lines) and directed graphs (edges are arrows).
We learn about paths, cycles, loops.
We learn about what a tree is (in the context of graphs).
Euler tours
We will learn about Euler tours (Eulercykel). See Problem 10.7.
Topological sorting
We will learn about topological sorting. See Section 10.5.1 and the Notes on topological sorting.