AMS 303, Graph Theory

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

 

Course Materials for Fall 2022:

"Applied Combinatorics", by Alan Tucker, 6th edition, published by Pearson; ISBN: 9780558982478; AND

"Introduction to Graph Theory", by Robin Wilson, 6th Edition, John Wiley & Sons; ISBN: 9780273728894

 

AMS 303 Instructor Page

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

Learning Outcomes for AMS 303, Graph Theory

1.) Develop skill with proofs in graph theory (this is the only Applied Math course that teaches proofs), including:
        * the careful use of definitions and stated conditions, and their consequences;
        * direct arguments;
        * indirect arguments, i.e., proof by contradiction;
        * proof with generalized figures.

2.) Examine graph theory topics in greater depth (than AMS 301) with a focus on studying and extending theoretical results:
        * general graph properties;
        * planar graphs;
        * graph coloring, including edge and face coloring.

3.) Understand the theory behind Polya’s Enumeration Formula and use this understanding in applied problem-solving.

4.) Develop the network algorithms for:
        * maximal minimal flows;
        * maximal matching; 
        * the transportation problem.

5.) Understand the set-theoretic constructions underlying the theory of progressively finite games and apply this knowledge to develop winning strategies for such games:
        * kernel of a game;
        * level-by-level construction;
        * Grundy functions;
        * direct sums of games, including Nim.

6.) Use combinatorial reasoning to efficiently solve cryptograms based on keyword transpose encodings; extend this reasoning to solve polyalphabetic codes.