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.
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 |
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.
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.
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.
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