Math 442  201, 2017WT2, JanApr 2018
Optimization in Graphs and Networks
Announcements
Announcements will be posted here from time to time. Please check
regularly.

Midterm details now up!
 Don't forget UBC will be closed February 12th, so no office
hours that day. Please email me instead.
 Congratulations on your midterm average of 80%! Enjoy your
candy!
 Here is the link to the Youtube
video about the 4 colour theorem  thanks to Kristian for
sharing it.
 Don't forget UBC will be closed April 2nd, so no office hours
that day. Please email me instead.
 The course will be complete April 5th, so no office hours at
4pm.
 Maxflow mincut was inspired by the Cold War. Thank you to
Eric for this lead. Here is a blog
post with references.
Lecture details
Lecturer: S van
Willigenburg, Math 208, 8222630, steph at math splotch ubc
splotch ca.
Location: TTh 14.0015.30 CHEM C124.
Web page: http://www.math.ubc.ca/~steph/442/442.html
Office hours: Mon 1011am, Thur 45pm, 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 emphasis both
on proof and algorithmic techniques. Topics include tours and
graphs, planarity, graph colouring, trees, shortest paths, flows,
matchings. Prerequisite is Math 340.
Text
Robin J Wilson, Introduction to Graph Theory (5th Edition),
Pearson. ISBN13: 9780273728894. This text is optional and
contains sketches of some of the proofs plus additional practice
exercises. Other books on the subject can also be found in the
library around QA 166.
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 except in very unusual circumstances. We
will, however, drop the lowest homework grade.
Exams
Midterm,
Tuesday 6th February.
Final
exam, Thursday 19th 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 makeup or alternate exams, so make
sure you do not make travel plans, work plans etc that will
conflict. Valid documentation must be provided within 72 hrs if
any consideration is to be taken for a missed midterm.
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 will be expected to
perform calculations and construct rigorous proofs involving
fundamental ideas of the course.
Working together and academic integrity
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
 maximum benefit from a homework problem if you work hard on it
alone before combining your ideas with someone else's,
 no benefit from one person just telling another how to do a
problem.
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 a violation of UBC's Academic
Integrity
Code. We take academic integrity very seriously and
will follow university procedures in all cases of suspected
cheating  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 xerox a random sample of exam books 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 4th.
Assignment
2, due Thursday January 11th.
Assignment
3, due Thursday January 18th.
Assignment
4, due Thursday January 25th.
Assignment
5, due Thursday February 1st.
No assignment due Thursday February 8th due
to midterm.
Assignment
6, due Thursday February 15th.
Assignment
7, due Thursday March 1st.
Assignment
8, due Thursday March 8th.
Assignment
9, due Thursday March 15th.
Assignment
10, due Thursday March 22nd.
Assignment
11, due Thursday March 29th.
Assignment
12, due Thursday April 5th.
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
Solution
11
Solution
12
Other handouts
Here are some more study materials I found to help, or might be
interesting.
Other useful links