4
13
13
13
14
16
16
21
29
32
38
43
46
46
49
56
56
56
56
- 2 -
ОГЛАВЛЕЕШЕ
Построение решений основной дискретной
изопериметрической задачи.............................
Определение рассматриваемых классов решений...........
1. Постановка задачи..................................
2. Теорема о сводимости...............................
Построение всех оптимальных множеств особой мощности..............................................
1. Описание используемого подхода.....................
2. Вычисление радиусов Ь -шаров и некоторые вспомогательные утверждения...........................
3. Множества, перестановочно-эквивалентные стандартному размещению...............................
4. Описание всех оптимальных множеств из
класса ....................................
5. Описание всех оптимальных множеств из класса
Пп ..............................................
6* Актуальность описания всех оптимальных множеств
особой мощности....................................
Построение решений, имеющих неособую мощность.....
1. Достаточное условие несуществования оптимальных критических множеств неособой мощности................
2. Построение оптимальных критических множеств из неоптимальных.........................................
Изопериметрические задачи на множествах специальной структуры.........................................
6 и.
..................
1. Постановка задачи..................................
2. Доказательство основного результата................
- 3 -
3. Обобщения основного результата.................... 58
§ 2. Изопериметрическая задача .для К -того слоя
куба В^ .............................................. 60
1. Постановка задачи ................................ 60
2. Каноническое множество............................ 61
3. Некоторые определения и вспомогательные утверждения........................................... 64
4. Леммы о конечных отрезках........................ 67
5. Доказательство оптимальности канонического множества при К-2. и К-3 ............................. 70
6. ?Лощность окрестности канонического множества. 79
7. Исследование множества Яб'цк, пг) на ассим-птоткческую оптимальность при к=о(\|и.)и к-*«*>.. 81
8. Сравнение мощностей множеств 56^, к, тО и
к, пг) при К=С-П , 0Л < С < 0.$ 91
Глава 3. Кзопериметрические задачи, возникающие при
различных определениях граничных вершин............... 96
1. Обзор постановок задач ............................ 96
2. Обобщение из опериметрической задачи, рассматриваемой в главе I ..................................... 97
3. Центральная теорема.............................. 104
4. Случай, когда окрестность состоит из линейно-независимых векторов куба В........................................................ 107
5. Дальнейшее обобщение центральной теоремы.*... 108
Литература..................................................... 112
- 4 -
Введение
В диссертации исследуется задача, являющаяся дискретны?.! аналогом известной классической изопериметрической задачи. На её основе производится построение решений некоторых других экстремальных комбинаторных проблем.
Как известно, классическая изопериметрическая задача заключается в отыскании среда всех простых замкнутых кривых с фиксированным периметром р такой, которая отделяет максимальную площадь 5 . В двойственной постановке указанная задача состоит в нахождении среди всех фигур площади 5 такой, которая имеет наименьший периметр р . Эти задачи были известны давно, и полное их решение впервые было найдено в XIX столетии на основе аппарата вариационного исчисления Г^З . Оказалось, что окружность и круг являются единственными решениями соответствующих задач.
В настоящее время под изопериметрическими подразумевают широкий класс задач, связанных с исследованием соотношений ?лежду мощностью множеств различной природы и мощностью границ этих множеств. В диссертации исследуются дискретные изопери-метрические задачи.
Рассмотрим ^ —мерный единичный куб:
ЬК -- [(*х, хк) : хс. £ 10,11,1 = 1,г,..*,].
Определим расстояние Хемминга между вершинами куба:
?<*• & 'йи‘ 'А ••^ - •• ^)' Г О5*.
Скажем, что вершина /или точка/ о^А является граничной для множества А<=БН , если , где
шар радиуса Ь в метрике Хемминга с центром в точке £ £ .
Совокупность всех граничных точек множества А будем обозначать через 1ТА).
Дискретная изопериметрическая задача состоит в том, чтобы
- 5 -
по произвольному заданно?^ целому числу т, из сегмента [ 4, 2.^1] найти такое т -элементное подмножество А £= & , множество граничных точек которого имеет минимально возможную мощность, т.е. такое, что |ГТА*)|- 1Г(А)1.
Множество А называется оптимальным.
Сформулированная дискретная изопериметрическая задача была рассмотрена в ряде работ / см. (^15^ , £1б] , £зо] , £28]/. Интерес к ней был связан как с некоторыми вопросами вариационного принципа алгебры логики, так и с задачами теории кодирования и теории графов.
Изопериметрические задачи находят широкое применение в булевой алгебре / £ю] - £12] , £14]/ при исследовании метрических характеристик подмножеств К -мерного единичного куба, а также при решении задач минимизации булевых функций. В раде случаев необходимо уметь оценивать число подмножеств куба, , имеющих заданную мощность границы £18] .
Тесные всязи с рассматриваемыми в работе вопросами имеют задачи теории кодирования / £13] , £23] , £34]/. Как известно, основная задача построения кодов Хемминга состоит в нахождении плотных упаковок К -мерных шаров в К -мерном кубе. Если ко-довые наборы взвешенные, то требуется найти плотную упаковку шаров разных размерностей. Наличие пересечений в рассматриваемой упаковке соответствует задаче приближенного декодирования при разных допустимых значениях смещений пар кодовых слов. }1мегощиеся результаты указывают на минимальную область пространства 6к 9 где могут быть размещены кодовые слова с допустимыми областями их изменений.
Рассмотрим теперь граф С = ( V, /г ) с (о -элементным множеством вершин V и ^—элементным множеством ребер £ . Пусть V* - нумерация вершин графа 6 числами I, 2,..., р
-6 -
Еслив^Е и , то число назовем
дайной ребра в . Определим длину нумерации Г~' как число
21. Ае и ширину нумерации как тъх Де . Во многих приклад-сеЕ.
ных задачах, в том числе в задачах автоматизации проектирования ЭВМ / [Г7] , [203/, ставится вопрос о нахождении нумерации ^ графа б при минимизации дайны и ширины нумерации. Это соответствует, например, минимизации общей или максимальной длины соединений при линейном размещении элементов электрической схемы.
В работе [28] доказано сведение проблемы нахождения нумерации с минимальной шириной для случая С = £> к решению дискретной изопериметрической задачи, и найдены условия, при которых возможно такое сведение при произвольном графе С
По-видимому, впервые задача построения оптимальных по длине и ширине нумераций вершин графов была явно сформулирована в работе £32] , где указывалось на возможность использования таких нумераций при кодировании информации с целью минимизации средней или наибольшей ошибки при передаче сообщений.
При численном решении многих инженерных, физических и математических задач в настоящее время широко используется метод конечных элементов / [193/. При применил этого метода необходимо произвести нумерацию узлов дискретной решетки, аппроксимирующей заданную непрерывную область. Таким образом, возникает задача построения нумераций вершин некоторых классов графов. При этом также следует стремиться получить нумерации с минимальной шириной.
Имеется ряд работ, посвященных указанной проблеме / [243 » ^27] , [.293/. При построении соответствующих нумераций помимо специальных комбинаторных построений используется изопериметри-ческий подход.
Необходимость изучения свойств решений дискретной изопери-
ческой задачи возникает при синтезе многопроцессорных вычис-
соотношений между мощностью оптимального множества и числом . его граничных точек позволяет оценить надежность указанных систем.
Множество всех решений дискретной изопериметрической задачи используется в теории распознавания образов при описании задач, наиболее соответствующих гипотезам распознавания типа компактности [з} • При исследовании изопериметрической задачи выяснилось, что дискретная природа И, -мерного единичного куба накладывает существенный отпечаток на свойства ее решений, так, что в отличие от "непрерывной” задачи, где решение единственно, в дискретном случае множество всех решений содержит такие элементы, которые не соответствуют обычным представлениям о компактности.
В теоретическом плане изопериметрические задачи представляют интерес в связи с экстремальными задачами для семейств подмножеств конечного множества. Некоторые результаты их исследования носят классический характер /см.,например, теорему Краскаля-Катона [зо] , [зз} / и используются в самых различных областях комбинаторики / [25} , [2б] , [3l] , [35J , [зб]/ и теории чисел [22} .
История решения дискретной изопериметрической задачи такова. В 1966 году Харпер [28} и независимо от него Катона [зф в 1975 году построили одно из оптимальных множеств, называемое стандартным размещением. В 1969 году Р.Г. Нигматуллин [1б] доказал, что в случае щость множества ю является
то шар радиуса К является единственным с точностью до выбора центра решением указанной задачи.
лительннх систем из ненадежных компонентов [21} . Использование
мощностью шара, т.е.
при некотором К , К ^ hi
-8 -
Далее, в 1980 году Л.А.Лсланян, В.М.Караханян, Б.Е.Торосян показали, что любое оптимальное множество А мощности иг - 2 + <Г , О * сГ < (&±) содержит некоторый шар 5« (£)
радиуса К , т.е. (<£)£ А . Кроме того, в случае если т. является особой мощностью /подробнее см.ниже/, существует точка £е А , такая, что $£(<£) — А — ^^ • Эти же авто-
ры впервые отметили, что в некоторых случаях во множестве А существуют такие точки, произвольное размещение которых в пространстве В не влияет на величину границы А .
Таким образом, для завершения описания всех оптимальных
Вк»
необходимо уточнить строение оптимальных множеств особой мощности и исследовать оптимальные множества не особой мощности. Изучению этих вопросов посвящена первая глава диссертации.
В первом параграфе этой главы приводится математическая постановка рассматриваемой задачи и доказываются результаты по сведению описания одних классов решений к другим. Обозначим через Р(А) внутренность множества А , т.е.Р(А)~А\ ГС/П ,
А И,
Назовем А - В критическим /по компактности/ множеством, если для любой ^е А, I < I Р(А)1 . Основным резуль-
татом этого параграфа является теорема 1.1, из которой вытекает способ построения всех оптимальных некритических множеств при условии, что построены все оптимальные критические множества.
В соответствии с этим далее рассматриваются лишь оптимальные критические множества.
Назовем число т особой мощностью, если все оптимальные
ез ^
т -элементные подмножества куба о являются критическими. Например, числа вида 21 (£7, э И, суть особый мощности.
с -О
В § 2 главы I приведено описание всех оптимальных множеств особой мощности. В пункте I этого параграфа изложен
- 9 -
используемый подход и сформулированы основные утверждения. Главными результатами п.4 и 5 §2 являются теоремы 1.8 и 1.9, из которых вытекает способ построения всех оптимальных множеств
особой мощности. В теореме 1.11 и следствии из нее доказано,
5и. о/г-1
равно £ . Таким обра-
зом, ровно для половины целых чисел иг из сегмента в §2 гл.1 построены все оптимальные иг -элементные множества.
Третий параграф главы I посвящен построению оптимальных критических множеств неособой мощности. Обозначим через рСт.п) число внутренних точек у оптимального /п -элементного подмножества А- & • Основным результатом п.1 этого параграфа является теорема 1.13, в которой доказано, что если р(т,к) есть особая мощность, то не существует оптимальных т -элементных множеств, которые нельзя было бы построить, исхода из результатов §§ I и 2 гл.1. В теореме 1.14 доказано, что число неособых мощностей Ш таких, что р(т?к) особая мощность, ассиштотически равно <2 . Таким образом, учитывая результаты §2 гл.1, пока-
зано, что для некоторых чисел тп , доля которых составляет ас-симптотически от всех возможных значений, построены все оптимальные т. -элементные подмножества куба Е^1 .
3 пункте 2 §3 изучаются оптимальные подмножества оставшихся мощностей. Построена процедура, позволяющая из любого критического подмножества куба В получить оптимальное критическое подмножество куба большей размерности такое, что структура полученного множества в некотором смысле совпадает со структурой исходного. В теоремах 1.15 и 1.16 доказано,что при этом произвольное критическое подглножество куба £) становится оптимальным при "вложении" его в пространство большей размерности.
Указанные результаты отражают трудности,возникающие при
- Київ+380960830922