Week 12
Modelling Structure: Graph Theory
Business
⦿ Monday
What graph theory is: Introduction and background
- Introduction to Graph Theory Video 4:56
- The graphs of Graph Theory aren't like the ones you are used to, though I have drawn some from time to time. This video also goes over the jargon and nomenclature we use to describe and refer to graphs.
- The Birth of Graph Theory Video 6:58
- Graph Theory has an interesting origin story. Watch this if you're curious.
- General Applications of Graph Theory Video 11:25
- This narrated slide show describes some of the many applications of graph theory.
- Applications of Graph Theory in the Life Sciences Video 11:31
- This narrated slide show describes two applications of graph theory in the life sciences: Trophic webs, and Landscape connectivity.
Spanning Trees
- Spanning trees PDF 1 page
- Hand drawn notes explaining what spanning trees are. Because before we try to find minimal spanning trees, we need to know what they are.
Minimal Spanning Tree On-the-graph
- MST example done on-the-graph Pencast video 4:35 | PDF
- The MST algorithm is simple enough you might be able to learn it just by watching me do these two examples. But if not there are the detailed notes below to refer to.
- Minimal Spanning Tree Algorithm: On-the-graph PDF 4 pages
- Detailed notes on how to find the minimal spanning tree of a weighted graph.
Shortest Route Algorithm On-the-graph
- Shortest Route example done on-the-graph Pencast video 9:44 | PDF
- The shortest route algorithm involves some fussy bookeeping. You might want to skim the notes below before watching the example in this video.
- Shortest Route Algorithm: On-the-graph 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:
§6.1-6.3 in Chapter 6 of College Mathematics for Everyday life by Inigo, Jameson, Kozak, Lanzetta, and Sonier.
Chapter 6: Graph Theory in Math in Society by David Lippman.
5: Graph Theory in Combinatorics and Graph Theory by David Guichard.
⦿ Wednesday
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.
⦿ Friday
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.
Exercises
No exercises on Hamiltonian Circuits! Use this gifted time to catch up.
Supplementary resources:
§6.6: Hamiltonian Circuits and the Traveling Salesman Problem in Math in Society by David Lippman.
Assignment
Assignment 11 is posted. Due by 1 pm Friday March 29. Note that the problems are worth different numbers of marks. Use your time wisely.
- You can hand in work done by hand to me in class or in dropbox A19.
- Excel or other binary files should be sent as file attachments to an email message.
- 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 A11_firstname.pdf, e.g.
A11_Tim.pdf
If you have to submit multiple files, add a suffix number to each, e.g.
A11_Tim_1.pdf
A11_Tim_2.pdf