Week 14
Graph Theory II

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 🍫

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

Wednesday

Matrix Multiplication

The last mathematical technique of the course(!) is matrix multiplication. Matrix multiplication will enable us to determine whether a graph is connected given its matrix representation, and be the basis for the Markov models we will look at next week.

If you prefer reading to watching you can start with the PDF notes at the end of the list below.

📹Scalars, vectors and matrices Pencast video 2:51

Scalar = a number. Vector = a list of numbers. Matrix = a table of numbers.

📹Adding and subtracting matrices Pencast video 3:05

Probably just what you would do intuitively.

📹Multiplying vectors Pencast video 4:41

Not intuitive! Be sure to view this before viewing "Multiplying Matrices" below.

📹Multiplying matrices Pencast video 5:41

Also not intuitive, it's a fairly involved set of steps. But they are mechanical so you can learn to carry them out.

📹Can all matrices be multiplied? Pencast video 2:42

Spoiler: No.

📹One last thing about vector multiplication Pencast video 3:58

Surprise! Unlike with numbers the order of multiplication can change the answer with matrices, i.e. A×B≠B×A.

📘Matrix Multiplication PDF 5 pages

Detailed notes on how to multiply matrices.

Graph reachability and connectedness

📹Adjacency matrices and connectedness Pencast video 18:50

Sorry this one is so long, there just didn't seem to be a natural place ot break it in to pieces.

📘Graph Reachability and Connectedness PDF 4 pages

Detailed notes on reachability and how to determine if a graph is connected from its matrix representation.

📹Using Excel to Calculate Reachability Matrices Screencast video 7:44

Walkthrough of using Excel for calculating adjacency matrices. tl;dr Use the MMULT() function.

💻Graph_Reachability.xlsx Excel File

Here's the Excel sheet developed in the video above, in case you want to download it as, oh I don't know, a starting point for an assignment maybe.

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.

The Rule of 72

📹The Rule of 72 Pencast video 11:42

The rule of 72 is a very handy heuristic approximation.

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.

The week's exercise (Yes, just one!)

Due by 4 pm Monday April 12.

Exercise Set 13: Matrix multiplication Problems and Solutions.

Assignment

Assignment 12 is posted. Due by 4 pm Tuesday April 13. 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 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