Namespaces
Variants
Actions

Difference between revisions of "Covering and packing"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
m (→‎References: latexify)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
Combinatorial configurations related to multi-valued mappings of one set into another. Assume that one is given sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c0269101.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c0269102.png" /> together with a multi-valued mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c0269103.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c0269104.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c0269105.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c0269106.png" /> be the image of an element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c0269107.png" /> under <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c0269108.png" /> and, for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c0269109.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691010.png" />. A subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691011.png" /> is called a covering for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691012.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691013.png" />. A subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691014.png" /> is called a packing for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691015.png" /> if for any two different elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691016.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691017.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691018.png" /> the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691019.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691020.png" /> do not intersect. A subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691021.png" /> is called a perfect packing, or a perfect covering, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691022.png" /> is simultaneously a covering and a packing. The set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691023.png" /> is called the covering set, and the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691024.png" /> is called the covered set. If the inverse mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691025.png" /> is such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691026.png" />, one can consider <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691027.png" /> as a covering set and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691028.png" /> as the covered set. The mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691029.png" /> defines an incidence relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691030.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691031.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691032.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691033.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691034.png" /> are incident (denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691035.png" />) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691036.png" />.
+
<!--
 +
c0269101.png
 +
$#A+1 = 129 n = 2
 +
$#C+1 = 129 : ~/encyclopedia/old_files/data/C026/C.0206910 Covering and packing
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
The concepts of a packing and a covering are related to extremal problems involving the search for packings and coverings (for any given triple <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691037.png" />) that provide an extremum for some functional. That functional may, for example, be specified by means of a function that puts each element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691038.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691039.png" /> into correspondence with a non-negative real number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691040.png" />, called the weight of the element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691041.png" />. The minimal covering problem consists in constructing a covering <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691042.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691043.png" /> takes a minimal value. One often considers the case where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691044.png" />; here one is concerned with finding a covering of minimal cardinality, or a so-called least covering. If the triple <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691045.png" /> is such that
+
{{TEX|auto}}
 +
{{TEX|done}}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691046.png" /></td> </tr></table>
+
Combinatorial configurations related to multi-valued mappings of one set into another. Assume that one is given sets  $  V $
 +
and  $  E $
 +
together with a multi-valued mapping  $  \Gamma $
 +
of  $  E $
 +
into  $  V $.
 +
Let  $  \Gamma ( e) $
 +
be the image of an element  $  e \in E $
 +
under  $  \Gamma $
 +
and, for any  $  C \subseteq E $,
 +
let  $  \Gamma ( C) = \cup _ {e \in E }  \Gamma ( e) $.
 +
A subset  $  C \subseteq E $
 +
is called a covering for  $  ( V, E, \Gamma ) $
 +
if  $  \Gamma ( C) = V $.
 +
A subset  $  P \subseteq E $
 +
is called a packing for  $  ( V, E, \Gamma ) $
 +
if for any two different elements  $  e _ {i} $
 +
and  $  e _ {j} $
 +
from  $  P $
 +
the sets  $  \Gamma ( e _ {i} ) $
 +
and  $  \Gamma ( e _ {j} ) $
 +
do not intersect. A subset  $  P \subseteq E $
 +
is called a perfect packing, or a perfect covering, if  $  P $
 +
is simultaneously a covering and a packing. The set  $  E $
 +
is called the covering set, and the set  $  V $
 +
is called the covered set. If the inverse mapping  $  \Gamma  ^ {-} 1 $
 +
is such that  $  \Gamma  ^ {-} 1 ( V) = E $,
 +
one can consider  $  V $
 +
as a covering set and  $  E $
 +
as the covered set. The mapping  $  \Gamma : E \rightarrow V $
 +
defines an incidence relation  $  I $
 +
for which  $  v $
 +
from  $  V $
 +
and  $  e $
 +
from  $  E $
 +
are incident (denoted by  $  vIe $)
 +
if  $  v \in \Gamma ( e) $.
  
then the minimum cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691047.png" /> of the covering satisfies the inequalities
+
The concepts of a packing and a covering are related to extremal problems involving the search for packings and coverings (for any given triple  $  ( V, E, \Gamma ) $)
 +
that provide an extremum for some functional. That functional may, for example, be specified by means of a function that puts each element  $  e $
 +
from  $  E $
 +
into correspondence with a non-negative real number  $  w( e) $,
 +
called the weight of the element  $  e $.  
 +
The minimal covering problem consists in constructing a covering  $  C $
 +
for which  $  \sum _ {e \in C }  w( e) $
 +
takes a minimal value. One often considers the case where  $  w( e) \equiv 1 $;
 +
here one is concerned with finding a covering of minimal cardinality, or a so-called least covering. If the triple  $  ( V, E, \Gamma ) $
 +
is such that
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691048.png" /></td> </tr></table>
+
$$
 +
\max _ {e \in E }  | \Gamma ( e) |  \leq  u ,\ \
 +
\min _ {v \in V }  | \Gamma  ^ {-} 1 ( v) |  \geq  w,
 +
$$
  
In extremal problems on packings one usually is required to find packings of maximal cardinality.
+
then the minimum cardinality  $  \kappa ( V, E, \Gamma ) $
 +
of the covering satisfies the inequalities
 +
 
 +
$$
  
Sometimes a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691049.png" /> is defined on the covered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691050.png" /> that takes non-negative integer values, and then the name <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691052.png" />-covering (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691054.png" />-packing) is given to a subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691055.png" /> that satisfies the following condition: For each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691056.png" />, the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691057.png" /> of those elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691058.png" /> that are incident to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691059.png" /> obeys the inequality
+
\frac{| V | }{u}
 +
  \leq  \
 +
