Math 38 - Spring 2005
Dartmouth College
home
general information
syllabus
homework
office hours
professor
course
description |
textbook |
exams
|
scheduled lectures |
homework policy |
disabilities |
grades |
honor principle |
math department |
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).