Indicate the table resulting from the transitive closure

Question

Indicate the table resulting from the transitive closure of the following supervision relationship:

Supervise Est Supervise
Alain Charles
Richard Charles
Marie Richard
Charles Julie
Veronique Marie
Richard Marie

Summary

In the given table, there are seven records. A graph is drawn based on the records above. The graph vertices will be {Alain, Richard, Marie, Charles, Veronique, Julie}. The edges are based on the records above, and there are seven edges. From the graph drawn, the transitive closure of the Supervision table is found and shown below. The table is constructed with 0’s and 1’s based on the reachability of one vertex from the other.

Explanation

transitive closure of supervision relationship diagram

The graph built above is from the table given.
The given table has six records in it, indicating the edges between the vertices of the graph.
The first record is (Alain, Charles).
In the above graph, there is an edge between Alain and Charles.
The second record is (Richard, Charles).
In the above graph, there is an edge between Richard and Charles.
The third record is (Marie, Richard).
In the above graph, there is an edge between Marie and Richard.
The fourth record is (Charles, Julie).
In the above graph, there is an edge between Charles and Julie.
The fifth record is (Veronique, Marie).
In the above graph, there is an edge between Veronique and Marie.
The sixth record is (Richard, Marie).
In the above graph, there is an edge between Richard and Marie.

Transitive Closure:
In a directed graph, for an entry in a table at the index (i, j), it is checked if we can reach vertex ‘j’ from ‘i’, if yes, then 1 will be placed in the table, otherwise 0 will be placed in the table.
The transitive closure for the graph drawn above is:

Alain Charles Julie Richard Veronique Marie
Alain 1 1 1 0 0 0
Charles 0 1 1 0 0 0
Julie 0 1 1 0 0 0
Richard 0 1 1 1 0 1
Veronique 0 1 1 1 1 1
Marie 0 1 1 1 0 1

There is a path {Alain → Charles} from Alain to Charles, hence kept 1 in the table.
There is no path from Charles to Alain, hence kept 0 in the table.
There is a path {Veronique → Marie → Richard → Charles → Julie} from Veronique to Julie, hence kept 1 in the table.

 

Also read, Subset construction to build DFA equivalent to NFA below

Share this post

Leave a Reply

Your email address will not be published. Required fields are marked *