6 replies to this topic

[gammaman]

Given the following Relation

R={1-2,1-4,4-2,4-3,2-3,2-1,3-2,5-3,2-5}

Find the total path matrix of R in a 2D array

01010

10101

01000

01100

00100

If I were told to find the path matrix of exactly length 3, could I just use the relation I was given and come up with a digraph and then see were the 3 step connections are, and put that back into a 2D array?

[WingedPanther]

R*R*R = path matrix of length 3.

[gammaman]

Oh yes I know that, but based on what is in the code block, did I find the total path matrix, does that mean to just take the relation given and put it into a 2d array as I did.

[WingedPanther]

I believe you found matrix R correctly.

[gammaman]

Well thanks. I am almost positive now that total path matrix and transitive closure are the same thing. Sometimes my prof uses terminology that no one else has heard of.

[WingedPanther]

You always want to get definitions. It sounds like your doing some sort of finite math course for programmers.

[gammaman]

The course is called Algorithm Concepts. We just cover the algorithms themselves and the steps that are involved. We learn how they are computed by diagrams and "steps". We do not learn how to program them. In this course it is expected that you already know how to program, so as the course title suggests, the entire class is conceptual.

As far as defenitions go, my professor sometimes uses terms that know one has heard of, like total path matrix for example.

I found out that total path matrix is:

A path matrix of length n denoted by R*n is a matrix containing 0 and 1’s such that the ( i, j) entry is 1 if there is a path of length exactly n from element i to element j in the graphical representation of the R, and the entry (i, j) is 0 otherwise
The total path matrix for R denoted by P*total is a matrix containing 0 and 1 such that the (I, j) entry is 1 as long as there is a path of any length from i to j in the graphical representation of R.

Edited by WingedPanther, 25 March 2009 - 01:09 PM.
Double post