Options

Exercise 17 - Chapter 4

edited June 2018 in Exercises

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?

Previous Next

$$ \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} $$

Comments

  • 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) \]
  • 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.
  • 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.
  • 4.

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

    Comment Source:Nice! I'm glad you folks are doing the exercises!
Sign In or Register to comment.