Chapter 6, Problem 1CE

To determine

To calculate: The Stampede Air cities which can be reached by a two-flight sequence from San Antonio and the cities which can be reached by three flight sequence.

Answer to Problem 1CE

Solution:

With the help of two flight sequence we can reach Austin, El Paso, Dallas-Fort Worth and Corpus Christi from San Antonio.

With the help of three flight sequence we can reach every city from San Antonio.

Explanation of Solution

Given:

The Stampede air route map.

The adjacency matrix corresponding to stampede airlines is given by:

$A=\left[\begin{array}{ccccccc}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\end{array}\right]$

Formula used:

Calculation:

The adjacency matrix corresponding to stampede airlines is given by:

$A=\left[\begin{array}{ccccccc}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\end{array}\right]$

And with the help of this we can easily compute $A^2$ as well as $A^3$.

$\begin{array}{c}{A}^2=\left[\begin{array}{ccccccc}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\end{array}\right]\left[\begin{array}{ccccccc}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\end{array}\right]\\ =\left[\begin{array}{ccccccc}4& 2& 2& 2& 2& 2& 0\\ 2& 3& 2& 2& 2& 2& 1\\ 2& 2& 5& 4& 1& 1& 1\\ 2& 2& 4& 5& 1& 1& 1\\ 2& 2& 1& 1& 2& 2& 0\\ 2& 2& 1& 1& 2& 2& 0\\ 0& 1& 1& 1& 0& 0& 1\end{array}\right]\end{array}$

And,

$A^3=\left[\begin{array}{ccccccc}6& 8& 12& 12& 4& 4& 4\\ 8& 6& 11& 11& 4& 4& 2\\ 12& 11& 10& 11& 9& 9& 2\\ 12& 11& 11& 10& 9& 9& 2\\ 4& 4& 9& 9& 2& 2& 2\\ 4& 4& 9& 9& 2& 2& 2\\ 4& 2& 2& 2& 2& 2& 0\end{array}\right]$

San Antonio is represented by the fifth row of the matrix and as we can see in the matrix $A^2$, only the last column of the fifth row corresponds to zero entry. Hence, with the help of two flight sequence we cannot travel only the city placed at that vertex, i.e. Lubbock.

For three flight sequence we look at the matrix $A^3$ and in this matrix there is no zero entry corresponding to the row represented by San Antonio. Hence, we can travel every city with the help of a three flight sequence from San Antonio.