# MAT 460 Graph Theory and Algorithms

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

• Required: MAT 211, MAT 271, and MAT 241 or CSC 121 or CSC 115, or equivalent with grade C or better.
• Recommended: MAT 281 with a grade of a C or better.

### Textbook

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

### Learning Outcomes

After completing MAT 460, students will be able to:

• Identify properties and characteristics of graphs
• Write proofs of theorems involving graph concepts and definitions
• Reframe an assortment of real-life problems in terms of graph theoretic problems
• Decide whether two differently presented graphs are the same (isomorphic) from a graph theoretical perspective
• Execute graph algorithms, both by hand, and with the assistance of a computer
• Determine whether a given applied or pure graph problem can be solved by an efficient algorithm, and if so, to describe such an algorithm

### 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

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.