Покрытия И Упаковки

Комбинаторные конфигурации, связанные с многозначным отображением одного множества на другое. Пусть заданы множества Vи Еи многозначное отображение Г множества Ена множество V. Пусть Г(е).- образ элемента при отображении Г и для любого пусть Г(С) =. Подмножество наз. покрытием (для (V, Е, Г)), если Г(С)=V. Подмножество наз. упаковкой, или укладкой (для (V, Е, Г)), если для любых двух различных элементов е i, е j из Рмножества Г( е i). и Г(е j) не пересекаются. Подмножество наз. совершенной упаковкой, или совершенным покрытием, если Рявляется одновременно и покрытием, и упаковкой. Множество Еназ. покрывающим, а множество V — покрываемым. Если обратное отображение Г -1 таково, что Г -1(V)=Е, то можно рассматривать V как покрывающее множество, а Екак покрываемое. Отображение определяет отношение инцидентности I, при к-ром v из Vи е из Еинцидентны (обозначение vIe), если . С понятиями упаковки и покрытия связаны экстремальные задачи, заключающиеся в отыскании (по произвольно заданной тройке (V, Е, Г)) П. и у., доставляющих экстремум тех или иных функционалов. Такой функционал можно, напр., задать с помощью функции, сопоставляющей каждому элементу еиз Енеотрицательное действительное число w(e), наз. весом элемента е. Задача о минимальном покрытии заключается в построении покрытия С, для к-рого принимает минимальное значение. Часто рассматривается случай, когда ; здесь речь идет о нахождении покрытия минимальной мощности, или т. н. кратчайшего покрытия. Если тройка (V, Е, Г) такова, что то минимальная мощность покрытия удовлетворяет неравенствам В экстремальных задачах об упаковках чаще всего требуется найти упаковки максимальной мощности. Иногда на покрываемом множестве Vзадается функция l, принимающая целые неотрицательные значения, тогда l-покрытием (l-упаковкой) наз. подмножество , удовлетворяющее условию: для каждого число s(v, Р).тех элементов , к-рые инцидентны элементу v, подчиняется неравенству (соответственно ). Существует связь между l-покрытиями минимальной мощности и l-упаковками максимальной мощности. Именно, пусть заданы множества Vи Е, многозначное отображение Г : Е V, а также функции l и l' на множестве Vтакие, что для каждого : Тогда, если множество Сесть минимальное по мощности l-покрытие для (V, Е, Г), то множество Р= EС является максимальной по мощности l'-упаковкой, и наоборот: если Р- максимальная l'-упаковка, то множество С=ЕР. есть l-покрытие минимальной мощности. К классу задач о П. и у. относятся, напр., следующие: 1) Пусть G — граф с множеством вершин Vи множеством ребер Е. Если рассматривать множество Vв качестве покрываемого, множество Е — в качестве покрывающего и отношение инцидентности вершин и ребер — в качестве I, то покрытием является реберное покрытие графа, упаковкой — паросочетание, совершенной упаковкой — совершенное паросочетание. Если в качестве и покрывающего, и покрываемого взять множество вершин, а в качестве I — отношение смежности вершин, то покрытием будет внешне устойчивое множество, а упаковкой — внутренне устойчивое множество; при этом минимальная мощность покрытия наз. числом внешней устойчивости, а максимальная мощность упаковки — числом внутренней устойчивости (см. Графов числовые характеристики). 2) Пусть V — непустое множество в метрич. пространстве R. Система л множеств наз. e-покрытием множества V, если диаметр d(U).любого множества не превосходит 2e и . Множество наз. e-сетью для множества V, если любая точка множества Vнаходится на расстоянии, не превышающем e, от нек-рой точки из S. Множество наз. e-различимым, если любые две его различные точки лежат на расстоянии, большем e. Пусть Ne (V) — минимальное число множеств в e-покрытии множества V, а М e(V) — максимальное число точек в e-различимом подмножестве множества V. Число log2Ne (V).наз. e-энтропией множества V, а log2Me( V).наз. e-емкостью множества V. Понятия e-энтропии и e-емкости применяются в теории приближения функций и в теории информации. 3) Пусть В n — единичный n-мерный куб с метрикой Хемминга и покрываемое множество есть множество его вершин, а покрывающее множество — множество шаров радиуса r в В n. Тогда множество центров шаров упаковки есть код, исправляющий rошибок. Если упаковка является совершенной, то код наз. плотно упакованным, или совершенным. Если в качестве покрываемого множества взять подмножество Nf вершин куба В n, на к-ром нек-рая булева функция f( х 1, . .., х п).принимает значение 1, а в качестве покрывающего — множество граней (интервалов), целиком содержащихся в Nf, то покрытие наименьшей мощности будет соответствовать кратчайшей дизъюнктивной нормальной форме функции f(x1,..., х n), а покрытие с наименьшей суммой рангов — минимальной дизъюнктивной нормальной форме функции f(x1 ,..., х п).(см. Булевых функций нормальные формы). В задачах о П. и у. оцениваются их мощности, исследуются вопросы существования, построения, перечисления совершенных упаковок, изучаются возможности построения эффективных алгоритмов для решения этих задач. Лит.:[1] Роджерс К., Укладки и покрытия, пер. с англ., М., 1968; [2] Тот Л. Ф., Расположения на плоскости, на сфере и в пространстве, пер. с нем., М., 1958; [3] Питерсон У., Уэлдон Э., Коды, исправляющие ошибки, пер. с англ., М., 1976; [4] Дискретная математика и математические нопросы кибернетики, т. 1, М., 19.74; [5] Xарари Ф., Теория графов, пер. с англ., М., 1973; [6] Берж К., Теория графов и ее применения, пер. с франц., М., 1962; [7] Витушкин А. Г., Оценка сложности задачи табулирования, М., 1959; [8] Колмогоров А. Н., Тихомиров В. М., "Успехи матем. наук", 1959, т. 14, в. 2, с. 3-86; [9] Бахвалов Н. С., Численные методы, 2 изд., М., 1975; [10] Яблонский С. В., Введение в дискретную математику, М., 1979. А. А. Сапоженко.