Discrete Structures
Revised: November 2006
Course Description
Graph Theory: planarity, eulerian, hamiltonian, colorings, and trees. Enumeration: permutations, combinations, generating functions, recurrence relations, and inclusion-exclusion. Prerequisites: Junior standing or permission of the instructor. 3 credit hours.
Objectives
- To introduce students to terminology and concepts associated with graph theory and combinatorics.
- To enable students to develop proficiency in discrete mathematics problem solving through reasoning and combinatorial modeling.
Text
Alan Tucker, Applied Combinatorics (Fourth Edition), John Wiley & Sons, 2002.
Grading Procedure
Grading procedures and factors influencing course grade are left to the discretion of individual instructors, subject to general university policy.
Attendance Policy
Attendance policy is left to the discretion of individual instructors, subject to general university policy.
Course Outline
-
Chapter 1: Elements of Graph Theory (6 days)
All sections: Graph models, graph isomorphisms, edge counting, and planarity. -
Chapter 2: Covering Circuits and Graph Coloring (6 days)
All sections: Euler circuits, Hamiltonian cycles, graph coloring, and coloring theorems. -
Chapter 3: Trees and searching (5 days)
Sections 1 - 2: Properties of trees, depth-first and breadth-first searching, and spanning trees. Remaining topics may be covered at the instructor's discretion. - Chapter 4: Network Algorithms (Optional, at the instructor's discretion as time allows)
-
Chapter 5: Counting Methods for Selections and Arrangements (10 days)
Sections 1 - 4, and highlights of section 5: Basic counting principles, arrangements and selections, arrangements and selections with repetition, distributions, and binomial coefficients. -
Chapter 6: Generating Functions (4 days)
Sections 1 and 2: Generating function models, and calculating coefficients of generating functions. -
Chapter 7: Recurrence Relations (4 days)
Sections 1 - 3: Recurrence Relation models, divide-and-conquer relations, and solutions of linear recurrence relations. -
Chapter 8: Inclusion-Exclusion (4 days)
Sections 1 - 3: Counting with Venn diagrams, the inclusion-exclusion formula, and rook polynomials (if time allows).