Изопериметрические задачи на n-мерном единичном кубе тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение.

Глава I. Построение решений основной дискретной изопериметрической задачи.

§ I. Определение рассматриваемых классов решений.

1. Постановка задачи.

2. Теорема о сводимости.

§ 2. Построение всех оптимальных множеств особой мощности.

1. Описание используемого подхода.

2. Вычисление радиусов "6 -шаров и некоторые вспомогательные утверждения.

3. Множества, перестановочно-эквивалентные стандартному размещению.

4.- Описание всех оптимальных множеств из класса

5. Описание всех оптимальных множеств из класса

6. Актуальность описания всех оптимальных множеств особой мощности.

§ 3. Построение решений, имеющих неособую мощность.

1. Достаточное условие несуществования оптимальных критических множеств неособой мощности.

2. Построение оптимальных критических множеств из неоптимальных.

Глава 2. Изопериметрические задачи на множествах специальной структуры.

§ I. Теорема о четных слоях куба

1. Постановка задачи.

2. Доказательство основного результата.

3. Обобщения основного результата.

§ 2. Изопериметрическая задача для К -того слоя куба Б^

1. Постановка задачи.

2. Каноническое множество

3. Некоторые определения и вспомогательные утверждения.

4. Леммы о конечных отрезках.

5. Доказательство оптимальности канонического множества при и К

6. Мощность окрестности канонического множества.

7. Исследование множества на ассим-птотическую оптимальность при К=о(|к.)и К

8. Сравнение мощностей множеств т) и

М (X К, иг) при К=С-П, ОЛ <С < 0,$

Глава 3, Изопериметрические задачи, возникающие при различных определениях граничных вершин.

1. Обзор постановок задач

2. Обобщение изопериметрической задачи, рассматриваемой в главе I

3. Центральная теорема.

4. Случай, когда окрестность состоит из линейно

5. Дальнейшее обобщение центральной теоремы. 108 Литература.

В диссертации исследуется задача, являющаяся .дискретным аналогом известной классической изопериметрической задачи. На её основе производится построение решений некоторых других экстремальных комбинаторных проблем.

Как известно, классическая изопериметрическая задача заключается в отыскании среди всех простых замкнутых кривых с фиксированным периметром р такой, которая отделяет максимальную площадь S . В двойственной постановке указанная задача состоит в нахождении среди всех фигур площади S такой, которая имеет наименьший периметр р . Эти задачи были известны давно, и полное их решение впервые было найдено в XIX столетии на основе аппарата вариационного исчисления [V] . Оказалось, что окружность и круг являются единственными решениями соответствующих задач.

В настоящее время под изопериметрическими подразумевают широкий класс задач, связанных с исследованием соотношений между мощностью множеств различной природы и мощностью границ этих множеств. В диссертации исследуются дискретные изопери-метрические задачи.

Рассмотрим ^ -мерный единичный куб:

ЬК = : £ = и,}.

Определим расстояние Хемминга между вершинами куба:

Ф= Дк' "А-1.•• ß'fa.-.JSK).

Скажем, что вершина /или точка/ о£бА является граничной для множества ', если З4 А » гДе SM -шар радиуса h в метрике Хемминга с центром в точке . Совокупность всех граничных точек множества А будем обозначать через

ГС А).

Дискретная изопериметрическая задача состоит в том, чтобы по произвольному заданному целому числу пь из сегмента [ 2. 2 найти такое нъ -элементное подмножество А £ /3 , множество граничных точек которого имеет минимально возможную мощность, т.е. такое, что |ГТА*)|= гпНг 1Г(А)1.

Множество А называется оптимальным.

Сформулированная дискретная изопериметрическая задача была рассмотрена в ряде работ / см. [153 , [16^ , £зо] , Интерес к ней был связан как с некоторыми вопросами вариационного принципа алгебры логики, так и с задачами теории кодирования и теории графов.

Изопериметрические задачи находят широкое применение в булевой алгебре / [10] - \12] , [и]/ при исследовании метрических характеристик подмножеств К -мерного единичного куба, а также при решении задач минимизации булевых функций. В ряде случаев необходимо уметь оценивать число подмножеств куба, , имеющих заданную мощность границы [18~[ .

Тесные всязи с рассматриваемыми в работе вопросами: имеют задачи теории кодирования / [13]] , , £34]/. Как известно, основная задача построения кодов Хемминга состоит в нахождении плотных упаковок К -мерных шаров в К -мерном кубе. Если кодовые наборы взвешенные, то требуется найти плотную упаковку шаров разных размерностей. Наличие пересечений в рассматриваемой упаковке соответствует задаче приближенного декодирования при разных допустимых значениях смещений пар кодовых слов. "Дмеющиеся результаты указывают на минимальную область пространства &К , где могут быть размещены кодовые слова с допустимыми областями их изменений.