\kappa ( V, E, \Gamma ) \leq  \
 +
1 +
 +
\frac{E}{w}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691060.png" /></td> </tr></table>
+
\left (
  
(correspondingly, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691061.png" />). There is a relationship between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691062.png" />-coverings of minimal cardinality and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691063.png" />-packings of maximal cardinality. That is, let two sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691064.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691065.png" /> be given together with a multi-valued mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691066.png" /> and let also functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691067.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691068.png" /> be given on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691069.png" /> such that for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691070.png" />,
+
\frac{ \mathop{\rm ln}  | V | w }{| E | }
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691071.png" /></td> </tr></table>
+
\right ) .
 +
$$
  
Then, if the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691072.png" /> is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691073.png" />-covering of minimal cardinality for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691074.png" />, the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691075.png" /> is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691076.png" />-packing of maximal cardinality, and vice versa. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691077.png" /> is a maximal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691078.png" />-packing, the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691079.png" /> is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691080.png" />-covering of minimal cardinality. The following relate, for example, to the class of problems concerned with coverings and packings:
+
In extremal problems on packings one usually is required to find packings of maximal cardinality.
  
1) Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691081.png" /> be a graph with set of vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691082.png" /> and set of edges <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691083.png" />. If one considers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691084.png" /> as the covered set and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691085.png" /> as the covering set, while the incidence relation for the vertices and edges is taken as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691086.png" />, 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691087.png" /> 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|Graph, numerical characteristics of a]]).
+
Sometimes a function  $  \lambda $
 +
is defined on the covered set $  V $
 +
that takes non-negative integer values, and then the name  $  \lambda $-
 +
covering ( $  \lambda $-
 +
packing) is given to a subset  $  P \subseteq E $
 +
that satisfies the following condition: For each  $  v \in V $,  
 +
the number $  \sigma ( v, P) $
 +
of those elements  $  e \in P $
 +
that are incident to  $  v $
 +
obeys the inequality
  
2) Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691088.png" /> be a non-empty set in a metric space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691089.png" />. A system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691090.png" /> of sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691091.png" /> is called an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691093.png" />-covering of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691094.png" /> if the diameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691095.png" /> of any set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691096.png" /> does not exceed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691097.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691098.png" />. A set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c02691099.png" /> is called an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910101.png" />-net for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910102.png" /> if any point in the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910103.png" /> is at distance not exceeding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910104.png" /> from some point in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910105.png" />. A set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910106.png" /> is called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910108.png" />-distinguishable if any two of different points of it have distance greater than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910109.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910110.png" /> be the minimal number of sets in an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910111.png" />-covering of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910112.png" />, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910113.png" /> be the maximal number of points in an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910114.png" />-distinguishable subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910115.png" />. The number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910116.png" /> is called the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910118.png" />-entropy of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910119.png" />, while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910120.png" /> is called the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910122.png" />-capacity of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910123.png" />. The concepts of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910124.png" />-entropy and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910125.png" />-capacity are used in the theory of approximation of functions and in information theory.
+
$$
 +
