Search

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.

PrerequisiteAMS 301

3 credits

Course Materials for Spring 2021:

"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

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.