Exercises marked with (*) require further reading/search beyond the suggested texts.
3. Find the PQR tree for the collection in the previous exercise. (C = {he, dc, fb, dcifbg, ae, gb, ic, jc} under U = abcdefghij.)
Answer:
The strictly overlapping graph for the collection is:
Starting from U0 = U and C0 = C, we can consider H0 = aeh, which is the union of a component in the graph. Performing the division, the next two U and C are obtained as follows:
U1 = aeh C1 = {he, ae} U2 = bcdfgijU1 C2 = {dc, fb, dcifbg, gb, ic, jc}
For U1 and C1 (which is prime) there is a linear order that demands e between a and h, so there should be a Q node with e in the center.
A set H2 for U2 can be bfg, so the next two U and C are:
U3 = bfg C3 = {fb, gb} U4 = cdijU1U3 C4 = {dc, dciU3, ic, jc}
For U3 and C3 (which is prime) there is a linear order that demands b between f and g, so there should be a Q node with b in the center.
The set H4 for U4 is cdijU3, so the next two U and C are:
U5 = cdijU3 C5 = {dc, dciU3, ic, jc} U6 = U1U5 C6 = ∅
C5 is prime and non trivial, but it demands c to be between d and i, and consecutive to j as well, which is impossible. So there should be an R node including the elements of U5.
C6 is prime and trivial, so there should be a P node including U5 and U1, which are the elements of U6.
The resulting tree is:
© 2015 Joao Meidanis
