Covering and packing
Combinatorial configurations related to multi-valued mappings of one set into another. Assume that one is given sets and
together with a multi-valued mapping
of
into
. Let
be the image of an element
under
and, for any
, let
. A subset
is called a covering for
if
. A subset
is called a packing for
if for any two different elements
and
from
the sets
and
do not intersect. A subset
is called a perfect packing, or a perfect covering, if
is simultaneously a covering and a packing. The set
is called the covering set, and the set
is called the covered set. If the inverse mapping
is such that
, one can consider
as a covering set and
as the covered set. The mapping
defines an incidence relation
for which
from
and
from
are incident (denoted by
) if
.
The concepts of a packing and a covering are related to extremal problems involving the search for packings and coverings (for any given triple ) that provide an extremum for some functional. That functional may, for example, be specified by means of a function that puts each element
from
into correspondence with a non-negative real number
, called the weight of the element
. The minimal covering problem consists in constructing a covering
for which
takes a minimal value. One often considers the case where
; here one is concerned with finding a covering of minimal cardinality, or a so-called least covering. If the triple
is such that
![]() |
then the minimum cardinality of the covering satisfies the inequalities
![]() |
In extremal problems on packings one usually is required to find packings of maximal cardinality.
Sometimes a function is defined on the covered set
that takes non-negative integer values, and then the name
-covering (
-packing) is given to a subset
that satisfies the following condition: For each
, the number
of those elements
that are incident to
obeys the inequality
![]() |
(correspondingly, ). There is a relationship between
-coverings of minimal cardinality and
-packings of maximal cardinality. That is, let two sets
and
be given together with a multi-valued mapping
and let also functions
and
be given on
such that for each
,
![]() |
Then, if the set is a
-covering of minimal cardinality for
, the set
is a
-packing of maximal cardinality, and vice versa. If
is a maximal
-packing, the set
is a
-covering of minimal cardinality. The following relate, for example, to the class of problems concerned with coverings and packings:
1) Let be a graph with set of vertices
and set of edges
. If one considers
as the covered set and
as the covering set, while the incidence relation for the vertices and edges is taken as
, a covering is an edge-covering of the graph and a packing is a pairing, while a perfect packing is a perfect pairing. If one takes the set of vertices as the covering and covered sets, while
is the adjacency relation for vertices, a covering will be an externally stable set, while a packing is an internally stable set; moreover, the cardinality of the minimal covering is the external stability number, and the cardinality of the maximum packing is the internal stability number (see Graph, numerical characteristics of a).
2) Let be a non-empty set in a metric space
. A system
of sets
is called an
-covering of
if the diameter
of any set
does not exceed
and
. A set
is called an
-net for
if any point in the set
is at distance not exceeding
from some point in
. A set
is called
-distinguishable if any two of different points of it have distance greater than
. Let
be the minimal number of sets in an
-covering of
, and let
be the maximal number of points in an
-distinguishable subset of
. The number
is called the
-entropy of
, while
is called the
-capacity of
. The concepts of
-entropy and
-capacity are used in the theory of approximation of functions and in information theory.
3) Let be the
-dimensional unit cube with the Hamming metric, while the covered set is the set of its vertices and the covering set is the set of spheres of radius
in
. Then the set of centres for the sphere packing is a code that will correct
errors. If the packing is perfect, the code is said to be densely packed or perfect.
If for the covered set one takes the subset of vertices in the cube
on which some Boolean function
takes the value 1, while the covering set is the set of faces (intervals) entirely contained in
, then the covering of minimal cardinality will correspond to the shortest disjunctive normal form of
, while the covering with minimal sum of ranks will correspond to the minimal disjunctive normal form of
(see Boolean functions, normal forms of).
In problems on coverings and packings, one estimates their cardinality, examines questions of existence, construction and enumeration of perfect packings, as well as the possibility of constructing effective algorithms for solving these problems.
References
[1] | C.A. Rogers, "Packing and covering" , Cambridge Univ. Press (1964) MR0172183 Zbl 0176.51401 |
[2] | L. Fejes Toth, "Lagerungen in der Ebene, auf der Kugel und im Raum" , Springer (1972) Zbl 0229.52009 |
[3] | W.W. Peterson, E.J. Weldon, "Error-correcting codes" , M.I.T. (1972) MR0347444 Zbl 0251.94007 |
[4] | , Discrete mathematics and mathematical problems in cybernetics , 1 , Moscow (1974) (In Russian) Zbl 1185.68346 |
[5] | F. Harary, "Graph theory" , Addison-Wesley (1972) MR1536844 Zbl 1161.05345 Zbl 0951.05056 Zbl 0838.05066 Zbl 0854.05044 Zbl 0797.05064 Zbl 0677.01013 Zbl 0547.00012 Zbl 0443.05036 Zbl 0471.05024 Zbl 0465.05026 Zbl 0458.00002 Zbl 0329.05125 Zbl 0288.05109 Zbl 0282.00003 Zbl 0275.05101 Zbl 0253.00004 Zbl 0224.05129 Zbl 0196.27202 Zbl 0193.28103 Zbl 0182.57702 |
[6] | C. Berge, "Théorie des graphes et leurs applications" , Dunod (1958) |
[7] | A.G. Vitushkin, "Estimation of the complexity of the tabulation problem" , Moscow (1959) (In Russian) |
[8] | A.N. Kolmogorov, V.M. Tikhomirov, "![]() ![]() |
[9] | N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian) MR0362811 Zbl 0524.65001 |
[10] | S.V. Yablonskii, "Introduction to discrete mathematics" , Moscow (1979) (In Russian) MR0563327 |
Comments
References
[a1] | A. Schrijver (ed.) , Packing and covering in combinatorics , CWI , Amsterdam (1979) MR0562282 Zbl 0419.00004 |
Covering and packing. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Covering_and_packing&oldid=46547