Week 13
Graph Connectedness

Business

The start of the week email.

⦿ Monday

Easter Monday Holiday: No Class 😔

⦿ 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 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. 🤷🏻‍♂️

⦿ Friday

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. 😉

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.

Assignment

Assignment 12 (the last one!) was posted last week. This is just a convenience link so you can reach it from this page as well. Due by 1 pm Wednesday April 15. 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