Математическая энциклопедия - покрытия и упаковки

комбинаторные конфигурации, связанные с многозначным отображением одного множества на другое. Пусть заданы множества 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 отношение смежности вершин, то покрытием будет внешне устойчивое множество, а упаковкой внутренне устойчивое множество; при этом минимальная мощность покрытия наз. числом внешней устойчивости, а максимальная мощность упаковки числом внутренней устойчивости (см. Графов числовые характеристики).