Оценки чисел Борсука и Грюнбаума для (0,1)- и (-1, 0, 1)-многогранников в пространствах малой размерности

• Автор: Гольдштейн, Виталий Борисович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 138 с.

Оглавление

Список основных обозначений

Введение

1 История проблем Борсука и Грюнбаума

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

1.1.1 Возникновение гипотезы Борсука

1.1.2 Опровержение гипотезы

1.2 История возникновения проблемы Грюнбаума

1.3 Постановка задачи и формулировки результатов

2 О проблеме Борсука для (0,1)- и (—1,0,1)-многогранников

в пространствах малой размерности

2.1 Описание алгоритма
2.1.1 Устройство алгоритма
2.1.2 Отсечения перебора
2.1.3 Отсечение пустоты подграфа
2.1.4 Отсечение максимальности по включению
2.1.5 Отсечения, связанные с симметрией
Изометрическое преобразование
Отсечение изометрии отражения
Отсечение изометрии перестановки координат

2.1.6 Отсечение раскраски графа
Отсечение жадной раскраски
Отсечение раскраски табу
2.1.7 Дополнительные отсечения
2.2 Доказательства лемм
Доказательство леммы
Доказательство леммы
2.3 Работа программы
О проблеме Грюнбаума для (0,1)- и (—1,0,1)-многогранников в пространствах малой размерности
3.1 Описание алгоритма
3.1.1 Устройство алгоритма
3.1.2 Отсечения перебора
3.1.3 Отсечение пустоты подграфа 7ф
3.1.4 Отсечение максимальности по включению
3.1.5 Отсечения, связанные с симметрией
3.1.6 Отсечение помещения в шары
Отсечение жадным алгоритмом помещения в шары ... 40 Отсечение переборным алгоритмом помещения в шары .
3.2 Работа программы
3.3 Замечание о покрытии (0,1)-многогранников шарами с сГ2 по-
луцелыми координатами центров
3.4 Обозримое доказательство в случае (0,1)-многогранников
3.4.1 Доказательства вспомогательных лемм
Лемма о множествах диаметра
Леммы о множествах больших диаметров
Леммы о покрытии замкнутыми шарами множеств диаметра /2 и их следствия
Леммы о покрытии открытыми шарами множеств диаметра л/2 и их следствия
3.4.2 Доказательства основных лемм
Лемма о покрытии замкнутыми шарами (0, 1)-
многранников в размерности
Лемма о покрытии замкнутыми шарами (0, 1)-
многранников в размерности
Лемма о покрытии открытыми шарами (0, 1)-
многранников в размерности
Заключение и открытые проблемы
Список использованных источников
Приложение
Общий исходный код для двух программ
Исходный код алгоритма в проблеме Борсука
Исходный код алгоритма в проблеме Грюнбаума

2. если а = 1, то следует рассмотреть три под случая и убедиться в корректности равенства прямым вычислением:
• если х = у, то обе части равенства равны 0;
• если х = 0, у = 1, то обе части равны 1;
• если х = 0, у = 2, то обе части равны 2.
Так как все слагаемые суммы равны, то и сами суммы равны. Лемма доказана.
2.3 Работа программы
Описанный в разделе 2.1 алгоритм был реализован на языке С++. Соответствующий код находится в приложении. Программа была запущена на персональном компьютере с 4 гигабайтами оперативной памяти и с одним процессором с тактовой частотой 2.8 гигагерц.
Для демонстрации эффективности использования отсечений приводится сравнительная таблица 2.1. В данной таблице сравнивается время работы алгоритма при использовании части отсечений, описанных в разделе 2.1.
В первом столбце таблицы 2.1 написано множество, на котором работала программа. В последующих столбцах написано время работы программы с различными отсечениями в минутах.
Таблица 2.
Множество V Все отсечения Без раскраски Без симметрии Без раскраски и симстрии
{0,1}", п < 6 0 0 0
{0,1}7 0 0 0
{0,1}® 0 11 2
{0,1}9 20 > 104 > 104 >
Из таблицы 2.1 видно, что наибольший вклад дает отсечение раскраски, однако использование отсечения симметрии как дополнительного существенно ускоряет работу программы.