Lectures:

Tuesdays & Thursdays 10:05-11:25

Chase Building 319

Resources:

(REQUIRED) TEXTBOOK:

    Graph Theory and its Applications, J.L. Gross & J. Yellen,

    Chapman & Hall/CRC, 2nd Edition, ISBN 1-58488-505-X.

    * Available at the Dalhousie Bookstore.

COURSE WEB PAGE:

    http://www.mathstat.dal.ca/~siegel/math3330/

Course description:

The development of the Internet and the World Wide Web has changed our outlook on the world.  Science has followed suit with an increased emphasis on the study of networks.  However, mathematicians have studied networks for over one hundred years.  A network, to a mathematician, is a graph, and graph theory is a fertile research area on the cross-section of mathematics and computer science.

This course offers an introduction to graph theory, with an emphasis on applications and modelling.  Topics include: paths and cycles, shortest route problem, connectivity and trees, minimum spanning trees, network flow, planar graphs, matchings, assignment problem, graph colouring, Hamiltonian cycles and the Traveling Salesman Problem.

Topics to be covered include (but are not limited to):

1. -Paths, cycles and the concept of diameter
   

2. -Shortest paths
   

3. -Connectivity, strong connectivity & connected components
   

4. -Connectivity and spanning trees
   

5. -Minimum flow & maximum cut
   

6. -Graph colouring
   

7. -Graph models
   

Evaluation:

Assessment of your course performance will be based on assignments, a group presentation, a midterm exam, and a final exam.  Final grade will be determined be the following Grading Scheme.

GRADING SCHEME:

    Assignments    25%

    Presentations   15%

    Midterm test    25%

    Final exam      35%

FINAL GRADES:

    A+    90 - 100

    A      85 - 89.9

    A-     80 - 84.9

    B+    75 - 79.9

    B      70 - 74.9

    B-     65 - 69.9

    C+    62 - 64.9

    C      58 - 61.9

    C-     55 - 57.9

    D      50 - 54.9

    F       < 50

Assignments:

Assignments may be done individually or in teams of two.  If an assignment is handed in by a team, it is understood that both members have contributed equally to all questions on the assignment.  Both members will receive the same mark.  Assignments must be handed in on or before the due date, by start of class.  Late assignments will be penalized.  Assignment solutions will be posted on the course website as soon after class end as possible.  After that point, late assignments will not be accepted.  Plagiarism will be prosecuted.

Presentations:

During the term, there will be a series of short presentations scheduled that will be given by students.  If a student is absent during scheduled presentations, his or her own presentation mark may be affected.

Midterm Test:

A 90-minute, in-class midterm test will be given in the week or two following the Feb. 22-26 study break.  The precise date will be set on or before February 2nd.

Final Exam:

The final exam will be a 3-hour exam held during the scheduled exam period between April 12th and the 24th.  The location, date and time of the exam will be scheduled by the registrar. 

Academic Accomodations:

Students with disabilities are encouraged to register as quickly as possible at the Student Accessibility Services if they wish to receive academic accommodations.  To do so, please phone 494-2836, email access@dal.ca , drop in at the new Mark A. Hill Accessibility Centre or visit the website at www.studentaccessibility.dal.ca .  Students are also reminded that, for your convenience, all forms are now available on their website.