Содержание к диссертации
Введение
Глава I. Построение решений основной дискретной изопериметрической задачи . 13
I. Определение рассматриваемых классов решений 13
1. Постановка задачи 13
2. Теорема о сводимости 14
2. Построение всех оптимальных множеств особой мощности 16
1. Описание используемого подхода 16
2. Вычисление радиусов І -шаров и некоторые вспомогательные утверждения 21
3. Множества, перестановочно-эквивалентные стандартному размещению 29
4. Описание всех оптимальных множеств из класса fllw
5. Описание всех оптимальных множеств из класса
6. Актуальность описашш всех оптимальных множеств особой мощности 43
3. Построение решений, имеющих неособую мощность 46
1. Достаточное условие несуществования оптимальных критических множеств неособой мощности. 46
2. Построение оптимальных критических множеств из неоптимальных 49
Глава 2. Изоперметрические задачи на множествах специальной структуры 56
I. Теорема о четных слоях куба D 56
1. Постановка задачи 56
2. Доказательство основного результата. 56
3. Обобщения основного результата 58
2. Мзопериметрическая задача для К -того слоя куба В 60
1. Постановка задачи 60
2. Каноническое множество 61
3. Некоторые определения и вспомогательные утверждения 64
4. Леммы о конечных отрезках 67
5. Доказательство оптимальности канонического множества при К^2. и К-3 70
6. Мощность окрестности канонического множества. 79
7. Исследование множества S(*S к,т,) на ассим-птотическую оптимальность при K=O(JKJII h.-*., 81
8. Сравнение мощностей множеств о (К, к, т) и /І(и., к,иг) при к=С-п,0Л <С<0,$ 91
Глава 3. Изопериметрические задачи, возникающие при различных определениях граничных вершин 96
1. Обзор постановок задач 96
2. Обобщение изопериметрической задачи, рассматриваемой в главе I 97
3. Центральная теорема 104
4. Случаи, когда окрестность состоит из линейно - 107
5. Дальнейшее обобщение центральной теоремы.»... 108
Литература
- Построение всех оптимальных множеств особой мощности
- Актуальность описашш всех оптимальных множеств особой мощности
- Каноническое множество
- Случаи, когда окрестность состоит из линейно
Введение к работе
В диссертации исследуется задача, являющаяся .дискретным аналогом известной классической изопериметрической задачи. На её основе производится построение решений некоторых других экстремальных комбинаторных проблем.
Как известно, классическая изопериметрическая задача заключается в отыскании среди всех простых замкнутых кривых с фиксированным периметром р такой, которая отделяет максимальную площадь S . В двойственной постановке указанная задача состоит в нахождении среди всех фигур площади о такой, которая имеет наименьший периметр р . Эти задачи были известны давно, и полное их решение впервые было найдено в XIX столетии на основе аппарата вариационного исчисления [V] . Оказалось, что округшость и круг являются единственными решениями соответствующих задач.
В настоящее время под изопериметрическими подразумевают широкий класс задач, связанных с исследованием соотношений между мощностью множеств различной природы и мощностью границ этих множеств. В диссертации исследуются дискретные изопери-метрические задачи.
Рассмотрим ^ -мерный единичный куб:
Определим расстояние Хемминга между вершинами куба:
Скажем, что вершина /или точка/ о^А является граничной для множества . если
шар радиуса h в метрике Хемминга с центром в точке cL є ) . Совокупность всех граничных точек множества А будем обозначать через ГҐА).
Дискретная изопериметрическая задача состоит в том, чтобы
по произвольному заданному целому числу т, из сегмента [ ^ 2. J найти такое нь -элементное подмножество А /3 , множество
граничных точек которого имеет минимально возможную мощность, т.е. такое, что |ГТА*)|= Міг ІГ(Л)\.
Множество А называется оптимальным.
Сформулированная дискретная изопериметрическая задача была рассмотрена в ряде работ / см. [l5J , [іб] , [зсГ] , j^28]/. Интерес к ней был связан как с некоторыми вопросами вариационного принципа алгебры логики, так и с задачами теории кодирования и теории графов.
Изопериметрические задачи находят широкое применение в булевой алгебре / [io] - l2j , [l4J/ при исследовании метрических характеристик подмножеств К -мерного единичного куба, а также при решении задач минимизации булевых функций. В ряде случаев необходимо уметь оценивать число подмножеств куба, , имеющих заданную мощность границы [l8j .
Тесные всязи с рассматриваемыми в работе вопросами: имеют задачи теории кодирования / [із]] , ^23^ , 34]/. Как известно, основная задача построения кодов Хемминга состоит в нахождении плотных упаковок К -мерных шаров в К -мерном кубе. Если ко-довые наборы взвешенные, то требуется найти плотную упаковку шаров разных размерностей. Наличие пересечений в рассматриваемой упаковке соответствует задаче приближенного декодирования при разных допустимых значениях смещений пар кодовых слов. "Дмегащиеся результаты указывают на минимальную область пространства > , где могут быть размещены кодовые слова с допустимыми областями их изменений.
Рассмотрим теперь граф р -элементным
множеством вершин V и Q—элементным множеством ребер В. Пусть f - нумерация вершин графа (* числами I, 2,..,,, р
Если Є^Е и Є^(Ч,1Гг) , то число назовем
длиной ребра Є . Определим длину нумерацииг"' ^ как число 2L> Ае и ширину нумерации как max Ле . Во многих приклад-ных задачах, в том числе в задачах автоматизации проектирования ЭВМ / [17 J , [20]/, ставится вопрос о нахождении нумерации у графа Q при минимизации длины и ширины нумерации. Это соответствует, например, минимизации общей или максимальной длины соединений при линейном размещении элементов электрической схемы.
В работе [28] доказано сведение проблемы нахождения нумерации с минимальной шириной для случая G - & к решению дискретной изопериметрической задачи, и найдены условия, при которых возможно такое сведение при произвольном графе G
По-видимому, впервые задача построения оптимальных по длине и ширине нумераций вершин графов была явно сформулирована в работе [32] , где указывалось на возможность использования таких нумераций при кодировании информации с целью минимизации средней или наибольшей ошибки при передаче сообщений.
При численном решении многих инженерных, физических и математических задач в настоящее время широко используется метод конечных элементов / [l9j/. При примении этого метода необходимо произвести нумерацию узлов дискретной решетки, аппроксимирующей заданную непрерывную область. Таким образом, возникает задача построения нумераций вершин некоторых классов графов. При этом также следует стремиться получить нумерации с минимальной шириной.
Имеется ряд работ, посвященных указанной проблеме / [24J , \jW] » [.29]/. При построении соответствующих нумераций помимо специальных комбинаторных построений используется изопериметри-ческий подход.
Необходимость изучения свойств решений дискретной изопери-
ческой задачи возникает при синтезе многопроцессорных вычислительных систем из ненадежных компонентов J^2IJ . Использование соотношений между мощностью оптимального множества и числом , его граничных точек позволяет оценить надежность указанных систем.
Множество всех решений дискретной изопериметрической задачи используется в теории распознавания образов при описании задач, наиболее соответствующих гипотезам распознавания типа компактности [з] . При исследовании изопериметрической задачи выяснилось, что дискретная природа И, -мерного единичного куба накладывает существенный отпечаток на свойства ее решений, так, что в отличие от "непрерывной" задачи, где решение единственно, в дискретном случае множество всех решений содержит такие элементы, которые не соответствуют обычным представлениям о компактности.
В теоретическом плане изопериметрические задачи представляют интерес в связи с экстремальными задачами для семейств подмножеств конечного множества. Некоторые результаты их исследования носят классический характер /см.,например, теорему Краскаля-Катона [30] , [зз] / и используются в самых различных областях комбинаторики / [25J , [26] , [зі] , [зб] , [зб]/ и теории чисел [22] .
История решения дискретной изопериметрической задачи такова. В 1966 году Харпер [28j и независимо от него Катона[зо]в 1975 году построили одно из оптимальных множеств, называемое стандартным размещением. В 1969 году Р.Г. Нигматуллин [iб] доказал, что в случае, когда мощность множества m является мощностью шара, т.е. m-=Zl(6'j при некотором к , О^К^/г ,
с-О
то шар радиуса К является единственным с точностью до выбора центра решением указанной задачи.
Далее, в 1980 году Л.А.Асланян, В.М.Карахашш, Б„Е.Торосян Г4І показали, что любое оптимальное множество А мощности
К. / it
нг s Z (^ ) + о , 0 ~ 0 * (k+i/ содержит некоторый шар SK (<*-) радиуса К , т.е. S^C^^A . Кроме того, в случае если *п. является особой мощностью /подробнее см.ниже/, существует точка
cLe А , такая, что $к ^^ ^ А — >\+<? 6* J . Эти же авторы впервые отметили, что в некоторых случаях во множестве А существуют такие точки, произвольное размещение которых в пространстве & не влияет на величину границы А .
Таким образом, для завершения описания всех оптимальных подмножеств куба /2> необходимо уточнить строение оптимальных множеств особой мощности и исследовать оптимальные множества не особой мощности. Изучению этих вопросов посвящена первая глава диссертации.
В первом параграфе этой главы приводится математическая постановка рассматриваемой задачи и доказываются результаты по сведению описания одних классов решений к другим. Обозначим
через Р(А) внутренность множества А , т.е. ЯМ)=А\ ГС/0.
Назовем А- Ь критическим /по компактности/ множеством, если для любой ^еА, IР(А\^ч < I Р(Л)\ . Основным результатом этого параграфа является теорема I.I, из которой вытекает способ построения всех оптимальных некритических множеств при условии, что построены все оптимальные критические множества. В соответствии с этим далее рассматриваются лишь оптимальные критические множества.
Назовем число w- особой мощностью, если все оптимальные ft -элементные подмножества куба В являются критическими. Например, числа вида 21(^/, Кк^,2,--» h/ суть особый мощности.
В 2 главы I приведено описание всех оптимальны:!?: множеств особой мощности. В пункте I этого параграфа изложен
используемый подход и сформулированы основные утверждения. Главными результатами п.4 и 5 2 являются теоремы 1.8 и 1.9, из которых вытекает способ построения всех оптимальных множеств
особой мощности. В теореме I.II и следствии из нее доказано,
и <\h-±
___ r „... равно d . Таким обра-
зом, ровно для половины целых чисел иъ из сегмента L 4., J в 2 гл.1 построены все оптимальные ^ -элементные множества.
Третий параграф главы I посвящен построению оптимальных критических множеств неособой мощности. Обозначим через р(т,п) число внутренних точек у оптимального /п -элементного подмножества А- Ё> Основным результатом п.1 этого параграфа является теорема I.I3, в которой доказано, что если Ыт,к) есть особая мощность, то не существует оптимальных т -элементных множеств, которые нельзя было бы построить, исходя из результатов I и 2 гл.І. В теореме I.I4 доказано, что число неособых мощностей т. таких, что р(піуУг) особая мощность, ассимптотически
L. _ Л
равно <Е . Таким образом, учитывая результаты 2 гл.1, показано, что для некоторых чисел \т , доля которых составляет ас-
симптотически -п от всех возможных значений, построены все оптимальные иг -элементные подмножества куба Е)
3 пункте 2 3 изучаются оптимальные подмножества оставшихся мощностей. Построена процедура, позволяющая из любого критического подмножества куба Ь получить оптимальное критическое подмножество куба большей размерности такое, что структура полученного множества в некотором смысле совпадает со структурой исходного. В теоремах I.I5 и I.I6 доказано,что при этом произвольное критическое подмножество куба В становится оптимальным при "вложении" его в пространство большей размерности.
Указанные результаты отражают трудности,возникающие при
-io-
описании оптимальных множеств оставшихся мощностей, и в то же время являются способом построения таких множеств.
Во второй главе диссертации изучаются изопериметрические задачи на множествах специальной структуры.
Пусть >к - { %є Ьк- /|<|| = Y- ^с ~ к J . Это мно-жество называется К -тым слоем куба Ь . Обозначите через & (о) совокупность четных слоев куба Б , т.е.
ЬК(0)-- [&$: K = 0(*W*)J. Определим окрестность множества A : 0(A)-{^ о лА-^к^пг j.
В 1 главы 2 изучается изопериметрическая задача для
А Й
подмножеств п-Ь (о)% заключающаяся в построении такого м. -элементного множества А - &(о) / ± < т 2 /, мощность окрестности которого имеет наїшеньшее возможное значение /(32^. Решение этой задачи было использовано в работе JJC8]. Основным результатом параграфа I является теорема 2.1, утверждающая о том, что рассматриваемая задача эквивалентна в дискретной изо-периметрической задаче, изучаемой в главе I. Зная все решения одной из указанных задач,можно с помощью построенных в этой теореме преобразований получить все решения другой.
Во втором параграфе главы 2 исследуется изопериметричес-кая задача для подмножеств К -того слоя куба о , в которой требуется построить иг -элементное / і - ^ - (k / / подмножество слоя & к , обладающее наименьшей возможной мощностью множества 0(A) . Эта задача была поставлена в работе |_30J и возникает принекоторых исследованиях, связанных с минимизацией булевых функций. Результаты других авторов по решению указанной задачи в печати отражены не были.
В диссертации рассматриваемая задача решается для случаев К = Z ж К = 3 . Основными утверждениями пунктов 2-5 2 гл. 2 являются теоремы 2.4 и.2.6, в которых доказывается, что
-II-
множества \Л(^к,т) и ofaK^m) являются решениями поставленной задачи в случаях к= и К-3 соответственно. Определение множеств MOs»c,nt) и $(ь,к,т) см. в главе 2. В пункте 7 2 проводится исследование, направленное на приближенное решение задачи в случае К,-*о . в теореме 2.8 и следствии из нее доказано, что (Л(н,,к,т.) является ассимптотически оптимальнім множеством при К= о(Ьь), в теореме 2.10 показано, что уже не является ассимптотически оптимальным при К-с-іг , 0.к < С < о.5 , и что множество S0*i к, m) при этом в некоторых случаях имеет меньшую по порядку окрестность. В ходе исследования установлено, что отдельные утверждения о свойствах решений рассматриваемой задачи справедливы и при произвольных К и т /см.,например, теорему 2.5/.
В последней, третьей главе диссертации изучается семейство изопериметрических задач, возникающих при различных толкованиях граничных вершин.
В пункте 2 главы 3 рассматривается обобщение изопериметри-ческой задачи из главы I. Считается, что точка <^6А является -граничной / 1 - - *ъ ./, если S^ (<)Ф А .Назовем множество А -оптимальным, если оно имеет наименьшее возможное число -граничных вершин среди всех подмножеств той же мощности. Основным утверждением п.2 гл.З является Теотэема 3.1. Если А 1-оптимальное множество, то А также t -оптимальное множество при t г<2
, Из этой теоремы вытекает теорема 6.1 из статьи Л.А.Асла-няна \^~\ , в которой утверждается, что если А -оптимальное множество, то существует некоторая точка ^- А такая, что
О к () - А . Теорема 3.1 позволяет также определить число указанных точек.
Рассмотрим обобщение понятий граничных и внутренних вер-
шин. В топологии точку &еА называют внутренней точкой множества А , если некоторая окрестность этой точки входит в А . Под окрестностью точки понимают любое открытое множество, содержащее О- . Так как определение открытого множества тесным образом связано с операцией предельного перехода, которая не имеет особого значения в конечных пространствах, то понятие окрестности точки в последнем случае может иметь множество трактовок.
В пункте II главы 3 показано, что если по аналогии с "непрерывным" случаем под окрестностью 0(4-) точки о <= считать произвольное подмножество куба Ь , содержащее точку aL 9 то любое множество As в будет состоять лишь, например, из внутренних точек. Чтобы избежать подобного рода вырожденных постановок задач, нужно наложить ограничения на выбор множеств OCct-)9 2 пунктах 3-5 главы 3 считается, что 0(<) = = /^ «* t где М _ некоторое фиксированное подмножество куба 6> . Таким образом, 0(at) представляет собой "сдвинутое" на векторе А множество М . Определим окрестность множест-ва A : G(A) („U0())\\.
Рассматриваемые изопериметрические задачи из пунктов 3-5 главы 3 состоят в нахождении такого m -элементного , і - *п. * , подмножества А в , на котором достигается минимум числа Такім образом, указанные задачи отличаются друг от друга заданием множества 14 . Показано, что изопериметрическая задача из главы I входит в изучаемый в главе 3 класс задач. Множество А назовем G -оптимальным.
Основным результатом п.З главы 3 является теорема 3.2, в которой приведен способ построения (я -оптимального множества при У\-&±. в теореме 3.3 построено G -оптимальное множество в случае, когда /1 состоит из линейно-независимых
-ІЗ -
над полем [0,11 векторов куба /5 . В теоремах 3.4 и 3.5 для некоторых множеств М , содержащих линейно-зависимые векторы, показано, что (я -оптимальные множества, полученные в пункте 4, являются таковыми и в рассматриваемом случае.
Автор выражает глубокую благодарность своему научному руководителю доценту А.А. Сапоженко за постоянное внимание, . поддержку и помощь в работе.
Построение всех оптимальных множеств особой мощности
Разобьем куб Ъ по координате яу на два подкуба Ь и Ь о размерности -1 и пусть А& )і и А ) - части множества А в этих подкубах. Скажем, что п- Ё приведено по координате ЗУ , если \А(с )\ 1А Се )\ . Множество, приведенное по всем координатам, назовем приведенным. Назовем, наконец, разбиение приведенного множества А по координате - V минимальным, а координату V минимальной координатой множества
Обозначим через K совокупность всех УП -элементных оптимальных приведенных множеств особой мощности. Отметим, что оптимальное критическое множество Л особой мощности иъ не являющееся приведенным, может быть получено из некоторого множества В K L сдвигом & на вектор }f є Ё . Этот вектор имеет единицы в тех координатах, по которым А не приведено и нули в остальных.
Лемма 1.2. Пусть /лє Кщ и с его минимальная координата. Тогда подмножества A V) и А 6 ) являются оптимальными подмножествами особых мощностей соответственно в подкубах & о и о 4 . Лемма 1.3. Пусть гл -Куп и V его минимальная координата. Теорема 1.2. Пусть А оптимальное множество и \{\[=і і, m = ГГЯ + J" . Тогда: I/ существует точка -п такая, что о ( ) - 2/ если иг особая мощность, то существует точка єА такая, что SK ( ) А S +г Г J. Следствие. Если иг - (с- J , то шар радиуса Ас является единственным /с точностью до выбора центра/ решением дискретной изопериметрической задачи.
Доказательство лемм 1.2, 1.3, и теоремы 1.2 см. в [Vj. Далее на всем протяжении этого параграфа будем предпола гать, что УП есть особая мощность. Назовем точку « А такую, что , характеристической точкой множества А . Совокупность всех характеристических точек множества А обозначим через
Пусть у є о и ip = L- с- " с- ) - произвольный эле-мент группы подстановок f . Обозначим через А )f множество, полученное сдвигом множества А на вектор jf / здесь и далее означает сложение по модулю 2/, а через (7\) множество перестановочно-эквивалентное А , т.е. полученное из А с помощью перестановки f координат куба b . Скажем, j и. МНОЖеСТВО /А - L ния что множество А - В есть множество типа стандартного размеще , если для некоторых jf е )к И є Г . Лемма 1.4. Пусть S Г ) А S +i ґ ), тогда .для оптимальности множества А особой мощности т. необходимо и достаточно, чтобы оно являлось множеством типа стандартного размещения.
Доказательство леммы см. в [А]. Замечание I. Отметим, что в леммах 1.2 и 1.3 требуется, чтобы множество А было приведено по всем координатам куба В Однако, это требование не является жестким. Действительно, если А не приведено по координате хс и выполняется равен отво \\к(с)\-\ (с)\\ \\A"q)\-[hL(j)\[ , -- ,г, ...,( , то, как нетрудно показать, лемма 1.2 остается справедливой для такого множества, а выражения для [ А 6")/ и I А (с) \ в лемме 1.3 необходимо поменять местами. Поэтому далее будем считать, что координата Q является минимальной координатой множества А , если при j = 1 IIAV I-IAV.OIIsflAfyl-IA H.
Рассматриваемый в настоящем параграфе подход к описанию всех оптимальных подмножеств куба В из класса KhX_ состоит в следующем. Введем понятие процесса разбиения множества А . На первом шаге указанного процесса производится раз биение куба & по минимальной координате множества А . Из леммы 1.3 следует, что либо А (с) , либо А Сс) имеет мощ-. ность шара и, значит, с учетом леммы 1.2 и следствия из теоремы 1.2, является шаром. Структура другой части разбиения множества А при этом пока неизвестна. Назовем эту часть неопределенным множеством и обозначим через ± , а соответствующий подкуб Ві куба ЕЬ , в котором оно находится - неопределенным подкубом размерности К-1 . Далее на -том шаге процесса, разобьем куб о по какой-либо минимальной координате 3 неопределенного множества %g-i , находящегося в неопределенном подкубе Ь$.± размерности г-2 + 1 /считаем, что %о А /. Подкубы куба & , образующиеся при таком разбиении назовем основными. Индукцией по нетрудно показать, что среди основных подкубов размерности h -S будет не более одного неопределенного, В остальных же подкубах части множества А являются шарами /назовем их & -шарами/. Процесс разбиения заканчивается на шаге с номером "t , если полученное после его совершения неопределенное множество является шаром, т.е. его структура становится определенной. Подчеркнем, что момент останова процесса разбиения является существенным для дальнейшего.
Актуальность описашш всех оптимальных множеств особой мощности
Вторая, часть утверждения теоремы 1.9 нетрудно доказывается индукцией по параметру Уь аналогично тому, как это было сделано при доказательстве соответствующей части теоремы 1.8,
Оценим число подмножеств из класса TL , Для этого достаточно оценить число различных процессов разбиения, которые могут быть построены по алгоритму А2. Параметры из пунктов I и 2 описания алгоритма определяются однозначно по /п. . Число Й из пункта 3 можно выбрать не более, чем К способами, после чего число т. определяется однозначно. Множество Л/ можно выбрать не более, чем \ь способами в случае 5а и не более, чем и d способами в случае 56. Далее, последовательность координат Яслf...j Яе т можно выбрать заведомо не более, чем К! способами. Центры всех ҐЛ. -шаров кроме Чм определя Г" ются однозначно. Центр шара У.т может быть выбран не более, чем К способами. Учитывая вышеизложенное, нетрудно убедиться, что Так как fyz \т%, U % Ы &ЦгП , то %lCU %A и поскольку число всех оптимальных множеств особой мощности не превосходит \Kynl , то порядок логарифма указанного числа также не превосходит
6. Актуальность описания всех оптимальных множеств особой мощности Рассмотрим следующее линейное упорядочивание L0 вершин куба /Ь . Считаем, что вершина С старше А если:
2. При eUls/(M(, U. лексикографически младше у Нетрудно заметить, что первые \пь вершин куба о , выбранных в соответствии с указанным линейным порядком,образуют множество Lyri . Пусть теперь L есть произвольное полное линейное упорядочивание вершин куба Ь . Скажем, что тг _ элементное множество А- & порождено порядком L , если А состоит из первых /ті вершин куба Ь в указанном порядке
Представляет определенный интерес нахождение всех линейных порядков, порождающих оптимальные т -элементные множест-ва при і ГҐІ . Такие порядки назовем оптимальными. Известно обширное количество примеров экстремальных задач,решения которых порождаются линейными порядками. К тому же задание линейного порядка обеспечивает удобный способ задания подмножеств куба & , порождаемых им. Возможности по представлению оптимальных множеств оптимальными линейными порядками отражены в следующей теореме:
Теорема 1.10« Пусть А оптимальное критическое множество, порождаемое оптимальным линейным порядком L и IAI = УП . Тогда угъ является особой мощностью.
Доказательство Заметим, что существует точка є А , такая, что А\ ? оптимальное множество и ( Р(А)\ 1Р(А VO. По условию имеем:
Таким образом, \Р(т)\ \P(lm-i\\ » следовательно, УП особая мощность. Таким образом, построение всех оптимальных линейных порядков может быть сведено к построению всех оптимальных множеств особой мощности. Приведем критерий, позволяющий определить, является ли уп особой мощностью. Пусть /7isrH+()" . Обозначим через 3 s самую лексикографически младшую точку нормы + из Lk . Теорема I.II. Число УП является особой мощностью если и только если dK-i , / Доказательство
Пусть т. особая мощность. Рассмотрим множество точек С из куба Ь , имеющих норму К , таких, что все сравнимые с ними точки из (К+4) -го слоя куба & представляют собой множество М к-Ц Л Нетрудно заметить, что С- Mfa, Т, Ґ) , где ІЇ некоторое целое. Рассмотрим самую лексикографически младшую точку l = (j dt ..- JV) из Из определения множества С вытекает, что J внутренняя точка множества Ly . Заметим, что из определения критического множества и из того, что С - конечный К -отре-зок, следует, что & должна быть граничной точкой множества Lm\ . Однако, последнее имеет место лишь тогда, когда JL\ - 1 /и следовательно, J\ Доказательство достаточности производится аналогично.
Каноническое множество
В следующем пункте будет приведено описание множества i(\n, к,гп) , используемого при решении задачи 00 в случае ( =3 (ХтЗ)» в пункте 7 этого параграфа приведенная конструкция будет исследована на ассимптотическую оптимальность при. Н- сто и к = о(\[к ). В пунктах 3-5 будут доказаны следующие теоремы: Теорема 2.4. Мбг яг) является решением задачи ІЩ при К = «. Теорема 2.6. Решением задачи (V) в случае К-3 при т. fa) - к + 2. является $ (п, 3, иг), а при Ш ) К + 3 Заметим, что при К=і задача () тривиальна, так как в этом случае в качестве её решения можно выбрать любое \пъ и элементное / 1 s гп і VL / подмножество слоя Б х .
Каноническое множество
Скажем, что ребро куба Б /т.е. подкуб размерности I / имеет с -тое направление / 1 - 6 1ъ если дае вершины , инцидентные ему, различаются в О -той координате. Ниже будет построена нумерация векторов слоя Ок числами от I до (к J . Подмножество слоя Б к , состоящее из первых Гґі занумерованных векторов, назовем каноническим и обозначим через Sfa, к,ггг).
Обозначим через («) лексикографический номер точки аС , т.е. число сс )=5 - 2 . Этот номер численно ра-вен десятичному числу, двоичным представлением которого является координатная запись точки J- . Скажем, что вершина cL є &к старше вершины ft б к , если . Пусть -о - самая старшая точка из о«-і Рассмотрел все ребра вида Ыо, Pj, где Jb е Вк . Направления, которые имеют эти ребра назовем основными. Скажем, что с -тое основное направление старше і -того основного направления, если
Занумеруем теперь векторы & є о к , являющиеся вторыми концами указанных ребер,числами от І до К-к + і в порядке убывания их /векторов/ лексикографических номеров /см. рис.1/. Подкуб куба D , "натянутый" на вершины о и 1 = -( -7 назовем основным подкубом размерности И,-к+ 4. .
Пусть уже занумерованные точки из 5К , входящие в основные подкубы размерности ё и 6 1 . Выбросим из рассмотрения самое старшее из числа тех, что имеют ребра этих под-кубов, основное направление. Выберем, далее, все такие точки
(Ь &к-± » чт0 Для любого из оставшихся основных направлений в кубе )K существует ребро этого направления вида (&, V ) , где ft є Ьц . Из полученного множества точек { М оставим только такие, которые не были выбраны при нумерации точек Bi , входящих в основные подкубы размерности t+i . Пусть у о,дна из оставшихся точек. Рассмотрим подкуб размерности С 1 , содержащий точку у и имеющий ребра только указанных выше основных направлений. Его мы назовем основным подкубом размерности -4 . Занумеруем точки из i , принадлежащие основным подкубам размерности 1 следующими по старшинству числами в порядке убывания их лексикографических номеров.
Нумерация заканчивается по исчерпании запаса основных направлений. При этом будут занумерованы все векторы слоя
В качестве примера на рис.1 показана нумерация век-торов из &з Утолщенные ребра входят в основные подкубы.
Пусть некоторая точка ІЬ была занумерована при построении основных подкубов размерности б . Будем говорить в этом случае, что - имеет степень 6 /обозначение G (aL)s - /. На рисунке I .в кружках приведены степени каждой точки из з . 3. Некоторые определения и вспомогательные утверждения «- , являющиеся решениями задачи (%) , оптимальными. Пусть о/0 є &к. Введем верхнюю и нижнюю окрестности А : Известно /теорема Краскаля-Катона .[30j , [зз]/, что одним из іт -элементных подмножеств слоя Ьк , обладающих минимальной верхней /нижней/ окрестностью, является М ( , «, т) Лемма 2.3. Пусть га Ъ нъ0- (з) " +3 Тогда І \(к, ігі) есть решение задачи . Доказательство
Заметим, что по теореме Краскаля-Катона, мощность мно жества 0 (Ь/(и.,к,гп))еотъ неубывающая функция параметра ип
Кроме того, очевидно, что Нетрудно пока зать, что о \з )\2. /+W Тогда по теореме Краскаля-Катона имеем: J Он(А) 5- (0Н(Ы( .) к, m ) Ъ ( К =J ) \0И(Ы( , 3, гп,0))\=( )+(Ь ) 4(!г) . Таким образом, 0И(А)-- & как только m$m0, т.е. \0(А)[= \0(А) 1 + ( . Воспользуемся еще раз теоремой Краскаля-Катона: Ск = 3) что и завершает доказательство.
Разобьем куб о по координате 3/ на 2 подкуба Ь и Ь ± размерности h-i и пусть А- Ь k и А0=АП6 , Д = А0В і Нетрудно заметить, что относительно нумерации слоев подкуба Ь Q / Ь j / множество А0 /Ал / находится в К -том /в Ос-і)-ом/ слое & / В j /, т.е. А0- 5к о / А±- \л± /. Спроектируем теперь Ai в & 0 , т.е. заменим координату 3 у всех веторов из АІ на ноль. В результате получим нг -элементное множество С , находящееся в (камерном кубе Ъ Q и такое, что 10(с)\+ т. = №(/\)\ t где под 0(c) подразумевается окрестность множества С в кубе , а под 0(A) - окрестность множества А в кубе о Подобное преобразование использовалось в 1 гл.2, где и доказано последнее равенство. Обозначим множество, полученное из
А в результате описанного преобразования через А . Если множество А находилось в слое о к , то множество А находится в двух слоях - К -том и (K-iJ-ом куба & . Кроме того, если А есть оптимальное подмножество куба /5 , то множество А есть решение задачи нахождения т -элементного подмножества oK U Ък_ с минимально возможной окрестностью. Назовем эту задачу - задача , а подмножество, являющееся её решениями ( &) -оптимальными.
Случаи, когда окрестность состоит из линейно
Рассмотрим определение внутренних точек множества А , принятое в топологии. Точку «є Л называют внутренней точкой множества А , если некоторая её окрестность входит в Л . Под окрестностью точки понимают любое, содержащее её открытое гшожество. Так как определение открытого множества тесным образом связано с операцией предельного перехода, которая не имеет особого значения в конечных пространствах, то понятие окрестности точки в последнем случае может иметь множество трактовок.
Если по аналогии с "непрерывным" случаем считать под окрестностью 0( -) точки - Є (Ь произвольное подмножество куба , содержащее точку - , то нетрудно заметить, что любое множество п — о при этом будет оптимальным с точки зрения минимизации числа граничных вершин. Действительно, положив 0(c .)-aL для любой - ё В , ПОЛУЧИМ Г(А) ДЛЯ ЛЮбОГО А-& . Такая лее ситуация будет если положить для любой точки є Ь , 0() - {}() 1) . В этом случае для любого А - & имеем
Чтобы избежать подобного рода вырожденных постановок задач, необходимо наложить ограничения на выбор множеств 0( -) . Пожалуй, наиболее естественно считать, что все множества 0 ( при D имеют в некотором смысле одну и ту же структуру, т.е. все они являются шарами,либо параллелепипедами и т.п. Будем в дальнейшем считать, что 0С ) Afo t где /Ч есть некоторое фиксированное подмножество куба Е . Назовем точку .е А внутренней точкой множества А , если и граничной в противном случае,
Изопериметрические задачи, рассматриваемые в этой главе, заключаются в нахождении такого w- -элементного множества А , на котором реализуется tru I П7\) . Множество А !А(=т, назовем / -оптимальным. Указанные задачи различаются между собой заданием множества 1А . При этом основное внимание будет уделено построению лишь одного из решений каждой из задач. Отметим, что если л=в„ ив;, то осп &?&), т.е. изопериметрическая задача с таким определением граничных вершин рассмотрена в главе І. В пункте 2 настоящей главы будет исследовано естественное обобщение указанной задачи на случай /Ч - Ё 0 U &i U... U & , где С - некоторое фиксированное целое число.
В остальных пунктах главы З.для удобства изложения: изопериметрические задачи будут рассматриваться в несколько иной эквивалентной постановке. Определим окрестность Ы/4) множества
Рассмотрим задачу построения иа -элементного, й. м. L множества А с минимальной окрестностью, т.е. такого, что Назовем множество А G -оптимальным.
Нетрудно заметить, что т.е., имея гг элементное оптимальное множество А , мы можем построить 2- -т-элементное Г -оптимальное множество & \Д. 2. Обобщение изопетжметшческой задачи, "рассматриваемой в главе I
В изопериметрической задаче, рассматриваемой в главе I, считалось, что внутренность множества А определяется сле-.дующим образом: Р(А) [ " - є А Si () А] .
Рассмотрим задачу нахождения w. -элементного / 1 - m - / подмножества гл & , для которого мощность множества внутренних точек - lg(A) имеет наибольшее значение среда всех „к У -элементных подмножеств куба Ь . Такое множество назовем с -оптимальным. В этом пункте будет доказана следующая теорема: Теорема 3.1. Пусть А есть і -оптимальное множество. Тогда А является С -оптимальным при Z. Для доказательства теоремы потребуется несколько вспомогательных утверждений. Будем считать пока, что - . . Демма 3.1.
Доказательство Если Р(Р(А)), то для любого с , «2?- є /3(-/) t ГдЄ «V - орт-вектор -той координатной оси куба о . Далее имеем: «Сс- А для любого 4 с . Следовательно, Если 5W, то S±6Z) A , т.е. еЯ 70; Допустим, что ёА. є ГТР64)). Тогда для некоторого , /ТД) , т.е. -есГСЛ) и, значит, для некоторого jfc ,о f A, т.е. 5гТЛ) А . Противоречие. Следовательно, e ftWO). Лемма доказана.