\sigma ( v, P)  \geq  \lambda ( v)
 +
$$
  
3) Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910126.png" /> be the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910127.png" />-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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910128.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910129.png" />. Then the set of centres for the sphere packing is a [[Code|code]] that will correct <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910130.png" /> errors. If the packing is perfect, the code is said to be densely packed or perfect.
+
(correspondingly,  $  \sigma ( v, P) \leq  \lambda ( v) $).  
 +
There is a relationship between  $  \lambda $-
 +
coverings of minimal cardinality and $  \lambda $-
 +
packings of maximal cardinality. That is, let two sets  $  V $
 +
and  $  E $
 +
be given together with a multi-valued mapping  $  \Gamma :  E \rightarrow V $
 +
and let also functions  $  \lambda $
 +
and  $  \lambda  ^  \prime  $
 +
be given on  $  V $
 +
such that for each  $  v \in V $,
  
If for the covered set one takes the subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910131.png" /> of vertices in the cube <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910132.png" /> on which some Boolean function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910133.png" /> takes the value 1, while the covering set is the set of faces (intervals) entirely contained in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910134.png" />, then the covering of minimal cardinality will correspond to the shortest disjunctive normal form of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910135.png" />, while the covering with minimal sum of ranks will correspond to the minimal disjunctive normal form of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910136.png" /> (see [[Boolean functions, normal forms of|Boolean functions, normal forms of]]).
+
$$
 +
\lambda ( v) + \lambda  ^  \prime  ( v)  = \
 +
| \Gamma  ^ {-} 1 ( v) | .
 +
$$
  
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.
+
Then, if the set  $  C $
 +
is a  $  \lambda $-
 +
covering of minimal cardinality for  $  ( V, E, \Gamma ) $,  
 +
the set  $  P = E \setminus  C $
 +
is a  $  \lambda  ^  \prime  $-
 +
packing of maximal cardinality, and vice versa. If  $  P $
 +
is a maximal  $  \lambda  ^  \prime  $-
 +
packing, the set  $  C = E \setminus  P $
 +
is a  $  \lambda $-
 +
covering of minimal cardinality. The following relate, for example, to the class of problems concerned with coverings and packings:
  
====References====
+
1) Let  $  G $
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> C.A. Rogers, "Packing and covering" , Cambridge Univ. Press (1964) {{MR|0172183}} {{ZBL|0176.51401}} </TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> L. Fejes Toth, "Lagerungen in der Ebene, auf der Kugel und im Raum" , Springer (1972) {{MR|}} {{ZBL|0229.52009}} </TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> W.W. Peterson, E.J. Weldon, "Error-correcting codes" , M.I.T. (1972) {{MR|0347444}} {{ZBL|0251.94007}} </TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top"> , ''Discrete mathematics and mathematical problems in cybernetics'' , '''1''' , Moscow (1974) (In Russian) {{MR|}} {{ZBL|1185.68346}} </TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top"> F. Harary, "Graph theory" , Addison-Wesley (1972) {{MR|1536844}} {{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}} </TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top"> C. Berge, "Théorie des graphes et leurs applications" , Dunod (1958)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top"> A.G. Vitushkin, "Estimation of the complexity of the tabulation problem" , Moscow (1959) (In Russian)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top"> A.N. Kolmogorov, V.M. Tikhomirov, "<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910137.png" />-entropy and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c026/c026910/c026910138.png" />-capacity of sets in function spaces" ''Uspekhi Mat. Nauk'' , '''14''' : 2 (1959) pp. 3–86 (In Russian) {{MR|0112032}} {{ZBL|}} </TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top"> N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian) {{MR|0362811}} {{ZBL|0524.65001}} </TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top"> S.V. Yablonskii, "Introduction to discrete mathematics" , Moscow (1979) (In Russian) {{MR|0563327}} {{ZBL|}} </TD></TR></table>
+
be a graph with set of vertices  $  V $
 +
