MATH 471
COMBINATORICS AND GRAPH THEORY

1. Catalog Entry

MATH 471. Combinatorics and Graph Theory
Three hours lecture (3).

Prerequisite: CPSC 122 or ITEC 122 and MATH 460 (or equivalent)

Fundamental ideas of combinatorics and graph theory, permutations and combinations, inclusion and exclusion, ordinary generation function, recurrence relations, graphs and digraphs, trees, networks.

2. Detailed Description of Content of Course

The following topics in combinatorics and graph theory will be covered:

a) Permutations and combinations
b) The principle of inclusion and exclusion
c) Ordinary generating functions
d) Recurrence relations
e) Graphs and digraphs
f) Euler and Hamilton paths
g) Trees
h) Weighted trees and prefix codes
i) Spanning trees
j) Networks; the Max-flow Min-cut theorem

If time permits, instructors may add a computational component to the course.

3. Detailed Description of Conduct of Course

Most instructors will use the lecture method. Some may require students to work together in small groups. In all sections students will be asked to work problems assigned as homework. If a computational component is included, instructors may require students to work at computer terminals.

4. Goals and Objectives of the Course

To provide students of the mathematical sciences with the important ideas and techniques of combinatorics and graph theory.

5. Assessment Measures

Graded tasks may include tests, quizzes, homework exercises, programs, class participation, and attendance.

6. Other Course Information

None.

7. Review and Approval

DATE ACTION APPROVED BY
Sept. 2001 Review Stephen Corwin, Chair