Week 13
Modelling Structure: Graph Theory

Business

The start of the week email. No need to reread it if you received it. It's just linked here in case anyone accidentally deleted it (it's happened before 🥺).

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:

Exercise Set 12 Part 1: Graph theory essentials Problems and Solutions.

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:

Exercise Set 12 Part 2: Graph theory with matrices Problems and Solutions.

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 🐣

This Friday is Good Friday, a stat holiday, so no "class" today! Enjoy your day.

All the exercises in one place

All due by 4 pm Tuesday April 6.

Exercise Set 12 Part 1: Graph theory essentials Problems and Solutions.

Exercise Set 12 Part 2: Graph theory with matrices Problems and Solutions.

Assignment

Assignment 11 is posted. Due by 4 pm Friday April 9. 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.) Email is preferred, but you can also submit your work through Moodle.
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 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

Week 13Modelling Structure: Graph Theory