# Math Help - Use Warshall's algorithm to compute the transitive closure of R

1. ## Use Warshall's algorithm to compute the transitive closure of R

Let $A=\{2,4,6,8,10,12\}$. Let $R=\{(2,6),(2,12),(4,8),(6,4),(8,10),(10,6)\}$ be a relation on the set $A$. Use Warshall's algorithm to compute the transitive closure of $R$.

I regrettably cannot figure out Warshall's algorithm, primarily attributing to my being sick on the day of the lecture when it was taught to my class. Additionally, no source I've found has a quick-and-easy definition of it (though I doubt such a quick definition exists). The definitions I've found, also, are hard for me to understand (though it may just be due to my being tired right now).

2. Suppose you consider four cities: Ottawa, Toronto, Quebec-city and Halifax. There are some direct roads between these cities. You want to find all possibly indirect ways to get from one city to another.

In the beginning, you have only direct roads. Next, you consider what additional connections you get by driving through Ottawa. Then to those connections you add paths that go through Toronto, etc. At each step, you have some roads (note that unlike roads, which lead both ways, the (relation) graph in your case is directed). Then you see what additional connections you get from existing roads by driving through the next city on the list.

To solve your particular problem, draw the adjacency matrix of the relation, i.e., a table 6 x 6 with rows and columns labeled by 2, 4, 6, 8, 10, and 12. Put a check into each cell corresponding to the elements of $R$, i.e., to row 2, column 6; row 2, column 12, etc.

The algorithm has six big steps, one for each element of $A$. During each big step you go through every cell in the table and possibly add (never remove) some checks. For example, suppose it's a step corresponding to $6\in A$, and you are considering a cell at row $r$, column $c$. If this cell does not have a check yet, you put a check there if there are checks at $(r, 6)$ and $(6, c)$. This corresponds to going from $r$ to $c$ through $6$.

After going through all six big steps, you get the adjacency matrix of the transitive closure of $R$.