Graph Theory


Computer Science (66-4969) /Math (65-4150); Spring 2013

%
Instructor: Professor Goldberg
Class Hours and Place: Tue -- Fri; 2:00 - 3:50; SAGE 5510
Office Hours: Wednesday, 4:00 - 5:00; Lally Hall 302
Tel: 276-2609
e-mail: goldberg@cs.rpi.edu
url: http://www.cs.rpi.edu/~goldberg/13-GT/index.html
TAs: William Babbitt; Benno Lee
e-mail: babbiw@rpi.edu
e-mail: leeb5@rpi.edu
Office Hours: William: Thursday, 10:00 - 12:00; AE lounge
Benno: Monday, 3:00 - 5:00; AE 217
Textbook: Introduction to Graph Theory, Second edition
  by Douglas B. West, Prentice Hall 2001; ISBN: 0-13-014400-2
Prerequisite: MATH-2800 or equivalent
READ NOTES  in Discrete Mathematics


Graph Theory: preface

Graph Theory is a delightful playground for the exploration of proof technique in discrete mathematics, and its results have applications in many areas of the computing, social, and natural sciences. D. West, Introduction to Graph Theory

Teaching, Requirements and Grading

(PLEASE READ IT CAREFULLY).

Course outline. This course discusses fundamental concepts of Graph Theory and its applications in computer, social, and natural sciences. The topics include graphs as models; representation of graphs; trees; distances; matchings; connectivity; flows in networks; colorings; Hamiltonian cycles; and planarity. All concepts, methods, and applications will be presented through a sequence of exercises and problems.
Course objectives. The two main objectives of the course are
(1) to make students familiar with the most fundamental Graph Theory topics and results; and
(2) to teach the students the techniques of proofs and analysis.


Approximate Schedule


Date Topics
Jan 22 - Jan 25 Basic definitions: graphs; vertex degrees; paths; cycles;
Jan 29 - Feb 5 Trees; graceful labeling; minimum spanning trees;
Feb 5 - Feb 21 Matchings; independent sets; cuts, connectivity; blocks
Feb 21 - Mar 8 Network flows; application to optimal matchings in bipartite graphs 
March 19  First test 
Mar 22 - Mar 29 Eulerian and Hamiltonian cycles;
Apr 2 - Apr 12 Vertex coloring; 
Apr 23 - Apr 26 Edge coloring 
Apr 30 - May 3 Planar graphs 
May 7 Second test 




Student Learning Outcomes.

  • Knowledge of the most fundamental notions and results in Graph Theory; and
  • Problem solving skills; proof techniques.


    Requirements and Grading
    Students are encouraged to attend all classes. Your active in-class participation will be a substantial part of your learning process, and will be taken into consideration when final grades are determined. In-classes quizzes will be given with some regularity. Helpful exercises will often be recommended. Your solutions to them will not be graded, but you are welcome to consult with me or the TAs to check your solutions.

    Your grade will be based on several quizzes (up to ten) and two tests, the first of them in the middle of the term, and the second at the end of the term.

    Quizzes First test Second test
    30% 30% 40%

    The letter grade, to be reported to the registrar, will be assigned based on your final score according to the following rule:

    A A- B+ B B- C+ C C- D+ D F
    >95 91 - 95 87 - 91 83 - 87 80 - 83 76 - 80 72 - 76 68 - 72 64 - 68 60 - 64 < 60


    • For each in-class quiz, the students attending the class will be temporarily split into two member teams. The class will be given up to three problems, totaling up to three or four points towards the final grade. Every team will present a short written solution to every problem (and the names of the participants). After the write-ups are collected, if time permits, the solutions will be presented by the instructor. Else, the solution will be posted in one or two days after the quiz. It is your responsibility to read the posted solutions and compare them with your work.
    The grade for the missing quiz is a zero. For every student, the lowest of the grades for a quiz, in particular one missing quiz, will be replaced by the average of the remaining quiz grades. There will be no makeups for a quiz or a test, unless one makes a prior arrangement with the instructor or have a medical excuse supported by a document from a doctor. Students who know they are going to miss a test must notify me in advance. Special circumstances can be accommodated if I am notified about them in advance.
    Both tests are open-textbook but close-notes; extensive notes in the textbook may result in removing the textbook from the test.
    Policy on Academic Integrity: No collaboration is allowed during in-class tests. The evaluation of student performance is a service provided by Rensselaer. Attempts to undermine this service lower Rensselaer's reputation. Therefore, it is essential that academic honesty be preserved. Unless otherwise indicated, you should cooperate with one another in and outside of class on the solutions of problems. You may collaborate with your partner on reports. However, you may not collaborate on examinations or misrepresent another person's work as your own on examinations. You may not bring crib sheets to examinations, and you may not write on or alter examination materials that you submit for re-grading. Students who violate the spirit or letter of these rules are subject to penalties according to the principles outlined in the Rensselaer Handbook.