+
Действующая цена700 499 руб.
Товаров:
На сумму:

Электронная библиотека диссертаций

Доставка любой диссертации в формате PDF и WORD за 499 руб. на e-mail - 20 мин. 800 000 наименований диссертаций и авторефератов. Все авторефераты диссертаций - БЕСПЛАТНО

Расширенный поиск

Исследование оптимальных конфигураций в задачах о хроматическом числе пространства и проблеме Борсука

Исследование оптимальных конфигураций в задачах о хроматическом числе пространства и проблеме Борсука
  • Автор:

    Иванов, Леонид Львович

  • Шифр специальности:

    05.13.17, 01.01.09

  • Научная степень:

    Кандидатская

  • Год защиты:

    2011

  • Место защиты:

    Москва

  • Количество страниц:

    62 с. : ил.

  • Стоимость:

    700 р.

    250 руб.

до окончания действия скидки
00
00
00
00
+
Наш сайт выгодно отличается тем что при покупке, кроме PDF версии Вы в подарок получаете работу преобразованную в WORD - документ и это предоставляет качественно другие возможности при работе с документом
Страницы оглавления работы
"1 История и формулировки результатов 1.1 История задачи о хроматическом числе.


Оглавление

1 История и формулировки результатов

1.1 История задачи о хроматическом числе.

1.2 Формулировки результатов в задаче о хроматическом числе

1.3 История проблемы Борсука.

1.4 Формулировки результатов в проблеме Борсука . .

2 Доказательства результатов для хроматических чисел

2.1 Доказательство теоремы 1 . .

2.2 Доказательство теоремы 2.

2.3 Доказательства теорем 3 и 4

2.3.1 Обтций метод получения верхних оценок . .


2.3.2 Вспомогательные геометрические леммы . .
2.3.3 Доказательство теоремы 3
2.3.4 Доказательство теоремы 4
2.4 Комментарии
2.4.1 Примеры кубических покраскок
2.4.2 Почти правильная покраска плоскости в
цветов
2.4.3 Многоугольное хроматическое число разреженности .
3 Доказательства результатов в проблеме Борсука
3.1 Доказательство теоемы 5.
3.1.1 Общий план доказательства.
3.1.2 Конструкция множества
3.1.3 Отображение хнх
3.1.4 Лемма о мощности подмножества 2 с запретами
3.1.5 Завершение доказательства теоремы.
3.2 Дополнительные замечания
Введение
Актуальность


Однако довольно быстро стало понятно, что, с одной стороны, задача о раскраске пространства — это очень глубокая проблема, затрагивающая самую суть дискретной геометрии, а с другой стороны, она вовсе не замкнута сравнительно узкими рамками одной лишь комбинаторно-геометрической дисциплины, но напрямую связана с различными актуальными проблемами теории графов и теории кодирования. Во многом такому развитию данной проблематики поспособствовали многочисленные работы П. Эрдеша и популяризаторская деятельность М. Гарднера (см. С классической теорией графов задача о раскраске пространства связана следующим образом. V является набором (возможно, бесконечным) точек в а множество его ребер Е состоит из пар вершин, расстояние между которыми принадлежит множеству Л. Очевидно, что если взять максимальное из обычных хроматических чисел дистанционных графов, то получится ровно х(Еп; Л). Поскольку задача о раскраске графа является одной из центральных в теории графов и ее приложениях в теоретической информатике, а сами дистанционные графы служат отличными моделями для различных объектов, возникающих на практике, то задача о раскраске дистанционного графа имеет особую значимость и актуальность. С теорией кодирования задача о величине хО^;^) соприкасается сразу в двух “точках”. Во-первых, еще в году классики теории упаковок пространств Д. Ларман и К. А. Роджерс показали, что верхние оценки хроматического числа самым тесным образом связаны с вопросами построения плотнейших решетчатых упаковок шаров и наиболее в некотором смысле экономных разбиений Вороного, отвечающих решеткам (см. Во-вторых, нижние оценки хроматических чисел — это, по сути, верхние оценки мощности равновесного кода с одним или многими запрещенными расстояниями Хэмминга. Задача получения подобных оценок — важнейшая в теории кодирования, и ей занимались многочисленные ведущие специалисты в области (см. Более того, здесь есть выход и на теорию однородных гиперграфов с запрещенными пересечениями ребер, которой посвящено огромное количество работ в мире (см. Таким образом, сразу несколько важнейших проблем теоретической информатики тесно переплетаются с задачей раскраски пространства. Если задача об одном запрещенном расстоянии появилась исторически первой, то, едва стала ясна значимость такой проблематики, как возникли и различные важные обобщения исходного хроматического числа. Rn. В случае нескольких запретов следует различать ситуации, когда этих запретов конечное число и когда их бесконечное количество. Конечные множества запретов исследовал Эрдеш с учениками (см. Сейчас наилучшие результаты в этой области принадлежат А. М. Рай городскому, В. К). Протасову, И. М. Мит-ричевой и Е. С. Горской (см. И]). Задачи о бесконечных множествах запретов тесно примыкают к вопросам теории диофантовых приближений и потому также крайне актуальны (см. Среди других метрических пространств, которыми активно занимались и продолжают заниматься крупнейшие специалисты, стоит отметить пространство R7* с произвольной нормой (см. Qn с метрикой lq (см. S"“1 радиуса г с евклидовой метрикой (см. Также в диссертации рассматривается еще одна классическая задача комбинаторной геометрии — проблема Борсука, состоящая в отыскании минимального числа f(n) частей меньшего диаметра, на которые разбивается произвольное множество диаметра 1 в Мп. Эта. К. Борсуком в году (см. С точки зрения теории графов, важны так называемые графы диалютров G = (V, Е), у которых V С а Е — это множество пар вершин, отстоящих друг от друга на расстояние, равное диаметру V. Хроматические числа этих графов, по сути, и равны минимальным количествам частей меньшего диаметра, на которые разбиваются их множества вершин. Задачам о графах диаметров посвящена огромная литература (см. На стыке топологии и теории графов находится топологический метод в комбинаторике, основанный на применении теоремы Борсука-Улама в задачах раскраски графов (см. Наконец, для теории кодирования исключительно важны спецификации проблемы Борсука для случаев Хэммииговых пространств.

Рекомендуемые диссертации данного раздела

Название работыАвторДата защиты
Некоторые методы ресурсного анализа сетей Петри Башкин, Владимир Анатольевич 2014
Построение и исследование полных решающих деревьев для задач классификации по прецедентам Генрихов, Игорь Евгеньевич 2013
Время генерации: 0.677, запросов: 965