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
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