Рассмотрим теперь граф р -элементным множеством вершин V и ^—элементным множеством ребер В. Пусть У* - нумерация вершин графа & числами I, 2,.,,, р

Если её Е и , то число назовем длиной ребра е . Определим длину нумерации ^ как число

21 А е и ширину нумерации как тъх Де . во многих приклад-ее£ еее ных задачах, в том числе в задачах автоматизации проектирования ЭВМ / [17] , [20]/, ставится вопрос о нахождении нумерации у графа С при минимизации длины и ширины нумерации. Это соответствует, например, минимизации общей или максимальной длины соединений при линейном размещении элементов электрической схемы.

В работе [28] доказано сведение проблемы нахождения нумерации с минимальной шириной для случая 0 - ЕЬ^ к решению дискретной изопериметрической задачи, и найдены условия, при которых возможно такое сведение при произвольном графе Q

По-видимому, впервые задача построения оптимальных по длине и ширине нумераций вершин графов была явно сфоралулирована в работе [32] , где указывалось на возможность использования таких нумераций при кодировании информации с целью минимизации средней или наибольшей ошибки при передаче сообщений.

При численном решении многих инженерных, физических и математических задач в настоящее время широко используется метод конечных элементов / [19]/. При применил этого метода необходимо произвести нумерацию узлов дискретной решетки, аппроксимирующей заданную непрерывную область. Таким образом, возникает задача построения нумераций вершин некоторых классов графов. При этом также следует стремиться получить нумерации с минимальной шириной.

Имеется ряд работ, посвященных указанной проблеме / [24] , [27] , [29]/. При построении соответствующих нумераций помимо специальных комбинаторных построений используется изопериметри-ческий подход.

Необходимость изучения свойств решений дискретной изоперической задачи возникает при синтезе многопроцессорных вычислительных систем из ненадежных компонентов ¡^21] . Использование соотношений между мощностью оптимального множества и числом , его граничных точек позволяет оценить надежность указанных систем.

Множество всех решений дискретной изопериметрической задачи используется в теории распознавания образов при описании задач, наиболее соответствующих гипотезам распознавания типа компактности [з] . При исследовании изопериметрической задачи выяснилось, что дискретная природа И, -мерного единичного куба накладывает существенный отпечаток на свойства ее решений, так, что в отличие от "непрерывной" задачи, где решение единственно, в дискретном случае множество всех решений содержит такие элементы, которые не соответствуют обычным представлениям о компактности.

