Options

Exercise 57 - Chapter 2

edited June 2018 in Exercises

Fill out the matrix \( M_X \) associated to the graph X in Eq. (2.17):

$$ \begin{array}{ c | c c c c } d(\nearrow) & A & B & C & D \\ \hline A & 0 & ? & ? & ? \\ B & 2 & 0 & \infty & ? \\ C & ? & ? & ? & ? \\ D & ? & ? & ? & ? \end{array} $$ figure

Previous Next

Comments

  • 1.
    edited June 2018

    $$ \begin{array}{ c | c c c c } \nearrow & A & B & C & D \\ \hline A & 0 & \infty & 3 & \infty \\ B & 2 & 0 & \infty & 5 \\ C & \infty & 3 & 0 & \infty \\ D & \infty & \infty & 6 & 0 \end{array} $$

    Comment Source:\[ \begin{array}{ c | c c c c } \nearrow & A & B & C & D \\\\ \hline A & 0 & \infty & 3 & \infty \\\\ B & 2 & 0 & \infty & 5 \\\\ C & \infty & 3 & 0 & \infty \\\\ D & \infty & \infty & 6 & 0 \end{array} \]
  • 2.
    edited June 2018

    @Bruno You filled out the matrix with paths of length 1 (which is correct). What Happens when you multiply it by itself?

    Comment Source:@Bruno You filled out the matrix with paths of length 1 (which is correct). What Happens when you multiply it by itself?
  • 3.

    @Fredrick, multiplying the matrix by itself (using the Eq. 2.97 that tells us about matrix multiplication in a quantale) yields a matrix that tells us about paths with up to 2 edge-traversals.

    Comment Source:@Fredrick, multiplying the matrix by itself (using the Eq. 2.97 that tells us about matrix multiplication in a quantale) yields a matrix that tells us about paths with up to 2 edge-traversals.
Sign In or Register to comment.