Chapter 16.4, Problem 17WE

To determine

To find: the number of ways given point can send a message back to itself using no more than two relays.

Answer to Problem 17WE

  $\left[\begin{array}{ccccc}1& 1& 1& 0& 0\\ 2& 0& 1& 1& 1\\ 2& 1& 0& 1& 1\\ 2& 2& 1& 0& 1\\ 4& 2& 2& 2& 1\end{array}\right]$

Explanation of Solution

Given information:

In the communication network at the right, a “hook” indicates that two line segments do not intersect.

  

Calculation:

  $X=\begin{array}{c}A\\ B\\ C\\ D\\ E\end{array}\left[\begin{array}{ccccc}0& 1& 0& 0& 0\\ 1& 0& 1& 0& 0\\ 1& 0& 0& 1& 0\\ 1& 0& 0& 0& 1\\ 1& 1& 1& 1& 0\end{array}\right]$

Here $X$ represents the number of direct communication networks, $X^2$ represents the number of communication network using 2 steps. So $X+X^2$ represents the number of communication networks using no more than 2 steps.

  $X^2=XX$

  $\begin{array}{c}{X}^2=\left[\begin{array}{ccccc}0& 1& 0& 0& 0\\ 1& 0& 1& 0& 0\\ 1& 0& 0& 1& 0\\ 1& 0& 0& 0& 1\\ 1& 1& 1& 1& 0\end{array}\right]\left[\begin{array}{ccccc}0& 1& 0& 0& 0\\ 1& 0& 1& 0& 0\\ 1& 0& 0& 1& 0\\ 1& 0& 0& 0& 1\\ 1& 1& 1& 1& 0\end{array}\right]\\ =\left[\begin{array}{ccccc}1& 0& 1& 0& 0\\ 1& 0& 0& 1& 1\\ 1& 1& 0& 0& 1\\ 1& 2& 1& 0& 0\\ 3& 1& 1& 1& 1\end{array}\right]\end{array}$

Now,

  $\begin{array}{c}X+X^2=\left[\begin{array}{ccccc}0& 1& 0& 0& 0\\ 1& 0& 1& 0& 0\\ 1& 0& 0& 1& 0\\ 1& 0& 0& 0& 1\\ 1& 1& 1& 1& 0\end{array}\right]+\left[\begin{array}{ccccc}1& 0& 1& 0& 0\\ 1& 0& 0& 1& 1\\ 1& 1& 0& 0& 1\\ 1& 2& 1& 0& 0\\ 3& 1& 1& 1& 1\end{array}\right]\\ =\left[\begin{array}{ccccc}1& 1& 1& 0& 0\\ 2& 0& 1& 1& 1\\ 2& 1& 0& 1& 1\\ 2& 2& 1& 0& 1\\ 4& 2& 2& 2& 1\end{array}\right]\end{array}$

Thus, the total number of ways given point can send a message back to itself using no more than two relay is,

  $\left[\begin{array}{ccccc}1& 1& 1& 0& 0\\ 2& 0& 1& 1& 1\\ 2& 1& 0& 1& 1\\ 2& 2& 1& 0& 1\\ 4& 2& 2& 2& 1\end{array}\right]$