Exercises marked with (*) require further reading/search beyond the suggested texts.
3. Find the directed acyclic graph formed by the components obtained in the previous exercise.
Note: the previous exercise asked about the connected components of the scrict overlap graph for the rows in the following binary matrix:
0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1 0 1 1 0 1 0 1 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0
Answer:
These are the components obtained from the previous exercise, where Si represents row i:
Taking the union of the sets (rows) in each component, we get (numbers represent matirx columns):
A = {1,2,3,4,5,6,7,8,9,10}
B = {3,6,8}
C = {4,5,7,9}
D = {7}
The acyclic graph formed by the components is (with an arrow X → Y meaning that X contains Y):
© 2015 Joao Meidanis