University General Course Catalog 2018-2019 
    
    Mar 29, 2024  
University General Course Catalog 2018-2019 ARCHIVED CATALOG: LINKS AND CONTENT ARE OUT OF DATE. CHECK WITH YOUR ADVISOR.

Add to Portfolio (opens a new window)

MATH 685 - Graph Theory & Combinator

(3 units)
Counting rules; generating functions; recurrence relations; inclusion-exclusion; pigeonhole principle; Ramsey theory; fundamental graph theory concepts (connectedness, coloring, planarity); Eulerian/Hamiltonian chains and circuits; matching.

Units of Lecture: 3
Offered: Every Fall

Student Learning Outcomes
Upon completion of this course, students will be able to:
1. solve simple and complex counting problems, by using the addition and product rules, recognizing permutation/combinations with and without replacement, rephrasing as occupancy problems, and/or using the inclusion-exclusion principle/derangements.
2. demonstrate an understanding of the concept of computational complexity for algorithms, including the use of “Big O” notation.
3. demonstrate an understanding of the main concepts of graph theory, including graphs versus digraphs, connectedness, graph coloring, planarity, as well as the properties of bipartite graphs, complete graphs, and trees.
4. demonstrate knowledge of some of the great historical problems and results in graph theory/combinatorics, including the four-color problem, the Konigsberg bridge problem, Euler’s formula, the travelling salesman problem, the hatcheck problem, Kuratowski’s theorem, Ramsey’s theorem, and the solution to the Fibonacci recursion.
5. make simple “discrete” arguments/proofs, such as using mathematical induction or making “combinatorial arguments”.


Click here for course scheduling information. | Check course textbook information



Add to Portfolio (opens a new window)