Results 1 to 2 of 2

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

  1. #1
    Member
    Joined
    Jan 2010
    Posts
    232

    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).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof concerning a transitive closure
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 25th 2011, 01:26 PM
  2. Transitive Closure
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 27th 2010, 07:33 AM
  3. Transitive closure relation.
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: March 8th 2009, 04:38 AM
  4. Transitive Closure in FOL and Prolog
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 22nd 2009, 03:06 AM
  5. Transitive closure
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: August 15th 2008, 12:06 AM

Search Tags


/mathhelpforum @mathhelpforum