and set of edges  $  E $.  
 +
If one considers  $  V $
 +
as the covered set and $  E $
 +
as the covering set, while the incidence relation for the vertices and edges is taken as  $  I $,  
 +
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  $  I $
 +
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|Graph, numerical characteristics of a]]).
  
 +
2) Let  $  V $
 +
be a non-empty set in a metric space  $  R $.
 +
A system  $  \pi $
 +
of sets  $  U \subseteq R $
 +
is called an  $  \epsilon $-
 +
covering of  $  V $
 +
if the diameter  $  d( U) $
 +
of any set  $  U \in \pi $
 +
does not exceed  $  2 \epsilon $
 +
and  $  V \subseteq \cup _ {U \in \pi }  U $.
 +
A set  $  S \subseteq R $
 +
is called an  $  \epsilon $-
 +
net for  $  V $
 +
if any point in the set  $  V $
 +
is at distance not exceeding  $  \epsilon $
 +
from some point in  $  S $.
 +
A set  $  U \subseteq R $
 +
is called  $  \epsilon $-
 +
distinguishable if any two of different points of it have distance greater than  $  \epsilon $.
 +
Let  $  N _  \epsilon  ( V) $
 +
be the minimal number of sets in an  $  \epsilon $-
 +
covering of  $  V $,
 +
and let  $  M _  \epsilon  ( V) $
 +
be the maximal number of points in an  $  \epsilon $-
 +
distinguishable subset of  $  V $.
 +
The number  $  \mathop{\rm log} _ {2}  N _  \epsilon  ( V) $
 +
is called the  $  \epsilon $-
 +
entropy of  $  V $,
 +
while  $  \mathop{\rm log} _ {2}  M _  \epsilon  ( V) $
 +
is called the  $  \epsilon $-
 +
capacity of  $  V $.
 +
The concepts of  $  \epsilon $-
 +
entropy and  $  \epsilon $-
 +
capacity are used in the theory of approximation of functions and in information theory.
  
 +
3) Let  $  B  ^ {n} $
 +
be the  $  n $-
 +
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  $  r $
 +
in  $  B  ^ {n} $.
 +
Then the set of centres for the sphere packing is a [[Code|code]] that will correct  $  r $
 +
errors. If the packing is perfect, the code is said to be densely packed or perfect.
  
====Comments====
+
If for the covered set one takes the subset  $  N _ {f} $
 +
of vertices in the cube  $  B  ^ {n} $
 +
on which some Boolean function  $  f( x _ {1} \dots x _ {n} ) $
 +
takes the value 1, while the covering set is the set of faces (intervals) entirely contained in  $  N _ {f} $,
 +
then the covering of minimal cardinality will correspond to the shortest disjunctive normal form of  $  f( x _ {1} \dots x _ {n} ) $,
 +
