Formal Definition
Given a collection of subsets of a set X, an exact cover of X is a subcollection of that satisfies two conditions:
- The intersection of any two distinct subsets in is empty, i.e., the subsets in are pairwise disjoint. In other words, each element in X is contained in at most one subset in .
- The union of the subsets in is X, i.e., the subsets in cover X. In other words, each element in X is contained in at least one subset in .
In short, an exact cover is "exact" in the sense that each element in X is contained in exactly one subset in .
Equivalently, an exact cover of X is a subcollection of that partitions X.
For an exact cover of X to exist, it is necessary that:
- The union of the subsets in is X. In other words, each element in X is contained in at least one subset in .
If the empty set ∅ is contained in, then it makes no difference whether or not it is in any exact cover. Thus it is typical to assume that:
- The empty set is not in . In other words, each subset in contains at least one element.
Read more about this topic: Exact Cover
Famous quotes containing the words formal and/or definition:
“The bed is now as public as the dinner table and governed by the same rules of formal confrontation.”
—Angela Carter (1940–1992)
“Mothers often are too easily intimidated by their children’s negative reactions...When the child cries or is unhappy, the mother reads this as meaning that she is a failure. This is why it is so important for a mother to know...that the process of growing up involves by definition things that her child is not going to like. Her job is not to create a bed of roses, but to help him learn how to pick his way through the thorns.”
—Elaine Heffner (20th century)