Course Description | ||||||||||||
A graph is a mathematical structure used to model pairwise relations between objects. A "graph" is made up of "vertices" and "edges" that connect the vertices. The first paper on graph theory was published by Euler in 1736 on the seven Bridges of Königsberg. In this course we will cover the fundamental concepts of Graph Theory: simple graphs, digraphs, Eulerian and Hamiltonian graphs, trees, matchings, networks, paths and cycles, graphs colorings and planar graphs. Famous problems in Graph Theory include: Minimum Connector Problem (building roads at minimum cost), the Marriage Problem (matching men and women into compatible pairs), the Assignment Problem (filling n jobs in the best way), the Network Flow Problem (maximizing flow in a network), the Committee Scheduling Problem (using the fewest time slots), the Four Color Problem (coloring maps with four colors so that adjacent regions have different colors), and the Traveling Salesman Problem (visiting n cities with minimum cost). Graph theory has many applications to a many other subjects and areas of mathematics, for example, in computer science it can be used to represent networks of communication, data organization, computational device, the flow of computation, etc. The objectives of the course are:"Mathematics is not for spectators; in order to gain in understanding, confidence, and enthusiasm one has to participate." M.A. Armstrong | ||||||||||||
Exams | ||||||||||||
| ||||||||||||
Grades | ||||||||||||
The course grade will be computed as follows:
Students will be graded on class participation. Of course it is difficult to participate if one does not come to class at all, and so habitual absence will also be reflected in the class participation grade. | ||||||||||||
Homework Policy | ||||||||||||
Written homework will be assigned daily and will be collected once a week at the beginning of class.
| ||||||||||||
Textbook | ||||||||||||
Douglas B. West, Introduction to Graph Theory,
Second Edition, Prentice-Hall.
The home page of the textbook can be found here (Links to an external site.) | ||||||||||||
Honor Principle | ||||||||||||
Students are encouraged to work together to do homework problems. What is important is a
student's eventual understanding of homework problems, and not how that is achieved.
The honor principle on homework: What a student turns in as a homework solution is to be his or her own understanding of how to do the problem. Students must state what sources they have consulted, with whom they have collaborated, and from whom they have received help. It is a violation of the honor code to copy solutions from problems posted on the web or book or any other source. The solutions you submit must be written by you alone. Any copying (electronic or otherwise) of another person's solutions, in whole or in part, is a violation of the Honor Code. For example, it is a breach of the honor code to read the solutions of someone else in order to write your solution. The honor principle on exams: Students may not give or receive assistance of any kind on an exam from any person except for the professor or someone explicitly designated by the professor to answer questions about the exam. If you have any questions as to whether some action would be acceptable under the Academic Honor Code, please speak to me I will be glad to help clarify things. It is always easier to ask beforehand than to have trouble later! | ||||||||||||
Disabilities and Religious Observances | ||||||||||||
Students with disabilities enrolled in this course and who may need disability-related classroom accommodations are encouraged to
make an appointment to see your instructor before the end of the second week of the term. All discussions will remain confidential,
although the Student Accessibility Services office may be consulted to discuss appropriate implementation of any accommodation requested.
Some students may wish to take part in religious observances that occur during this academic term. If you have a religious observance that conflicts with your participation in the course, please meet with your instructor before the end of the second week of the term to discuss appropriate accommodations. |