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; ISBN: 9780471735076 and Introduction to Graph Theory, by Robin Wilson, Fifth Edition, John Wiley & Sons; ISBN: 9780273728894
THIS COURSE IS OFFERED IN THE SPRING SEMESTER ONLY
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