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:
“There must be a profound recognition that parents are the first teachers and that education begins before formal schooling and is deeply rooted in the values, traditions, and norms of family and culture.”
—Sara Lawrence Lightfoot (20th century)
“The physicians say, they are not materialists; but they are:MSpirit is matter reduced to an extreme thinness: O so thin!—But the definition of spiritual should be, that which is its own evidence. What notions do they attach to love! what to religion! One would not willingly pronounce these words in their hearing, and give them the occasion to profane them.”
—Ralph Waldo Emerson (1803–1882)