Доставка любой диссертации в формате PDF и WORD за 499 руб. на e-mail - 20 мин. 800 000 наименований диссертаций и авторефератов. Все авторефераты диссертаций - БЕСПЛАТНО
Рубанов, Олег Игоревич
01.01.09
Кандидатская
2014
Москва
68 с. : ил.
Стоимость:
499 руб.
Содержание
Обозначения
Введение
1 История вопроса и формулировки результатов
1.1 История вопроса
1.2 Нижние оценки хроматических чисел трёхмерных графов
расстояний с запретами на клики
1.3 Нижние оценки хроматических чисел графов расстояний с
запретами на клики в растущей размерности
1.3.1 Результаты с одним запрещённым расстоянием
1.3.2 Сравнение оценок СсПЧие(^) в теоремах 4, 5, 6 и 7
1.3.3 Результаты с несколькими запрещёнными расстояниями
1.3.4 Таблицы результатов теоремы
2 Хроматические числа трёхмерных графов расстояний без тетраэдров и треугольников
2.1 Доказательство теоремы
2.2 Доказательство теоремы
2.2.1 Основная часть доказательства теоремы
2.2.2 Доказательство предложения 2
2.2.3 Построение графа Т «шевелением»: вспомогательные
леммы
2.2.4 Процедура «шевеления»
3 Асимптотика хроматических чисел графов расстояний с несколькими запрещёнными расстояниями и без больших клик
при росте размерности пространства
3.1 Доказательство теоремы
3.2 Доказательство теоремы
3.3 Доказательство теоремы
3.4 Небольшой комментарий к теореме
3.5 Решение экстремальной задачи
Список литературы
Обозначения
• Ж‘ — п-мерное евклидово пространство
• (х, у) — скалярное произведение векторов X и у
• |х|, А — Х — модуль вектора х, А~к
• Ш — вектор из начала координат в точку X
• ЕК — математическое ожидание случайной величины V
• P(Z) — вероятность события Я.
• 1 — глава
• 1.2 — раздел 2 главы
• 1.2.3 — пункт 3 раздела 2 главы
Мозеровских веретён относительно осей, проходящих через пары точек А, Л3 И А2, /І4, и небольшим перебором.
Теорема доказана. Добавим, что полученный граф имеет 19 вершин и 44 ребра.
2.2 Доказательство теоремы
2.2.1 Основная часть доказательства теоремы
В нашей конструкции в качестве одной из составных частей мы будем использовать модификацию графа расстояний, построенного П. О’Доннеллом и Р. Хохбергом (см. [4], сам граф изображён на рисунке 1.2). Мы обозначим его Т> (см. рисунок 2.4).
ы) Аі Л
Все отмеченные здесь точки, обозначенные строчными буквами, представляют вершины, а отрезки и дуги, как сплошные, так и пунктирные, которые их соединяют, представляют рёбра. Граф состоит из 4-цикла {А, А2, Аз, УІ4} и 5-циклов ГД, Ні и Е2, которые представлены сплошными линиями, а также нескольких рёбер, которые проведены между этими циклами.
Лемма 1. Хроматическое число графа, изображённого на рисунке 2.4, равняется четырём. Кроме того, он не содержит треугольников.
Доказательство. Утверждение об отсутствии треугольников очевидно. Достаточно заметить, что граф состоит из 4-цикла {Аі, А2, Аз, АД и 5-циклов
Название работы | Автор | Дата защиты |
---|---|---|
Конструктивные описания графов | Иорданский, Михаил Анатольевич | 2001 |
Конструкции плотно упакованных кодов и нижние оценки их числа | Кротов, Денис Станиславович | 2000 |
Комбинаторные свойства сечений обобщенных пирамид Паскаля | Серегина, Марина Валерьевна | 2011 |