Math 428, Section 1
Fall 2005
|
Schedule
| Week |
Date of Monday |
Topic / Section of book |
Homework |
Comments |
| 1 |
Aug. 29 |
Introduction and definitions. Notes. |
All problems on pages 6 and 7 of Wilson, except 1.4. Due
9/8. |
Classes start on Sept. 1. |
| 2 |
Sept. 5 |
More definitions and examples. Notes. |
page 14: 2.2, 2.3, 2.5, 2.8, 2.13(i); page 20: 3.3, 3.5,
3.6; Due 9/15. |
No class Monday (Labor Day). |
| 3 |
Sept. 12 |
Finish definitions and examples. Paths and connectivity. Cut
vertices and bridges. Notes. |
page 30: 5.2, 5.5, 5.6, 5.7, 5.9, 5.10; page 34: 6.3, 6.4;
Due 9/22. |
|
| 4 |
Sept. 19 |
Euler and Hamilton. |
page 34: 6.7; page 37: 7.3, 7.5, 7.9; page 41: 8.1, 8.2, 8.4,
8.5; Due 9/29. |
|
| 5 |
Sept. 26 |
Shortest path problem. |
page 46: 9.3, 9.5, 9.8, 9.9, 9.10, 9.11; page 51: 10.1,
10.5; Due 10/6. |
Midterm Thursday. |
| 6 |
Oct. 3 |
Trees. |
page 57: 11.1, 11.2, 11.3, 11.8, 11.9, 11.11; Due 10/13. |
|
| 7 |
Oct. 10 |
Spanning trees. Prufer codes. |
page 64: 12.1, 12.2, 12.4, 12.5, 12.13; page 69: 13.1, 13.3,
13.4, 13.5, 13.6; Due 10/24. |
Changed due date of homework to the 24th. Homework now
assigned on and due on Mondays. |
| 8 |
Oct. 17 |
DFS/BFS. Planar graphs. Polyhedral graphs. |
None. |
|
| 9 |
Oct. 24 |
Dual graphs. Infinite graphs. |
page 76: 15.2, 15.3, 15.5, 15.8, 15.10(i); page 80: 16.1,
16.4(i), 16.6; Due 10/31. |
|
| 10 |
Oct. 31 |
Coloring. |
page 85: 17.2, 17.4, 17.6, 17.8, 17.10, 17.11(i); page 92:
19.1, 19.3 (give an example which is not a cycle), 19.4; Due
11/7. |
|
| 11 |
Nov. 7 |
Chromatic polynomials. |
None. |
Midterm Monday. |
| 12 |
Nov. 14 |
Directed graphs. |
page 99: 21.2, 21.4; page 104: 22.1, 22.3, 22.4, 22.5; page
108: 23.3, 23.4, 23.6, 23.7; Due 11/21. |
|
| 13 |
Nov. 21 |
Markov chains. |
page 111: 24.1, 24.2, 24.3, 24.4(i)(ii); Due 11/28. |
Thanksgiving -- No class Thursday. |
| 14 |
Nov. 28 |
Matchings. |
page 114: 25.1, 25.2, 25.3, 25.4, 25.5, 25.6(i); |
|
| 15 |
Dec. 5 |
Network flows. Max-flow equals min-cut. |
page 126: 28.2, 28.5, 28.6; page 130: 29.1, 29.2, 29.3, 29.4,
29.5, 29.7(i); |
|
| 16 |
Dec. 12 |
Questions/catch-up. |
None. |
Last class and last office hours are on Monday, 12/12. Final
is Dec. 16 from 8-11 am. The location is SEC-206. |
|
|
|