В теоретическом плане изопериметрические задачи представляют интерес в связи с экстремальными задачами для семейств подмножеств конечного множества. Некоторые результаты их исследования носят классический характер /см.»например, теорему Краскаля-Катона [30] , [зз] / и используются в самых различных областях комбинаторики / [2бД , [26] , [31] , [[35^ , [зб]/ и теории чисел [22] .

История решения дискретной изопериметрической задачи такова. В 1966 году Харпер [28^ и независимо от него Катона[зо]в 1975 году построили одно из оптимальных множеств, называемое стандартным размещением. В 1969 году Р.Г. Нигматуллин [1б] доказал, что в случае, когда мощность множества т является мощностью шара, т.е. т= ¿-[^ ) при некотором к , К , с-О то шар радиуса К является единственным с точностью до выбора центра решением указанной задачи.

Далее, в 1980 году Л.А.Асланян, В.М.Караханян, Б„Е.Торосян [4] показали, что любое оптимальное множество А мощности иг - (Г) + , 0 - содержит некоторый шар радиуса К , т.е. А . Кроме того, в случае если является особой мощностью /подробнее см.ниже/, существует точка с^е А , такая, что $£(<£) — А — С^З . Эти же авторы впервые отметили, что в некоторых случаях во множестве А существуют такие точки, произвольное размещение которых в пространстве & не влияет на величину границы А .

Таким образом, для завершения описания всех оптимальных подмножеств куба необходимо уточнить строение оптимальных множеств особой мощности и исследовать оптимальные множества не особой мощности. Изучению этих вопросов посвящена первая глава диссертации.

В первом параграфе этой главы приводится математическая постановка рассматриваемой задачи и доказываются результаты по сведению описания одних классов решений к другим. Обозначим через внутренность множества

Назовем критическим /по компактности/ множеством, если для любой А, / Р < I Р СА) I . Основным результатом этого параграфа является теорема 1.1, из которой вытекает способ построения всех оптимальных некритических множеств при условии, что построены все оптимальные критические множества. В соответствии с этим далее рассматриваются лишь оптимальные критические множества.

Назовем число т особой мощностью, если все оптимальные пъ -элементные подмножества куба ёЛ являются критическими.

К - д

Например, числа вида 21 (¿), К = К суть особый мощности. с-О

В § 2 главы I приведено описание всех оптимальны:!?: множеств особой мощности. В пункте I этого параграфа изложен используемый подход и сформулированы основные утверждения. Главными результатами п.4 и 5 §2 являются теоремы 1.8 и 1.9, из которых вытекает способ построения всех оптимальных множеств особой мощности. В теореме 1.11 и следствии из нее доказано,

Б к о/г-1 ,и. равной . Таким образом, ровно для половины целых чисел «г из сегмента [4., в §2 гл.1 построены все оптимальные ^ -элементные множества.

Третий параграф главы I посвящен построению оптимальных критических множеств неособой мощности. Обозначим через р(т,п) число внутренних точек у оптимального /п -элементного подмножества А - ЁЛ. Основным результатом п.1 этого параграфа является теорема 1.13, в которой доказано, что если есть особая мощность, то не существует оптимальных т -элементных множеств, которые нельзя было бы построить, исхода из результатов §§ I и 2 гл.1. В теореме 1.14 доказано, что число неособых мощностей т. таких, что р(т?п) особая мощность, ассимптотически равно г£ . Таким образом, учитывая результаты §2 гл.1, показано, что для некоторых чисел т , доля которых составляет ас-3 симптотически от всех возможных значений, построены все оптимальные иг -элементные подмножества куба ёЛ .

3 пункте 2 §3 изучаются оптимальные подмножества оставшихся мощностей. Построена процедура, позволяющая из любого критического подмножества куба Ь^ получить оптимальное критическое подмножество куба большей размерности такое, что структура полученного множества в некотором смысле совпадает со структурой исходного. В теоремах 1.15 и 1.16 доказано,что при этом произвольное критическое подмножество куба ЁЛ становится оптимальным при "вложении" его в пространство большей размерности.

Указанные результаты отражают трудности,возникающие при описании оптимальных множеств оставшихся мощностей, и в то же время являются способом построения таких множеств.

Во второй главе диссертации изучаются изопериметрические задачи на множествах специальной структуры.

Пусть = Г ЬК- //<£|| = 21 ^С = к( . Это мное'= 1 ^ жество называется к -тым слоем куба В . Обозначим через совокупность четных слоев куба , т.е. бЧо)= [ в* •' к = 0(мо*г)}.

Определим окрестность множества А : 0(А) = {°*-£&

В §1 главы 2 изучается изопериметрическая задача для подмножеств п-Ь (о)9 заключающаяся в построении такого м. -элементного множества А - Ь(о) / ± < т $ £ Д мощность окрестности которого имеет наименьшее возможное значение /¡32]/. Решение этой задачи было использовано в работе [18]. Основным результатом параграфа I является теорема 2.1, утверждающая о том, что рассматриваемая задача эквивалентна в дискретной изо-периметрической задаче, изучаемой в главе I. Зная все решения одной из указанных задач,можно с помощью построенных в этой теореме преобразований получить все решения другой.

Во втором параграфе главы 2 исследуется изопериметричесп кая задача для подмножеств К -того слоя куба о , в которой требуется построить т -элементное / 1 - т - (£) / подмножество слоя , обладающее наименьшей возможной мощностью множества ОСА) . Эта задача была поставлена в работе [30] и возникает принекоторых исследованиях, связанных с минимизацией булевых функций. Результаты других авторов по решению указанной задачи в печати отражены не были.

В диссертации рассматриваемая задача решается для случаев К = Л и К = 3 . Основными утверждениями пунктов 2-5 §2 гл. 2 являются теоремы 2.4 и.2.6, в которых доказывается, что множества ,гп) и о С''Ь К,иг) являются решениями поставленной задачи в случаях к=£ и К-3 соответственно. Определение множеств и 5>(и-,к,т) см. в главе 2. В пункте 7 §2 прово,дится исследование, направленное на приближенное решение задачи в случае к,-*©о . в теореме 2.8 и следствии из нее доказано, что МО*, к, пг) является ассимптотически оптимальным множеством при К = в теореме 2.10 показано, что уже не является ассимптотически оптимальным при К-с-(г , 0. ^ < С < о. 5 , и что множество £к,т) при этом в некоторых случаях имеет меньшую по порядку окрестность. В ходе исследования установлено, что отдельные утверждения о свойствах решений рассматриваемой задачи справедливы и при произвольных К и т /см.»например, теорему 2.5/.

