Catalog Description: Introduction to graph theory and combinatorial analysis. The emphasis is on solving applied problems rather than on theorems and proofs. Techniques used in problem solving will include generating functions, recurrence relations, and network flows. This course develops the type of mathematical thinking that is fundamental to computer science and operations research.
Prerequisites: AMS 210 or MAT 210 or AMS 361 or MAT303.
3 credits
Text: Applied Combinatorics, by Alan Tucker, 5th edition, John Wiley & Sons
ISBN# 9780471735076
AMS 301 Instructor page Lec 1
AMS 301 Instructor page lec 2
AMS 301 IS ALSO OFFERED DURING SUMMER SCHOOL. CHECK THE SUMMER SCHOOL BULLETIN FOR TIMES.
Topics
1. Basic concepts of graphs, graph models and isomorphism - 4 class hours.
2. Euler and Hamilton circuits and their applications - 3 class hours.
3. Graph coloring and its applications - 3 class hours.
4. Trees, their use in searching - 5 class hours.
5. Problems with permutations and combinations - 8 class hours.
6. Generation Functions - 5 class hours.
7. Recurrence Relations - 4 class hours.
8. Inclusion-Exclusion principle - 5 class hours
9. Examinations and Review – 5 class hours.