Math 442 - 201, 2019WT2, Jan-Apr 2020

Graphs and Networks

Announcements

Announcements will be posted here from time to time. Please check regularly.
  1. The course syllabus is available here.
  2. Midterm details now up!
  3. Kuratowski's original paper.
  4. No office hours on Monday February 24th due to prior UBC training commitment. Please email me if you have a question.
  5. Congratulations on your midterm median of 78%! Enjoy your cookies and midterm break. All remaining uncollected midterms are in the box outside Math 208 to collect at your convenience.
  6. Due to moving online there will no longer be physical office hours but please email me and I am happy to help!
  7. 26/3 Updated grading scheme because of Faculty of Science restrictions:
  8. Remaining course content:

The topics for the remainder of term are as follows, and the readings are taken from Robin J Wilson, Introduction to Graph Theory (4th Edition) freely available from Edinburgh University and posted here for you. The book is not as detailed as my notes but gives enough detail for you and though dense is more legible. In order to support you further, the regular lecture time after the assigned reading day will be devoted to a flipped classroom and questions on the assigned reading and will be on Collaborate Ultra.

Textbook.

House Rules Handout.

NEW To help facilitate a productive class, few tips on Netiquette.

Week
Topic
Page reference
Reading date
Discussion date
Handout
10
Spanning tree definition
p44
Tuesday 17/3
Thursday 19/3
Here

Counting trees and
Cayley's theorem
p47-49
Theorem 10.1




Prufer sequences
- Prufer sequences from trees
- Trees from Prufer sequences
First proof of
Theorem 10.1




Spanning trees
of the complete graph
p50
Corollary 10.2
Thursday 19/3
Tuesday 24/3
Here

Searching trees
p56-57




Shortest path problem and
weighted graphs
p38-39



11
Travelling salesman problem (TSP)
p41
Tuesday 24/3
Thursday 26/3
Here

Minimum spanning tree (MST) aka
minimum connector problem
p52-53




Finding a lower bound for TSP using MST
p53




Directed graphs (digraphs)
p100-102 up to end
of Theorem 22.1
Thursday 26/3
Tuesday 31/3
Here

Eulerian digraphs
p105 up to end
of Theorem 23.1



12
Longest path
p102-103
Tuesday 31/3
Thursday 2/4
Here

Network flows
p126-127



13
Further questions
N/A
N/A
Tuesday 7/4
Email me before
2pm to meet


Lecture details

Instructor: S van Willigenburg, office: Math 208, tel: (604) 822-2630, email: steph at math splotch ubc splotch ca.
Location:  TuTh 14.00-15.20  BIOL 2200.
Web page: http://www.math.ubc.ca/~steph/442/442.html
Office hours: Mon 10-11am, Thur 4-5pm, 15 mins just after class, and by appointment (not Wednesday). You can also email me anytime.

Course description

This is an introduction to graph theory. There will be an emphasis on proof techniques. Topics include tours and graphs, planarity, graph colouring, trees, shortest paths, and algorithms.  Prerequisite is 3rd year standing and one of MATH 220, MATH 223, MATH 226 or CPSC 221.

Text

Robin J Wilson, Introduction to Graph Theory (5th Edition), Pearson. ISBN-13: 978-0-273-72889-4.  This text is optional and contains sketches of some of the proofs plus additional practice exercises. There will also be a copy available for you to view during office hours and multiple copies in the library so purchasing the book is not necessary.

Homework

There will be a weekly homework assignment due on Thursdays at the start of class. The homework is the most important part of the course as most of your learning will take place while doing it.   We will not accept late homework. We will, however, drop the lowest homework grade.

Exams

Midterm, Tuesday 11th February.
Final exam, Wednesday 15th April.

Calculators, books, notes etc are not permitted in either exam. Please bring your student ID to both exams.

Please note that there are no make-up or alternate exams, so make sure you do not make personal travel plans or work plans etc that will conflict. 

Any student who misses the midterm is to present to their instructor the Department of Mathematics self-declaration form for reporting a missed assessment within 72 hours of the midterm date. This policy conforms with the UBC Vancouver Senate's Academic Concession Policy V-135 and students are advised to read this policy carefully.

Grading

Your grade will be based on the homework (10%), the midterm (30 or 40%), and the final (60 or 50%), whichever gives you the best grade.

Since this is a Mathematics Majors course, there is a median grade of around 68% and students are expected to perform calculations and construct rigorous proofs involving fundamental ideas of the course.

Working together and academic misconduct

Homework: We have no objection to collaboration on the homework, provided that it is done in a way that maximizes the benefit of the homework to all people involved. It is our experience that you get Regardless of whether you arrive at solutions in collaboration with others or alone, the paper that you turn in with your name on it should represent your own solutions, written in your own words.

In particular, you may not simply copy someone else's homework and turn it in as your own. Similarly, copying solutions that you might find on the web or from some other source is illegal.

These will all be treated as academic misconduct. We take all academic misconduct very seriously and will follow university procedures in all cases - disciplinary measures can result in expulsion.

Exams: There is anecdotal evidence that quite a bit of cheating occurs on campus. In an effort to prevent one common form of cheating, we will photocopy a random sample of exams before returning them.

Class etiquette

Use of cell phones (in any manner), laptops, smartphones, tablets and other electronic devices during class is highly inappropriate, as it is distracting and disrespectful to fellow students and the instructor. Chatting with neighbours, even when whispered, is equally inappropriate. If you have a question then please ask the instructor so the whole class may benefit too.

Arriving late and leaving early is also discouraged. If it happens then please enter/leave the room silently and do not disrupt the other students or instructor. Thank you.

Assignments

Assignment 1, due Thursday January 9th.
Assignment 2, due Thursday January 16th.
Assignment 3, due Thursday January 23rd.
Assignment 4, due Thursday January 30th.
Assignment 5, due Thursday February 6th.
No assignment due Thursday February 13th due to midterm.
Assignment 6 due Thursday February 27th.
Assignment 7 due Thursday March 5th.
Assignment 8 due Thursday March 12th.
Assignment 9 due Thursday March 19th.
Assignment 10 due Thursday March 26th.
Assignment 11 due Thursday April 2nd.

Solutions

These are to help you study. Please make sure your solutions include full details and citations.

Solution 1
Solution 2
Solution 3
Solution 4
Solution 5
Solution 6
Solution 7
Solution 8
Solution 9
Solution 10

Other handouts

Here are some more study materials I found to help, or might be interesting.

Other useful links