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 spiritual kinship between Lincoln and Whitman was founded upon their Americanism, their essential Westernism. Whitman had grown up without much formal education; Lincoln had scarcely any education. One had become the notable poet of the day; one the orator of the Gettsyburg Address. It was inevitable that Whitman as a poet should turn with a feeling of kinship to Lincoln, and even without any association or contact feel that Lincoln was his.”
—Edgar Lee Masters (1869–1950)
“... we all know the wag’s definition of a philanthropist: a man whose charity increases directly as the square of the distance.”
—George Eliot [Mary Ann (or Marian)