Connectivity Matricies

Daniel McIntyre Collegiate Institute Applied Math 40S Connectivity Matricies Planning travel between different cities can become very complicated. If the number of cities and the number of alternative routes are small, the problem is relatively easy and can be handled with little more than paper and pencil. If the number of cities is large (even just 5 cities) or if there are many alternative routes, the human mind has great difficulty organizing and considering all the alternatives. A matrix is a mathematical tool that is useful for organizing and dealing with large amounts of data. Matrices (plural for matrix) can be used to summarize the routes between cities and to even calculate the different number of routes. Airlines, train and bus companies, and truck dispatchers are some of the organizations that use matrices as they make plans for moving people or goods to and from various locations. To see how matrices are used in transportation planning, let's start with something simple: a problem involving three cities and then we'll extend what we've learned to a more realistic problem involving six cities. Three Cities A small airline serves three cities, Atlanta (ATL), Boston (BOS), and Charlotte (CLT), using a limited number of airplanes. The flight service planner needs a convenient method for keeping track of all possible trips connecting the three cities. She is concerned with "one-hop," "two-hop," "threehop," etc. trips. A "two-hop" trips means that you start at one city, say Atlanta, and make one-hop to the next, say Boston, then a second hop to another city, either Atlanta or Charlotte. This small airline is licenced to fly between certain cities. It can fly a route between Atlanta and Boston (to and from either city) and a route between Boston and Charlotte (again, to and from either city). No other flights are available. 1. Use the diagram below to draw a network that shows this airline's route service between Atlanta (ATL), Boston (BOS), and Charlotte (CLT). BOS ATL CLT 2 0   A matrix is a rectangular grid of numbers. For example, 0 1 is a matrix consisting of three rows   3 2 and two columns. We put parentheses around the numbers in the grid to indicate that they are to be considered as a single item: a matrix of numbers. Each number inside the matrix is known as an element or cell. We can create a matrix that represents the routes between our three cities. Such a matrix will need

three rows and three columns, each row and column represent each of the three cities. Atlanta

Boston

Charlotte

Atlanta Boston Charlotte For each cell in the matrix, we can place a 1 to indicate that there is one route between the city in the row and column for that cell. For example, there is one route between Atlanta and Boston, so there should be a 1 in the cell on the first row, second column. We use 0 to indicate that there is no route between the two cities. There is no route from Atlanta to Charlotte (directly, in one-hop) and likewise no route from Atlanta back to Atlanta (directly) so the matrix looks like: Atlanta Boston Charlotte

Atlanta 0

Boston 1

Charlotte 0

2. Complete the matrix above. Mathematicians prefer to work with only the most relevant information. The matrix summarizing the one-hop routes between the three cities is know as the "connectivity matrix" and it can be written in its briefest form by leaving off the names of the cities: 0  1  0

1 0  0 1  1 0

The power of mathematics is derived from what information one can gains from its use. To see this power, first produce all the "two-hop" routes between the three cities. To get you started, is there a "two-hop" route between Atlanta and Atlanta? Yes, you fly Atlanta to Boston then back to Atlanta. Any others? No. So 1 goes in the first cell. Is there a "two-hop" route from Atlanta to Boston? No, you can fly from Atlanta to Boston, but your next hop will take you away from Boston, so 0 will go in the next cell. Atlanta Boston Charlotte

Atlanta 1

Boston 0

Charlotte

3. Complete the table above of all two-hop routes between the three cities. 0  4. Find the product of 1  0

1 0 0  0 1 1  1 0 0

1 0  0 1  1 0

5. Compare the results of #3 and #4 above. What do you notice?

1  6. Find the product of 0  1

0 1 0  2 0 1  0 1 0

0 1 0   0 1  or 1   1 0 0

3 1 0  0 1  1 0

7. Fill in the table for the three hop routes between the three cities. Atlanta

Boston

Charlotte

Atlanta Boston Charlotte 8. What does the 4th power of the connectivity matrix tell you. Matrix multiplication can get tiresome. A graphing calculator or computer can be used to perform matrix multiplication. Feel free to use your calculator throughout this exercise. A More Realistic Example Consider six cities: Los Angeles (LAX), Atlanta (ATL), Pittsburgh (PIT), Miami (MIA), Charlotte (CLT), and Boston (BOS). Suppose our airline as expanded serve to include routes among these six as described by the network diagram below: BOS

PIT LAX

CLT

ATL MIA 9. Find the connectivity matrix for the six cities.

10. Use a graphing calculator to find the number of all two-hop routes between the six cities. 11. Use a graphing calculator to find the number of all three-hop routes between the six cities. 12. Use a graphing calculator to find the number of all four-hop routes between the six cities.

Daniel McIntyre Collegiate Institute Applied Math 40S Connectivity Matricies - Student Answer Sheet 1. BOS ATL CLT 2. Atlanta Boston Charlotte

Atlanta 0

Boston 1

Charlotte 0

Atlanta 1

Boston 0

Charlotte

3. Atlanta Boston Charlotte 0  4. 1  0

1 0 0  0 1 1  1 0 0

1 0  0 1 =  1 0

5. ____________________________________________________________________________ ______________________________________________________________________________ 0  6. 1  0

3 1 0  0 1 =  1 0

7. Atlanta

Boston

Charlotte

Atlanta Boston Charlotte 8. ____________________________________________________________________________ ______________________________________________________________________________

9.

To

From

 ___   ___   ___  ___   ___   ___

___ ___ ___ ___ ___ ___

10.

___ ___ ___ ___ ___ ___

___ ___ ___ ___ ___ ___

___ ___ ___ ___ ___ ___

___  ___  ___ ___ ___  ___

___ ___ ___ ___ ___ ___

___ ___ ___ ___ ___ ___

___  ___  ___ ___ ___  ___

___ ___ ___ ___ ___ ___

___ ___ ___ ___ ___ ___

___  ___  ___ ___ ___  ___

___ ___ ___ ___ ___ ___

___ ___ ___ ___ ___ ___

___  ___  ___ ___ ___  ___

To

From

 ___   ___   ___  ___   ___   ___

___ ___ ___ ___ ___ ___

11.

___ ___ ___ ___ ___ ___ To

From

 ___   ___   ___  ___   ___   ___

___ ___ ___ ___ ___ ___

12.

___ ___ ___ ___ ___ ___ To

From

 ___   ___   ___  ___   ___   ___

___ ___ ___ ___ ___ ___

___ ___ ___ ___ ___ ___