Week 13
Graph Theory II
Business
⦿ Monday
Matrix Multiplication
The last mathematical technique of the course(!) is matrix multiplication. Matrix multiplication will enable us to determine whether a graph is connected from 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 | PDF
- Scalar = a number. Vector = a list of numbers. Matrix = a table of numbers.
- Adding and subtracting matrices Pencast video 3:05 | PDF
- Probably just what you would do intuitively.
- Multiplying vectors Pencast video 4:41 | PDF
- Not intuitive! Be sure to view this before viewing "Multiplying Matrices" below.
- Multiplying matrices Pencast video 5:41 | PDF
- 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 | PDF
- Spoiler: No.
- One last thing about vector multiplication Pencast video 3:58 | PDF
- 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.
Exercises
If you're comfortable with the topics above you're ready to work on:
Supplementary resources:
§7.6 Matrices and matrix operations in Openstax's College Algebra covers arithmetic operations on matrices including multiplication.
Math is Fun's How to multiply matrices will show you how to, er, multiply matrices. 🤷🏻♂️
⦿ Wednesday
Graph reachability and connectedness
- Adjacency matrices and connectedness Pencast video 18:50 | PDF
- Sorry this one is so long, there just didn't seem to be a natural place to 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
- Walk-through 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. 😉
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.
Exercises
No exercises on these topics. They don't lend themselves to little problems, but they do appear on the assignment!
Supplementary resources:
I came up short (again) in finding a free, introductory resource on graph reachability and connectedness. Hopefully the PDF notes above are a sufficient supplement to the pencasts.
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 — so no class 😔
Assignment
Assignment 12 (the last one!) is posted. Due by 1 pm Tuesday 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.)
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