Howdy, Stranger!

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

Options

Exercise 57 - Chapter 2

edited June 2018

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}$$ • Options
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}$
• Options
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?
• Options
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.