Покрытия и упаковки

- комбинаторные конфигурации, связанные с многозначным отображением одного множества на другое. Пусть заданы множества Vи Еи многозначное отображение Г множества Ена множество V. Пусть Г(е).- образ элемента [img: http://localhost:8080/file/041723-31.jpg] при отображении Г и для любого [img: http://localhost:8080/file/041723-32.jpg] пусть Г(С) = [img: http://localhost:8080/file/041723-33.jpg]. Подмножество [img: http://localhost:8080/file/041723-34.jpg] наз. покрытием (для (V, Е, Г)), если Г(С)=V. Подмножество [img: http://localhost:8080/file/041723-35.jpg] наз. упаковкой, или укладкой (для (V, Е, Г)), если для любых двух различных элементов е i, е j из Рмножества Г(е i). и Г(е j) не пересекаются. Подмножество [img: http://localhost:8080/file/041723-36.jpg] наз. совершенной упаковкой, или совершенным покрытием, если Рявляется одновременно и покрытием, и упаковкой. Множество Еназ. покрывающим, а множество V - покрываемым. Если обратное отображение Г -1 таково, что Г -1(V)=Е, то можно рассматривать V как покрывающее множество, а Екак покрываемое. Отображение [img: http://localhost:8080/file/041723-37.jpg] определяет отношение инцидентности I, при к-ром v из Vи е из Еинцидентны (обозначение vIe), если [img: http://localhost:8080/file/041723-38.jpg]. С понятиями упаковки и покрытия связаны экстремальные задачи, заключающиеся в отыскании (по произвольно заданной тройке (V, Е, Г)) П. и у., доставляющих экстремум тех или иных функционалов. Такой функционал можно, напр., задать с помощью функции, сопоставляющей каждому элементу еиз Енеотрицательное действительное число w(e), наз. весом элемента е. Задача о минимальном покрытии заключается в построении покрытия С, для к-рого [img: http://localhost:8080/file/041723-39.jpg] принимает минимальное значение. Часто рассматривается случай, когда [img: http://localhost:8080/file/041723-40.jpg]; здесь речь идет о нахождении покрытия минимальной мощности, или т. н. кратчайшего покрытия. Если тройка (V, Е, Г) такова, что [img: http://localhost:8080/file/041723-41.jpg] то минимальная мощность [img: http://localhost:8080/file/041723-42.jpg] покрытия удовлетворяет неравенствам [img: http://localhost:8080/file/041723-43.jpg] В экстремальных задачах об упаковках чаще всего требуется найти упаковки максимальной мощности. Иногда на покрываемом множестве Vзадается функция l, принимающая целые неотрицательные значения, тогда l-покрытием (l-упаковкой) наз. подмножество [img: http://localhost:8080/file/041723-44.jpg], удовлетворяющее условию: для каждого [img: http://localhost:8080/file/041723-45.jpg] число s(v, Р).тех элементов [img: http://localhost:8080/file/041723-46.jpg], к-рые инцидентны элементу v, подчиняется неравенству [img: http://localhost:8080/file/041723-47.jpg] (соответственно [img: http://localhost:8080/file/041723-48.jpg]). Существует связь между l-покрытиями минимальной мощности и l-упаковками максимальной мощности. Именно, пусть заданы множества Vи Е, многозначное отображение Г: Е [img: http://localhost:8080/file/041723-49.jpg] V, а также функции l и l' на множестве Vтакие, что для каждого [img: http://localhost:8080/file/041723-50.jpg]: [img: http://localhost:8080/file/041723-51.jpg] Тогда, если множество Сесть минимальное по мощности l-покрытие для (V, Е, Г), то множество Р= EС является максимальной по мощности l'-упаковкой, и наоборот: если Р- максимальная l'-упаковка, то множество С=ЕР. есть l-покрытие минимальной мощности. К классу задач о П. и у. относятся, напр., следующие: 1) Пусть G - граф с множеством вершин Vи множеством ребер Е. Если рассматривать множество Vв качестве покрываемого, множество Е - в качестве покрывающего и отношение инцидентности вершин и ребер - в качестве I, то покрытием является реберное покрытие графа, упаковкой - паросочетание, совершенной упаковкой - совершенное паросочетание. Если в качестве и покрывающего, и покрываемого взять множество вершин, а в качестве I - отношение смежности вершин, то покрытием будет внешне устойчивое множество, а упаковкой - внутренне устойчивое множество; при этом минимальная мощность покрытия наз. числом внешней устойчивости, а максимальная мощность упаковки - числом внутренней устойчивости (см. Графов числовые характеристики). 2) Пусть V - непустое множество в метрич. пространстве R. Система л множеств [img: http://localhost:8080/file/041723-52.jpg] наз. e-покрытием множества V, если диаметр d(U).любого множества [img: http://localhost:8080/file/041723-53.jpg] не превосходит 2e и [img: http://localhost:8080/file/041723-54.jpg]. Множество [img: http://localhost:8080/file/041723-55.jpg] наз. e-сетью для множества V, если любая точка множества Vнаходится на расстоянии, не превышающем e, от нек-рой точки из S. Множество [img: http://localhost:8080/file/041723-56.jpg] наз. 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,..., х п).(см. Булевых функций нормальные формы). В задачах о П. и у. оцениваются их мощности, исследуются вопросы существования, построения, перечисления совершенных упаковок, изучаются возможности построения эффективных алгоритмов для решения этих задач.