CMU Campus
Undergraduate Programs      
Undergraduate Home Admissions and Financial Aid Research Opportunities Other Opportunities Degree Programs Course Descriptions Current Courses Honors Program Applying to Graduate School After Graduation Math Links
Undergraduate Courses 21-484
Graph Theory

Spring: 9 units

Graph Theory uses basic concepts to approach a diversity of problems and nontrivial applications in operations research, computer science and other disciplines. It is one of the very few mathematical areas where one is always close to interesting unsolved problems. Topics include graphs and subgraphs, trees, connectivity, Euler tours and Hamilton cycles, matchings, graph colorings, planar graphs and Euler's Formula, directed graphs, network flows, counting arguments, and graph algorithms. 3 hrs. lec. Prerequisites: ( 15-241 or 21-228 ) and ( 21-241 or 21-341 ) or permission of instructor.