interface( warnlevel=0, rtablesize=20 ):
with( laylinalg ):
# Text Reference: Section 2.1, powers of a matrix
# Wikipedia: adjacency matrix, graph theory
# Lab 3: Adjacency Matrices and Airline Routes
# The purpose of this lab is to show how powers of a matrix may be used to investigate graphs. Special attention is paid to airline route maps as examples of graphs.
# In order to study graphs, the notion of graph must first be defined. A graph is a set of points (called vertices, or nodes) and a set of lines called edges connecting some pairs of vertices. Two vertices connected by an edge are said to be adjacent. Consider the graph in Figure 1. Notice that two vertices may be connected by more than one edge (A and B are connected by 2 distinct edges), that a vertex need not be connected to any other vertex (D), and that a vertex may be connected to itself (F).
#
# Figure 1
# Another example of a graph is the route map that most airlines (or railways) produce. A copy of the northern route map for Cape Air from May 2001 is Figure 2. A newer route map is available at the web page: www.capeair.com. Here the vertices are the cities to which Cape Air flies, and two vertices are connected if a direct flight flies between them.
#
# Figure 2: Northern Route Map for Cape Air -- May 2001
# Some natural questions arise about graphs. It might be important to know if two vertices are connected by a sequence of two edges, even if they are not connected by a single edge. In Figure 1 , A and C are connected by a two-edge sequence (actually, there are four distinct ways to go from A to C in two steps). In the route map, Provincetown and Hyannis are connected by a two-edge sequence, meaning that a passenger would have to stop in Boston while flying between those cities on Cape Air. It might be important to know if it is possible to get from a vertex to another vertex. It is impossible to go from vertex D in Figure 1 to any other vertex, but a passenger on Cape Air can get from any city in their network to any other city given enough flights. But how many flights are enough? This is another issue of interest: what is the minimum number of steps to get from one vertex to another? What is the minimum number of steps to get from any vertex on the graph to any other? While these questions are relatively easy to answer for a small graph, as the number of vertices and edges grows, it becomes harder to keep track of all the different ways the vertices are connected. Matrix notation and computation can help to answer these questions.
# The adjacency matrix for a graph with n; vertices is an n;xn; matrix whose (i;,j;) entry is 1 if the i^th; vertex and j^th; vertex are connected, and 0 if they are not. If in Figure 1 A is vertex 1, B is vertex 2, etc., then the adjacency matrix for this graph is
# M = (Matrix(6, 6, {(1, 1) = 0, (1, 2) = 1, (1, 3) = 0, (1, 4) = 0, (1, 5) = 0, (1, 6) = 0, (2, 1) = 1, (2, 2) = 0, (2, 3) = 1, (2, 4) = 0, (2, 5) = 1, (2, 6) = 0, (3, 1) = 0, (3, 2) = 1, (3, 3) = 0, (3, 4) = 0, (3, 5) = 0, (3, 6) = 1, (4, 1) = 0, (4, 2) = 0, (4, 3) = 0, (4, 4) = 0, (4, 5) = 0, (4, 6) = 0, (5, 1) = 0, (5, 2) = 1, (5, 3) = 0, (5, 4) = 0, (5, 5) = 0, (5, 6) = 1, (6, 1) = 0, (6, 2) = 0, (6, 3) = 1, (6, 4) = 0, (6, 5) = 1, (6, 6) = 1}));
# This matrix depends upon the choice of coordinates: vertices A,B,C,D,E,F correspond to the rows of matrix M, and the same for the columns. The Maple command to create the adjacency matrix for Figure 1 is
# M := < <0, 1, 0, 0, 0, 0>
# | <1, 0, 1, 0, 1, 0>
# | <0, 1, 0, 0, 0, 1>
# | <0, 0, 0, 0, 0, 0>
# | <0, 1, 0, 0, 0, 1>
# | <0, 0, 1, 0, 1, 1> >;
M := < <0, 1, 0, 0, 0, 0>
| <1, 0, 1, 0, 1, 0>
| <0, 1, 0, 0, 0, 1>
| <0, 0, 0, 0, 0, 0>
| <0, 1, 0, 0, 0, 1>
| <0, 0, 1, 0, 1, 1> >;
# If the vertices in the Cape Air graph respectively correspond to Boston, Hyannis, Martha's Vineyard, Nantucket, New Bedford, Providence, and Provincetown, then the adjacency matrix for Cape Air is
# B = Matrix(7, 7, {(1, 1) = 0, (1, 2) = 1, (1, 3) = 1, (1, 4) = 1, (1, 5) = 0, (1, 6) = 0, (1, 7) = 1, (2, 1) = 1, (2, 2) = 0, (2, 3) = 1, (2, 4) = 1, (2, 5) = 0, (2, 6) = 0, (2, 7) = 0, (3, 1) = 1, (3, 2) = 1, (3, 3) = 0, (3, 4) = 1, (3, 5) = 1, (3, 6) = 1, (3, 7) = 0, (4, 1) = 1, (4, 2) = 1, (4, 3) = 1, (4, 4) = 0, (4, 5) = 1, (4, 6) = 1, (4, 7) = 0, (5, 1) = 0, (5, 2) = 0, (5, 3) = 1, (5, 4) = 1, (5, 5) = 0, (5, 6) = 0, (5, 7) = 0, (6, 1) = 0, (6, 2) = 0, (6, 3) = 1, (6, 4) = 1, (6, 5) = 0, (6, 6) = 0, (6, 7) = 0, (7, 1) = 1, (7, 2) = 0, (7, 3) = 0, (7, 4) = 0, (7, 5) = 0, (7, 6) = 0, (7, 7) = 0});
# The Maple command to create this matrix is
# B := < <0, 1, 1, 1, 0, 0, 1>
# | <1, 0, 1, 1, 0, 0, 0>
# | <1, 1, 0, 1, 1, 1, 0>
# | <1, 1, 1, 0, 1, 1, 0>
# | <0, 0, 1, 1, 0, 0, 0>
# | <0, 0, 1, 1, 0, 0, 0>
# | <1, 0, 0, 0, 0, 0, 0> >;
B := < <0, 1, 1, 1, 0, 0, 1>
| <1, 0, 1, 1, 0, 0, 0>
| <1, 1, 0, 1, 1, 1, 0>
| <1, 1, 1, 0, 1, 1, 0>
| <0, 0, 1, 1, 0, 0, 0>
| <0, 0, 1, 1, 0, 0, 0>
| <1, 0, 0, 0, 0, 0, 0> >;
# Adjacency matrices can be used to address the questions raised earlier.
# Question: Which vertices are connected by a two-edge sequence? How many different two-edge sequences connect each pair of vertices?
# Consider Figure 1. Vertices B and F are connected by two-edge sequences in 2 different ways: through vertex E or through vertex C. Notice that the two edges from B to C are not distinguished. Let m[i, j]; be the (i;,j;) entry in the adjacency matrix M, and note that
# m[1, 6]*m[2, 1]+m[2, 2]*m[2, 6]+m[2, 3]*m[3, 6]+m[2, 4]*m[4, 6]+m[2, 5]*m[5, 6];
# = (1)(0) + (0)(0) + (1)(1) + (0)(0) + (1)(1) + (0)(1)
# = 2
# which is the number of two-step sequences between B and F. This calculation works because in order for a two-step sequence to occur, B and F must both connect to an intermediate vertex. Because B connects with C and C connects with F, then m[2,3]*m[3,6]=1; since B connects with A but A does not connect with F, then B does not have a two-step sequence with A and m[2,1]*m[1,6]=0. Summing over all intermediate points gives us the result. Now notice that
# m[1, 6]*m[2, 1]+m[2, 2]*m[2, 6]+m[2, 3]*m[3, 6]+m[2, 4]*m[4, 6]+m[2, 5]*m[5, 6]; is just the (2,6) entry in the matrix M^2;. The following observation seems warranted:
# Observation 1:
# The number of two-step sequences between vertex i; and vertex j; in a graph with adjacency matrix M is the (i;,j;) entry in M^2;.
# In fact, the following is also true.
# Observation 2:
# The number of k;-step sequences between vertex i; and vertex j; in a graph with adjacency matrix M is the (i;,j;) entry in M^k;.
# If M is the adjacency matrix for Figure 1, then M=[[[0,1,0,0,0,0],[1,0,1,0,1,0],[0,1,0,0,0,1],[0,0,0,0,0,0],[0,1,0,0,0,1],[0,0,1,0,1,1]]], M^2=[[[1,0,1,0,1,0],[0,3,0,0,0,2],[1,0,2,0,2,1],[0,0,0,0,0,0],[1,0,2,0,2,1],[0,2,1,0,1,3]]], ;and M^3 = (Matrix(6, 6, {(1, 1) = 0, (1, 2) = 3, (1, 3) = 0, (1, 4) = 0, (1, 5) = 0, (1, 6) = 2, (2, 1) = 3, (2, 2) = 0, (2, 3) = 5, (2, 4) = 0, (2, 5) = 5, (2, 6) = 2, (3, 1) = 0, (3, 2) = 5, (3, 3) = 1, (3, 4) = 0, (3, 5) = 1, (3, 6) = 5, (4, 1) = 0, (4, 2) = 0, (4, 3) = 0, (4, 4) = 0, (4, 5) = 0, (4, 6) = 0, (5, 1) = 0, (5, 2) = 5, (5, 3) = 1, (5, 4) = 0, (5, 5) = 1, (5, 6) = 5, (6, 1) = 2, (6, 2) = 2, (6, 3) = 5, (6, 4) = 0, (6, 5) = 5, (6, 6) = 5}));.
# Thus there is 1 two-step sequence from C to F, and there are 5 three-step sequences between C and F.
# In observing the figures, note that some two-step or three-step sequences may not be meaningful. On the Cape Air route map, Nantucket is reachable in two steps from Boston (via Hyannis or Martha's Vineyard), but in reality this does not matter, since there is a direct flight between the two cities. A better question to ask of a graph might be
# Question: What is the least number of edges which must be traversed to go from vertex A to vertex B?
# To answer this question, consider the matrix S[k] = M^2+M; + ... + M[k];. The (i;,j;) entry in this matrix tallies the number of ways to get from vertex i; to vertex j; in k; steps or less. If such a trip is impossible, this entry will be zero. Thus to find the shortest number of steps between the vertices, continue to compute S[k]; as k; increases; the first k; for which the (i;,j;) entry in S[k]; is non-zero is the shortest number of steps between i; and j;. Note that this process is non-constructive; that is, the shortest number of steps may be computed, but the method does not determine what those steps are.
# Another question concerned whether it is possible to go from any vertex in a graph to any other. If a graph has the property that each vertex is connected to every other vertex in some number of steps, then the graph is connected.
# Question: How can it be determined if a graph is connected?
# This should be easy to see from a small graph, but is harder to see from the adjacency matrix. However, there is a calculation that can be done. Suppose that the graph contains n; vertices. Then the largest number of steps it could take to go from a vertex to any other vertex is n; steps. Thus S[n] = M^2+M; + ... + M^n; can help us. If there are any zeroes in this matrix, then it is impossible for some pair of vertices to connect in n; steps or less, so this pair will never connect, and the graph is not connected.
# Problems to be solved and submitted:
# Problem 1.
# The route map for the northern routes of Big Sky Airlines for 2003 is given in Figure 3 below. Produce a 20x20 adjacency matrix for this map. The airline ceased operations in 2008, so updated route maps don't exist.
#
# Figure 3: Northern Route Map for Big Sky Airlines -- 2003
# Problem 2.
# List the three-step sequences between C and F in Figure 1, and confirm that there are indeed 5 of them.
# Problem 3.
# Which Cape Air cities may be reached by a two flight sequence from New Bedford? Which may be reached by a three flight sequence?
# Problem 4.
# In Figure 1, show that the shortest path between A and F has 3 steps.
# Problem 5.
# Which trips in the Cape Air network take the greatest number of flights?
# Problem 6.
# Show that the graph in Figure 1 is not connected by observing S[n];.
# Problem 7.
# Figure 4 shows the May 2001 route map for Spirit Airlines. An updated map for 2015 may be found at https://www.spirit.com/routemaps.aspx. The adjacency matrix for the map in Figure 4 is the matrix A which is found below. The vertices correspond to: Atlantic City, Chicago (O'Hare), Detroit, Fort Lauderdale, Fort Myers, Los Angeles, Melbourne, Myrtle Beach, Newark, New York (LaGuardia), Oakland, Orlando, Tampa, and Washington (Reagan National). What is the shortest number of flights it would take to go from Tampa to Newark? How many different ways can you make that trip?
#
# Figure 4: Route Map for Spirit Air -- May 2001
# The Maple command to create the adjacency matrix for Spirit Airlines is
# A := < <0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0>
# | <1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0>
# | <0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0>
# | <1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1>
# | <1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0>
# | <0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0>
# | <0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1>
# | <1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0>
# | <0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0>
# | <0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0>
# | <0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0>
# | <1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0>
# | <1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0>
# | <0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0> >;
A := < <0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0>
| <1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0>
| <0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0>
| <1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1>
| <1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0>
| <0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0>
| <0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1>
| <1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0>
| <0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0>
| <0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0>
| <0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0>
| <1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0>
| <1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0>
| <0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0> >;
# Problem 8.
# What is the largest number of flights you would need to get from one Spirit city to another? Which trips take the largest number of flights? How many ways can you make those trips?
# More Routes
# Other airline route maps can be investigated by browsing www.airlineroutemaps.com or www.airfarewatchdog.com.