Week 12
Modelling Structure: Graph Theory
Business
⦿ Monday
Representing graphs using matrices
- From graph to matrix Pencast video 8:10 | PDF
- How to represent a graph in a matrix, showing two examples: an undirected graph, and a directed graph.
- From matrix to graph Pencast video 8:16 | PDF
- What can we learn by examining the matrix representation of a graph?
How to draw the visual graph given its matrix representation. - Matrix representations of graphs PDF 3 pages
- Notes on how to represent graphs using matrices.
Minimal Spanning Tree In-the-matrix
- MST example done in-the-matrix Pencast video 4:48 | PDF
- Not quite as easy as doing it on the graph, but might still be simple enough to be learned by watching me do these two examples.
- A larger MST example done in-the-matrix Pencast video 5:22 | PDF
- A second, slightly larger example of MST done in-the-matrix.
- Minimal Spanning Tree Algorithm In-the-matrix PDF 2 pages
- Detailed notes on how to find the minimal spanning tree of a weighted graph in its matrix representation.
Shortest Route In-the-matrix
- Shortest Route example done in-the-matrix Pencast video 5:52 | PDF
- There's still fussy bookeeping, but some students find it easier to do it in-the-matrix than on-the-graph.
- Shortest Route Algorithm: In the matrix PDF 3 pages
- Detailed notes on how to find the shortest route from one node to another in a weighted graph.
Exercises
If you're comfortable with the topics above you're ready to work on:
Supplementary resources:
I have not been able to find an online source on MST and Shortest Route in-the-matrix that is both free and introductory, so my fingers are crossed that the supporting PDF notes are sufficient. The classic introductory resource is Introduction to Operations Research by Frederick S. Hillier and Gerlad J. Lieberman, 2004. The YukonU library used to have copies of earlier editions, but it doesn't seem to anymore.
⦿ Wednesday
Hamiltonian Circuits
- Hamiltonian Circuits Pencast video 15:48
- Welcome to one of the frontiers of mathematics. A hamiltonian circuit is one that visits every vertex exactly once. And no one knows a quick way of determining if there is one in a graph.
- Hamiltonian Circuits and Algorithm Complexity PDF 4 pages
- A complement to the pencast above. Covers some of the same topics, but some new ones as well. In particular the ideas of algorithms, algorithmic complexity, and heuristics.
Fun Thing 1: The Rule of 72
- The Rule of 72 Pencast video 11:42
- The rule of 72 is a very handy heuristic approximation.
Fun Thing 2: Game Trees and Pitcher Problems
- Game Trees and Pitcher Problems Pencast video 17:11
- Game trees are what computers use to play games against us: Trees that map out and weight the possible moves in a game. They can also be put to use to solve Pitcher Problems. Coming soon to an assignment near you.
Exercises
No exercises on these topics. They don't lend themselves to little problems, but they do appear on the assignment!
Supplementary resources:
Two articles on The Rule of 72 at Better Explained and Wikipedia.
The Wikipedia article Game tree is as good an open resource as I could find.
⦿ Friday
- Good Friday Holiday: No Class 😔
Assignment
Assignment 12 is posted. Due by 1 pm Wednesday April 15. Given the back to back short weeks, this assignment also covers next week's material. So you probably can't do all the problems yet — but you can get started! Note that the problems may be worth different numbers of marks. Use your time wisely.
Submit PDF files of work done by hand, or in a word processor. (Let me know if you
are unsure
how to create these.)
Excel or other binary files should be sent as file attachments.
Google sheets can be submitted by sharing a link to them.
Work done in Desmos can be submitted by sharing a link to your saved graph.
Name the file you submit A12_firstname.pdf, e.g.
A12_Tim.pdf
If you have to submit multiple files, add a suffix number to each, e.g.
A12_Tim_1.pdf
A12_Tim_2.pdf