Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Options

Exercise 17 - Chapter 4

edited June 2018

Calculate $$M_X^4 * M_\Phi * M_Y^3$$, remembering to do matrix multiplication according to the (min, +)-formula for matrix multiplication in the quantale Cost; see Eq. (2.97).

Your answer should agree with what you got in Exercise 4.15; does it?

$$\begin{matrix} \begin{array}{c | c c c c} M_X & A & B & C & D \\ \hline A & 0 & \infty & 3 & \infty \\ B & 2 & 0 & \infty & 5 \\ C & \infty & 3 & 0 & \infty \\ D & \infty & \infty & 4 & 0 \end{array} & \begin{array}{c | c c c c} M_{\Phi} & x & y & z \\ \hline A & \infty & \infty & \infty \\ B & 11 & \infty & \infty \\ C & \infty & \infty & \infty \\ D & \infty & 9 & \infty \end{array} & \begin{array}{c | c c c c} M_Y & x & y & z \\ \hline x & 0 & 4 & 3 \\ y & 3 & 0 & \infty \\ z & \infty & 4 & 0 \end{array} \end{matrix}$$

• Options
1.
edited June 2018

$$( M * N )(x, z) := \bigvee_{y \in Y} M(x, y) \otimes N(y, z)$$ Using (min, +) gives entries of the form... $$( M * N )(x, z) := \underset{y \in Y}{min} \; M(x, y) + N(y, z)$$

Comment Source:$( M * N )(x, z) := \bigvee_{y \in Y} M(x, y) \otimes N(y, z)$ Using (min, +) gives entries of the form... $( M * N )(x, z) := \underset{y \in Y}{min} \; M(x, y) + N(y, z)$
• Options
2.
edited June 2018

We can either do the multiplication or we can examine the graph and find the least expensive path between the specified nodes.

$$\begin{matrix} \begin{array}{c | c c c c} M_X^2 & A & B & C & D \\ \hline A & 0 & 6 & 3 & \infty \\ B & 2 & 0 & 5 & 5 \\ C & 5 & 3 & 0 & 8 \\ D & \infty & 7 & 4 & 0 \end{array} & \begin{array}{c | c c c c} M_X^4 & A & B & C & D \\ \hline A & 0 & 6 & 3 & 11 \\ B & 2 & 0 & 5 & 5 \\ C & 5 & 3 & 0 & 8 \\ D & 9 & 7 & 4 & 0 \end{array} \end{matrix}$$ Each successive multiplication identifies paths of that length.

Comment Source:We can either do the multiplication or we can examine the graph and find the least expensive path between the specified nodes. $\begin{matrix} \begin{array}{c | c c c c} M_X^2 & A & B & C & D \\\\ \hline A & 0 & 6 & 3 & \infty \\\\ B & 2 & 0 & 5 & 5 \\\\ C & 5 & 3 & 0 & 8 \\\\ D & \infty & 7 & 4 & 0 \end{array} & \begin{array}{c | c c c c} M_X^4 & A & B & C & D \\\\ \hline A & 0 & 6 & 3 & 11 \\\\ B & 2 & 0 & 5 & 5 \\\\ C & 5 & 3 & 0 & 8 \\\\ D & 9 & 7 & 4 & 0 \end{array} \end{matrix}$ Each successive multiplication identifies paths of that length. 
• Options
3.

$$\begin{matrix} \begin{array}{c | c c c c} M_X^4 & A & B & C & D \\ \hline A & 0 & 6 & 3 & 11 \\ B & 2 & 0 & 5 & 5 \\ C & 5 & 3 & 0 & 8 \\ D & 9 & 7 & 4 & 0 \end{array} & \begin{array}{c | c c c c} M_{\Phi} & x & y & z \\ \hline A & \infty & \infty & \infty \\ B & 11 & \infty & \infty \\ C & \infty & \infty & \infty \\ D & \infty & 9 & \infty \end{array} & \begin{array}{c | c c c c} M_Y^3 & x & y & z \\ \hline x & 0 & 4 & 3 \\ y & 3 & 0 & 6 \\ z & 7 & 4 & 0 \end{array} \end{matrix}$$ So, $$\begin{matrix} \begin{array}{c | c c c c} M_X^4 * M_\Phi & x & y & z \\ \hline A & 17 & 20 & \infty \\ B & 11 & 14 & \infty \\ C & 14 & 17 & \infty \\ D & 18 & 9 & \infty \end{array} & & \begin{array}{c | c c c c} M_X^4 * M_\Phi * M_Y^3 & x & y & z \\ \hline A & 17 & 20 & 20 \\ B & 11 & 14 & 14 \\ C & 14 & 17 & 17 \\ D & 12 & 9 & 15 \end{array} \end{matrix}$$ . Which agrees with the result of Exercise 4.15.

Comment Source:$\begin{matrix} \begin{array}{c | c c c c} M_X^4 & A & B & C & D \\\\ \hline A & 0 & 6 & 3 & 11 \\\\ B & 2 & 0 & 5 & 5 \\\\ C & 5 & 3 & 0 & 8 \\\\ D & 9 & 7 & 4 & 0 \end{array} & \begin{array}{c | c c c c} M_{\Phi} & x & y & z \\\\ \hline A & \infty & \infty & \infty \\\\ B & 11 & \infty & \infty \\\\ C & \infty & \infty & \infty \\\\ D & \infty & 9 & \infty \end{array} & \begin{array}{c | c c c c} M_Y^3 & x & y & z \\\\ \hline x & 0 & 4 & 3 \\\\ y & 3 & 0 & 6 \\\\ z & 7 & 4 & 0 \end{array} \end{matrix}$ So, $\begin{matrix} \begin{array}{c | c c c c} M_X^4 * M_\Phi & x & y & z \\\\ \hline A & 17 & 20 & \infty \\\\ B & 11 & 14 & \infty \\\\ C & 14 & 17 & \infty \\\\ D & 18 & 9 & \infty \end{array} & & \begin{array}{c | c c c c} M_X^4 * M_\Phi * M_Y^3 & x & y & z \\\\ \hline A & 17 & 20 & 20 \\\\ B & 11 & 14 & 14 \\\\ C & 14 & 17 & 17 \\\\ D & 12 & 9 & 15 \end{array} \end{matrix}$ . Which agrees with the result of Exercise 4.15.
• Options
4.

Nice! I'm glad you folks are doing the exercises!

Comment Source:Nice! I'm glad you folks are doing the exercises!