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 conviction that the best way to prepare children for a harsh, rapidly changing world is to introduce formal instruction at an early age is wrong. There is simply no evidence to support it, and considerable evidence against it. Starting children early academically has not worked in the past and is not working now.”
—David Elkind (20th century)
“I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.””
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)