В последней, третьей главе диссертации изучается семейство изопериметрических задач, возникающих при различных толкованиях граничных вершин.

В пункте 2 главы 3 рассматривается обобщение изопериметри-ческой задачи из главы I. Считается, что точка <%€А является £ -граничной / 1 ~ € - ./, если

-(£)Ф А

Назовем множество А £ -оптимальным, если оно имеет наименьшее возможное число б -граничных вершин среди всех подмножеств той же мощности. Основным утверждением п.2 гл.З является Теотэема 3.1. Если А 1-оптимальное множество, то А также С -оптимальное множество при ^ - <2 Из этой теоремы вытекает теорема 6.1 из статьи Л.А.Асла-няна [4] , в которой утверждается, что если А -оптимальное множество, то существует некоторая точка такая, что

А . Теорема 3.1 позволяет также определить число указанных точек.

Рассмотрим обобщение понятий граничных и внутренних вершин. В топологии точку сСсА называют внутренней точкой множества А , если некоторая окрестность этой точки входит в А . Под окрестностью точки понимают любое открытое множество, содержащее & . Так как определение открытого множества тесным образом связано с операцией предельного перехода, которая не имеет особого значения в конечных пространствах, то понятие окрестности точки в последнем случае может иметь множество трактовок.

В пункте II главы 3 показано, что если по аналогии с "непрерывным" случаем под окрестностью ОС**-) точки оС 6 ¿Засчитать произвольное подмножество куба Ь^ , содержащее точку £ , то любое множество А £ выбудет состоять лишь, например, из внутренних точек. Чтобы избежать подобного рода вырожденных постановок задач, нужно наложить ограничения на выбор множеств В пунктах 3-5 главы 3 считается, что 0(<£)

- М, © «А , где М - некоторое фиксированное подмножество куба . Таким образом, 0(сС) представляет собой "сдвинутое" на вектор А множество М . Определим окрестность множества А : А. Д

Рассматриваемые изопериметрические задачи из пунктов 3-5 главы

3 состоят в нахождении такого т -элементного , i - ^ - £ , ^ н. подмножества , на котором достигается минимум числа 16 «и

Таким образом, указанные задачи отличаются друг от друга заданием множества 14 . Показано, что изопериметрическая задача из главы I входит в изучаемый в главе 3 класс задач. Множество А назовем й -оптимальным.

Основным результатом п.З главы 3 является теорема 3.2, в которой приведен способ построения С -оптимального множества при М - в теореме 3.3 построено С -оптимальное множество в случае, когда М состоит из линейно-независимых над полем [о, векторов куба . В теоремах 3.4 и 3.5 для некоторых множеств М , содержащих линейно-зависимые векторы, показано, что G -оптимальные множества, полученные в пункте 4, являются таковыми и в рассматриваемом случае.

Автор выражает глубокую благодарность своему научному руководителю доценту A.A. Сапоженко за постоянное внимание, . поддержку и помощь в работе.

1. Асланян Л.А», Караханян В.М., Торосян Б.Е. Решение дискретной изопериметрической задачи. - ДАН Арм.ССР, 1977, т5, с.257-262.

2. Асланян Л.А., Караханян В.М. Общие описание решений дискретной изопериметрической задачи. ДАН Арм.СОР, 1977, т.¿XV В 4, с.211-215.

3. Асланян Л.А. Алгоритмы распознавания с логическими отделителями. Сборник работ по математической кибернетике, вып. I, ВЦ АН СССР, 1976, с.116-131.

4. Асланян Л.А. Изопериметрическая задача и смежные экстремальные задачи для .дискретных пространств. Проблемы кибернетики, вып. 36, - М.: Наука, 1979, с.85-127.

5. Безруков С.Л. Изучение подмножеств, минимизирующих границу в Хемминговом пространстве. Прикладная математика и математическое обеспечение ЭВМ, изд. МГУ, 1981, с.72-73.

6. Безруков С.Л. Изопериметрическая задача. Прикладная математика и математическое обеспечение ЭВМ, изд. МГУ, 1982, с.40-44

7. Безруков С.Л. Об одной изопериметрической задаче. Дискретный анализ, вып. 40, Новосибирск, 1984, с.32-46.

8. Бляшке В. Круг и шар. М.: Наука, 1967.

9. Леонтьев B.K. Верхняя оценка -глубины (0,1) -матриц. Матем. заметки, 1974, т. 15, J£ 3, с. 421-429.

10. Маргулис A.A. Вероятностные свойства графов с большой связностью. Проблемы передачи информации, 1974,т.10, ЬЬ 2, с. I0I-I08.

11. Нечипорук Э.И. О топологических принципах самокорректирования. Проблемы кибернетики, вып. 21. - М.: Наука, 1969, с. 5-102.

12. Нигматуллин Р.Г. Вариационный принцип в алгебре логики. -Дискретный анализ, вып. 10, Новосибирск, 1967, с. 69-89.

13. Нигматуллин Р.Г. Некоторые метрические соотношения в единичном кубе. Дискретных анализ, вып. 9, Новосибирск, 1967, с. 47-58.

14. Петросян A.B., Маркосян O.E., Щукурян Ю.Г. Математические вопросы автоматизации проектирования ЭВМ. Ереван, 1977.

15. Сапоженко A.A., Коршунов А.Д. О числе двоичных кодов с расстоянием 2. Проблемы кибернетики, вып. 40. М.: Наука, 1983, с. III-I30.

16. Сегерлинд Л. Применение метода конечных элементов. М., Мир, 1979.

17. Селютин В.А. Автоматизированное проектирование топологии БИС. М.: Радио и связь, 1983.

18. A&tsweole к., KoScAcck КМ. Note о* ак е-%1рн>4&т oCNSinf foir ипне&'ос&к neiuohicS ¿и рссыМеС cofnfouii^. Dcschete Malte/nahes , 1383, \f. kl, р.137-15<>.

19. Aitdehbon. 1. Oh, a oldrcsor-S of a Mmfeh.- X Lotvoloh, HM. Soc.t 1968, v. 43, p. kiO-^lt.23. bewstecn. A.I., StcLcfeciz K., Hopwfi У. E. EtuioM'^ of ocrux€ocf for- -gedeihy. sf^methic

20. EE c^fohmaicon b&eohq, 13CS, V.li~l2, NoM} p. kZ5-k30.2%.Cß-VCctoL£oVCL У. OpttmciC £ac4cic'(b^ of OC phoduct öf bbtooactás.- Víchete titxiA., ±<37St-v. 4J, Ño.S-k,p.2k3-¿53

