Week 1 |
Jan 6 |
Syllabus
Introduction to Graph Theory
(slides 1-21)
-
Chapter 1 (1.1, 1.3-1.6) and Appendices A.2-A.3
-
Ch. 1.2 is optional; it's an overview of topics in the book.
|
Jan. 8 |
|
Jan. 10 |
-
slides continued (rest of slides)
Subgraphs, walks, Eulerian and Hamlitonian graphs
(slides 1-17)
-
Chapters 1.7 and 2 (2.1-2.6; skip 2.7)
|
Week 2 |
Jan. 13 |
|
Jan. 15 |
|
Jan. 17 |
-
slides continued (rest of slides)
|
Week 3 |
Jan. 20 |
Martin Luther King, Jr. Holiday
|
Jan. 22 |
Trees
(slides)
Spanning tree algorithms
(slides 1-3),
(worksheets)
-
Chapter 3.2-3.4
-
Please print out the worksheets at full size to facilitate note taking in lecture.
|
Jan. 24 |
-
slides continued (4-51) + worksheets
-
The DFS example on the slides has a mistake, so I used worksheets on the projector instead. There were also several other examples on the worksheets on the projector. See the 1/24 and 1/27 podcasts to review it.
|
Week 4 |
Jan. 27 |
-
slides continued (rest of slides and worksheets)
Weighted graph algorithms
(slides 1-14)
|
Jan. 29 |
|
Jan. 31 |
-
slides continued (rest of slides)
Connectivity
-
Will be on the chalkboard, not on slides.
-
Chapter 4.4-4.5 and 4.7.
Skip other parts of Chapter 4 for now (may do later in the quarter if time permits).
|
Campuswide deadline to drop without a "W"
|
Week 5 |
Feb. 3 |
-
Chapter 4 continued
-
Example for question asked in class about a graph with λ(G)<δ(G), namely, 1<2:
(drawing)
Matchings
-
Chapter 5 intro to matchings (on chalkboard)
|
Feb. 5 |
-
Chapter 5.1: Independent sets, matchings, vertex and edge covers
|
Feb. 7 |
Midterm
|
Week 6 |
Feb. 10 |
Matchings: Hall's Theorem, applications, and generalizations
(slides 1-24)
[slides revised 2/10 after class]
|
Feb. 12 |
-
slides continued (25-39, 57-61)
|
Feb. 14 |
-
slides continued (rest of slides)
|
Campuswide deadline to drop with a "W"
|
Week 7 |
Feb. 17 |
Presidents' Day Holiday
|
Feb. 19 |
Vertex and Edge Colorings
(revised slides 1-24, 45-48)
[slides revised again 2/23]
|
Feb. 21 |
|
Week 8 |
Feb. 24 |
Planar Graphs
(slides 1-16)
-
Chapter 7
-
Covering 7.1-7.3 in full, and parts of 7.4 and 7.6-7.8. Skipping 7.5.
|
Feb. 26 |
|
Feb. 28 |
-
slides continued (rest of slides)
|
Week 9 |
Mar. 2 |
The Max-Flow Min-Cut Theorem
(slides 1-31)
|
Mar. 4 |
|
Mar. 6 |
-
slides continued (rest of slides)
Stable Matchings: The Gale-Shapley Algorithm
(slides 1-8)
|
Week 10 |
Mar. 9 |
-
slides continued (up to 31)
|
Mar. 11 |
-
slides continued (rest of slides)
Extremal Graph Theory
(slides 1-26)
-
Chapter 9-9.2 (+ Ramsey Numbers, not in the book)
|
Mar. 13 |
|
Week 11 |
Wed. Mar. 18 |
Final exam, 3-6 p.m.
|