Spring 2010

MTHS 622
Graph Theory with Applications

Collins,Karen L.

01/25/2010 - 05/07/2010
Thursday 07:00 PM - 09:30 PM

A graph is a set, called a vertex set, along with a collection of unordered pairs of vertices, called edges. Because the definition of a graph is so simple, graphs can be used to model many real life situations. For instance, given a local airline service between several cities, one could ask for the shortest path (or lowest cost route) between two particular cities. We can represent this as a graph by assigning a vertex to each city, and an edge between two vertices if the corresponding cities have a direct flight between them. Each edge can be given a weight, which could be the distance between the cities, or the cost of the flight between them. Given two particular cities, Dijkstra discovered an elegant algorithm to determine the shortest (or least expensive) path between them. Graphs are used to model many such situations, including network systems, assignments of personnel, job sequencing, and storage planning.

This course will begin with basic concepts of graphs, and continue with trees, connectivity, matchings, planar graphs and coloring. Each new concept will lead to a new application.There will be regular homework problems, and student presentations on the last day of class.

Students do not need any specific background other than high school mathematics.

The text for this course will be Graph Theory with Applications by J. A. Bondy and U. S. R. Murty (this book is available free online).

Grades will be based on regular problem sets and one or two class presentations.

Students do not need any specific background other than high school mathematics, but should review the concepts of functions, algorithms and induction.

Course tuition: $2022.

Enrollment is limited to 18 students.

This course is open to auditors.

A syllabus for this course is available at:
Course Syllabus

Karen Collins (B.A., Smith College; M.A., Wesleyan University; Ph.D., MIT) is professor of mathematics. Click here for more information about Karen Collins.


Consent of Instructor Required: No

Format: Seminar

Level: GLSP Credits: 3 Enrollment Limit: 18

Texts to purchase for this course:
J. A. Bondy and U. S. R. Murty, GRAPH THEORY WITH APPLICATIONS. This text can be downloaded for free here: GRAPH THEORY WITH APPLICATIONS

Register for Courses

Contact glsinquire@wesleyan.edu to submit comments or suggestions. 
Copyright Wesleyan University, Middletown, Connecticut, 06459