Catalog Description: Paths and circuits, trees and tree based algorithms, graph coloring, digraphs, network flows, matching theory, matroids, and games with graphs.
Prerequisite: AMS 301
3 credits
Textbooks: Applied Combinatorics, by Alan Tucker, Fifth Edition, John Wiley & Sons; Introduction to Graph Theory, by Robin Wilson, Third Edition, John Wiley & Sons; Elementary Cryptanalysis, by Abraham Sinkov, Second Edition, Math. Assoc. of America
THIS COURSE IS OFFERED IN THE SPRING SEMESTER ONLY
Spring 2010 Section
52490 LEC 01 TUTH 11:20-12:40PM Loc: Physics P118 Inst: Alan Tucker AMS 303 Webpage
Topics
1. General Graph Theory Foundations (Wilson, Sect. 2,3,5) – 4 class hours
2. Planar Graphs and Duality (Wilson, Sect. 12, 13, 15) – 6 class hours
3. Graph Coloring (Wilson, Sect. 17,19,20) –6 class hours
4. Polya’s Enumeration Formula (Tucker, Chap 9) – 4 class hours
5. Network Flows (Tucker, Chap. 4) – 8 class hours
6. Graphs and Games (Tucker, Chap. 11) – 2 class hours
7. Cryptanalysis (Sinkov, Chap. 1,2,3) – 8 class hours
8. Examinations and Review – 4 class hours