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)

Lecture Notes:

• Lecture Notes Thursday (scanned PDF) on simple graphs and Euler tours

• Lecture Notes Friday (scanned PDF) on Euler tours and directed graphs

---

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.