while the covering with minimal sum of ranks will correspond to the minimal disjunctive normal form of  $  f( x _ {1} \dots x _ {n} ) $(
 +
see [[Boolean functions, normal forms of|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====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> A. Schrijver (ed.) , ''Packing and covering in combinatorics'' , CWI , Amsterdam (1979) {{MR|0562282}} {{ZBL|0419.00004}} </TD></TR></table>
+
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> C.A. Rogers, "Packing and covering" , Cambridge Univ. Press (1964) {{MR|0172183}} {{ZBL|0176.51401}} </TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> L. Fejes Toth, "Lagerungen in der Ebene, auf der Kugel und im Raum" , Springer (1972) {{MR|}} {{ZBL|0229.52009}} </TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> W.W. Peterson, E.J. Weldon, "Error-correcting codes" , M.I.T. (1972) {{MR|0347444}} {{ZBL|0251.94007}} </TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top"> , ''Discrete mathematics and mathematical problems in cybernetics'' , '''1''' , Moscow (1974) (In Russian) {{MR|}} {{ZBL|1185.68346}} </TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top"> F. Harary, "Graph theory" , Addison-Wesley (1972) {{MR|1536844}} {{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}} </TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top"> C. Berge, "Théorie des graphes et leurs applications" , Dunod (1958)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top"> A.G. Vitushkin, "Estimation of the complexity of the tabulation problem" , Moscow (1959) (In Russian)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top"> A.N. Kolmogorov, V.M. Tikhomirov, "$\epsilon$-entropy and $\epsilon$-capacity of sets in function spaces" ''Uspekhi Mat. Nauk'' , '''14''' : 2 (1959) pp. 3–86 (In Russian) {{MR|0112032}} {{ZBL|}} </TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top"> N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian) {{MR|0362811}} {{ZBL|0524.65001}} </TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top"> S.V. Yablonskii, "Introduction to discrete mathematics" , Moscow (1979) (In Russian) {{MR|0563327}} {{ZBL|}} </TD></TR>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top"> A. Schrijver (ed.) , ''Packing and covering in combinatorics'' , CWI , Amsterdam (1979) {{MR|0562282}} {{ZBL|0419.00004}} </TD></TR></table>

Latest revision as of 11:05, 26 March 2023


Combinatorial configurations related to multi-valued mappings of one set into another. Assume that one is given sets $ V $ and $ E $ together with a multi-valued mapping $ \Gamma $ of $ E $ into $ V $. Let $ \Gamma ( e) $ be the image of an element $ e \in E $ under $ \Gamma $ and, for any $ C \subseteq E $, let $ \Gamma ( C) = \cup _ {e \in E } \Gamma ( e) $. A subset $ C \subseteq E $ is called a covering for $ ( V, E, \Gamma ) $ if $ \Gamma ( C) = V $. A subset $ P \subseteq E $ is called a packing for $ ( V, E, \Gamma ) $ if for any two different elements $ e _ {i} $ and $ e _ {j} $ from $ P $ the sets $ \Gamma ( e _ {i} ) $ and $ \Gamma ( e _ {j} ) $ do not intersect. A subset $ P \subseteq E $ is called a perfect packing, or a perfect covering, if $ P $ is simultaneously a covering and a packing. The set $ E $ is called the covering set, and the set $ V $ is called the covered set. If the inverse mapping $ \Gamma ^ {-} 1 $ is such that $ \Gamma ^ {-} 1 ( V) = E $, one can consider $ V $ as a covering set and $ E $ as the covered set. The mapping $ \Gamma : E \rightarrow V $ defines an incidence relation $ I $ for which $ v $ from $ V $ and $ e $ from $ E $ are incident (denoted by $ vIe $) if $ v \in \Gamma ( e) $.

The concepts of a packing and a covering are related to extremal problems involving the search for packings and coverings (for any given triple $ ( V, E, \Gamma ) $) that provide an extremum for some functional. That functional may, for example, be specified by means of a function that puts each element $ e $ from $ E $ into correspondence with a non-negative real number $ w( e) $, called the weight of the element $ e $. The minimal covering problem consists in constructing a covering $ C $ for which $ \sum _ {e \in C } w( e) $ takes a minimal value. One often considers the case where $ w( e) \equiv 1 $; here one is concerned with finding a covering of minimal cardinality, or a so-called least covering. If the triple $ ( V, E, \Gamma ) $ is such that

$$ \max _ {e \in E } | \Gamma ( e) | \leq u ,\ \ \min _ {v \in V } | \Gamma ^ {-} 1 ( v) | \geq w, $$

then the minimum cardinality $ \kappa ( V, E, \Gamma ) $ of the covering satisfies the inequalities

$$ \frac{| V | }{u} \leq \ \kappa ( V, E, \Gamma ) \leq \ 1 + \frac{E}{w} \left ( \frac{ \mathop{\rm ln} | V | w }{| E | } \right ) . $$

In extremal problems on packings one usually is required to find packings of maximal cardinality.

Sometimes a function $ \lambda $ is defined on the covered set $ V $ that takes non-negative integer values, and then the name $ \lambda $- covering ( $ \lambda $- packing) is given to a subset $ P \subseteq E $ that satisfies the following condition: For each $ v \in V $, the number $ \sigma ( v, P) $ of those elements $ e \in P $ that are incident to $ v $ obeys the inequality

$$ \sigma ( v, P) \geq \lambda ( v) $$

(correspondingly, $ \sigma ( v, P) \leq \lambda ( v) $). There is a relationship between $ \lambda $- coverings of minimal cardinality and $ \lambda $- packings of maximal cardinality. That is, let two sets $ V $ and $ E $ be given together with a multi-valued mapping $ \Gamma : E \rightarrow V $ and let also functions $ \lambda $ and $ \lambda ^ \prime $ be given on $ V $ such that for each $ v \in V $,

$$ \lambda ( v) + \lambda ^ \prime ( v) = \ | \Gamma ^ {-} 1 ( v) | . $$

Then, if the set $ C $ is a $ \lambda $- covering of minimal cardinality for $ ( V, E, \Gamma ) $, the set $ P = E \setminus C $ is a $ \lambda ^ \prime $- packing of maximal cardinality, and vice versa. If $ P $ is a maximal $ \lambda ^ \prime $- packing, the set $ C = E \setminus P $ is a $ \lambda $- covering of minimal cardinality. The following relate, for example, to the class of problems concerned with coverings and packings:

1) Let $ G $ be a graph with set of vertices $ V $ and set of edges $ E $. If one considers $ V $ as the covered set and $ E $ as the covering set, while the incidence relation for the vertices and edges is taken as $ I $, 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 $ I $ 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 $ V $ be a non-empty set in a metric space $ R $. A system $ \pi $ of sets $ U \subseteq R $ is called an $ \epsilon $- covering of $ V $ if the diameter $ d( U) $ of any set $ U \in \pi $ does not exceed $ 2 \epsilon $ and $ V \subseteq \cup _ {U \in \pi } U $. A set $ S \subseteq R $ is called an $ \epsilon $- net for $ V $ if any point in the set $ V $ is at distance not exceeding $ \epsilon $ from some point in $ S $. A set $ U \subseteq R $ is called $ \epsilon $- distinguishable if any two of different points of it have distance greater than $ \epsilon $. Let $ N _ \epsilon ( V) $ be the minimal number of sets in an $ \epsilon $- covering of $ V $, and let $ M _ \epsilon ( V) $ be the maximal number of points in an $ \epsilon $- distinguishable subset of $ V $. The number $ \mathop{\rm log} _ {2} N _ \epsilon ( V) $ is called the $ \epsilon $- entropy of $ V $, while $ \mathop{\rm log} _ {2} M _ \epsilon ( V) $ is called the $ \epsilon $- capacity of $ V $. The concepts of $ \epsilon $- entropy and $ \epsilon $- capacity are used in the theory of approximation of functions and in information theory.

3) Let $ B ^ {n} $ be the $ n $- 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 $ r $ in $ B ^ {n} $. Then the set of centres for the sphere packing is a code that will correct $ r $ 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 $ N _ {f} $ of vertices in the cube $ B ^ {n} $ on which some Boolean function $ f( x _ {1} \dots x _ {n} ) $ takes the value 1, while the covering set is the set of faces (intervals) entirely contained in $ N _ {f} $, then the covering of minimal cardinality will correspond to the shortest disjunctive normal form of $ f( x _ {1} \dots x _ {n} ) $, while the covering with minimal sum of ranks will correspond to the minimal disjunctive normal form of $ f( x _ {1} \dots x _ {n} ) $( 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, "$\epsilon$-entropy and $\epsilon$-capacity of sets in function spaces" Uspekhi Mat. Nauk , 14 : 2 (1959) pp. 3–86 (In Russian) MR0112032
[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
[a1] A. Schrijver (ed.) , Packing and covering in combinatorics , CWI , Amsterdam (1979) MR0562282 Zbl 0419.00004
How to Cite This Entry:
Covering and packing. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Covering_and_packing&oldid=37473
This article was adapted from an original article by A.A. Sapozhenko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article