Compatibility Relations
Compatibility relation: let R be a relation on a set S. R is a compatibility relation on S if and only if it is reflexive and symmetric. A compatibility relation on a set partitions the set into compatibility classes. They are typically not disjoint.
Example: let S = {A,B,C,D,E} and
R = {A,A),(B,B),(C,C),(D,D),(E,E),(A,B),(B,A),(A,C),(C,A), (A,D), (D,A),(A,E),(E,A),(B,D),(D,B),(C,D),(D,C),(C,E),(E,C)}
Then the compatibility classes are (AB)(AC)(AD)(AE)(BD)(CD)(CE)(ABD)(ACD)(ACE)
The incompatibility classes are (BC)(BE)(DE)
Compatible pairs may be found using implication tables
Maximal compatibles may be found using merger diagrams