|
|
|
Nov 27, 2024
|
|
MATH 485 - 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.
Recommended Preparation: MATH 330.
Units of Lecture: 3
Student Learning Outcomes:
Upon completion of this course:
1. Students will be able to 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. Students will be able to demonstrate an understanding of the concept of computational complexity for algorithms, including the use of “Big O” notation.
3. Students will be able to 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. Students will be able to 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. Students will be able to 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)
|
|
|