21. C6eme>fttz G.P. Ine<^.uo(ùtceB coivcehhc num&hS of svfseU of a {cue'te set- ÏComê. ТАео^т^МЧ^.т-Ж.

22. Da ^ КС ft Ü.E.jGooíftey l,Hc€tob АЛЬ/. E*¿síetvce Ь&соhchvs! fSjochhe-h famcùeS 1. Comfcn.Tfieohy, Î37Ï AÎJ, p. ¿k5'251.

23. Fctècjeh-cxfoC С.И. Opte mat скуеяску, of lAt vchteces ofcfhccpJs. MatA. Comftuí.jíW, vM, A/0.127, p. 225-831.

24. Hothpeh LM. Oplcmaë nvmßehcivys and c'sopehc'methc'c pt-oêCems oh, 7. Com S. Theory г 13 SS, (/. 1, Ыо.З, /ü. 325-333.

25. Hoff matt АЛ., Mochte*, M. 1, Rose ЪЛ. Co mptexctg. ¿ookíÁs foh tt^uEoch ft не le ote f-fct-ексе and foncée ttemevd %hcds.-S>lA¡1 1 Nvmeh. кшв^тЗ,^ d0} p.364-369.

26. Kotow G.O.H. Túe Hammen,^ -sp&ehe Acts mínimum &>vhc(<xhy. Mude a Sccent ИМ,

27. Ka to na G.G. H. A ifizohcm, of fottete $ets.-T4eoh(¿ ofbvehxpest ,1968, p.í8?-¿0?.

28. Kol ut 2 1л/. И. Optômcsed doctor etvcodcyug. fot- dcyctaC coniputehSXRE Сонм. Recoh-ds ,195k, pt.k> pA?~56.33. кьиъкав F.ß. Túe ким#еь of sCrr\,p?c$ec in a oomptex-Hatßvemaüca^ Opicmc¿atc'on Тёс&псуце$> 1963J p.¿51

29. S CepcccK Ъ. A c£ass of scfrnatfù'nq dípAafeís-beíi i(.35, Üo.í, p.203'¿3k.

30. VJclh^ P. l)¿schete csopehcmethcc johotftfenbS.SIAh1.App€. Kat&.js^v.ôé^o.k, p.MO'MO.

31. I^L.^anoj. P. Exíhemocé con-fc^cft-atcoKS on, ос de sc hete tobus and а уe. he ha вс ê a, te on of ifaqeneha&'êed МоосаиЛец t&eohem,- SX4M !7. App&KM., ¿977, v. 33, No.i, p, 5S'S3.