Please assit. 1) An intersection graph of a collection of sets A(1), A(2),%u2026
ID: 2985908 • Letter: P
Question
Please assit.
1) An intersection graph of a collection of sets A(1), A(2),%u2026, A(n) is the graph that has as a vertex each of these sets and has an
edge connecting the vertices representing two sets if these sets have a nonempty intersection. The attachment contains an
example of an intersection graph for five sets A, B, C, D and E. Is it possible to represent the graph as a relation? If yes, what
properties of relations would it satisfy?
A = {0, 2, 4, 6, 8}
B = {0, 1, 2, 3, 4}
C = {1, 3, 5, 7, 9}
D = {5, 6, 7, 8, 9}
E = {0, 1, 8, 9}
Explanation / Answer
Yes, we can represent the graph as a relation on the sets.
R on {A,B,C,D,E}x{A,B,C,D,E}
R = {(S,T) : S,T belong to {A,B,C,D,E} and S intersection T is nonempty}
The relation is symmetric since S intersection T = T intersection S