MAT 460 Graph Theory and Algorithms

This is a sample syllabus only. Ask your instructor for the official syllabus for your course.

Instructor:
Office:
Office hours:
Phone:
Email:

Course Description

The objective of this course is to study the conceptual, theoretical, and computational concepts of graph theory, along with examples of its applications to real-life problems. The topics covered will be: Graph concepts, definitions, and theorems. Modelling and algorithms with graphs. Isomorphisms, subgraphs, and representations of graphs. Trees, spanning trees, and shortest paths in graphs. Graph traversal problems.

MAT 460 meets three hours of lecture per week.

Prerequisites

Textbook

A. Stanoyevitch, Discrete Structures with Contemporary Applications, Chapman & Hall (2011)

Learning Outcomes

After completing MAT 460, students will be able to:

Course Outline

Week Topics
1 Overview of the subject with introductions to some key graph concepts and examples
2 Degree sequences of graphs, and an algorithm for determining whether a given sequence can be realized as the degree sequence of a simple graph
3 Digraphs, multigraphs, and modeling real-life problems with graphs
4 Distance related concepts in graphs
5 Subgraphs Exam #1
6 Graph and digraph isomorphisms
7 Matrix representations of graphs and applications of matrix operations
8 Trees (very important types of graph)
9 Spanning Trees and means of construction
10 Applications of spanning trees Exam #2
11 Tree Growing Algorithms
12 The traveling salesman problem, and related problems
13 Hamiltonian graphs
14 Network Flows
15 Review for final

Grading

Grades are based on homework, quizzes, in-class exams, a final exam, and special projects as determined by the instructor.

Attendance Requirements

Attendance policy is set by the instructor.

Policy on Due Dates and Make-Up Work

Due dates and policy regarding make-up work are set by the instructor.

Schedule of Examinations

The instructor sets all test dates except the date of the final exam. The final exam is given at the date and time announced in the Schedule of Classes.

Academic Integrity

The mathematics department does not tolerate cheating. Students who have questions or concerns about academic integrity should ask their professors or the counselors in the Student Development Office, or refer to the University Catalog for more information. (Look in the index under "academic integrity".)

Accomodations for Students with Disabilities

Cal State Dominguez Hills adheres to all applicable federal, state, and local laws, regulations, and guidelines with respect to providing reasonable accommodations for students with temporary and permanent disabilities. If you have a disability that may adversely affect your work in this class, I encourage you to register with Disabled Student Services (DSS) and to talk with me about how I can best help you. All disclosures of disabilities will be kept strictly confidential. Please note: no accommodation may be made until you register with the DSS in WH B250. For information call (310) 243-3660 or to use telecommunications Device for the Deaf, call (310) 243-2028.


Revision history:

Prepared by A. Stanoyevitch, spring 2010. Adapted for the web 3/4/2011 by G. Jennings.