|
Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://www.mccme.ru/ium/s06/cg.html
Дата изменения: Wed Feb 1 21:13:49 2006 Дата индексирования: Tue Oct 2 01:19:01 2012 Кодировка: koi8-r Поисковые слова: http astrokuban.info astrokuban |
1. Проблема Хадвигера - Гохберга - Маркуса - Леви освещения границы выпуклого тела. Решение проблемы освещения для трехмерных центрально-симметричных тел. Оценки числа освещения в произвольной размерности.
2. Комбинаторная задача о покрытии и ее связь с проблемами Борсука (разбиение тел на части меньшего диаметра), Грюнбаума (покрытие тел шарами того же диаметра) и Нелсона - Эрдеша - Хадвигера (о раскраске пространства).
2.1. Системы общих представителей (с.о.п.). Верхняя оценка мощности минимальной с.о.п. для совокупности подмножеств конечного множества. Различные способы получения нижних оценок.
2.2. Применение техники пункта 2.1 к проблемам Борсука и Нелсона - Эрдеша - Хадвигера для решетчатых многогранников.
2.3. Применение техники пункта 2.1 к проблеме Грюнбаума для решетчатых многогранников.
2.4. Несколько слов о размерности Вапника - Червоненкиса. Связь между размерностью Вапника - Червоненкиса и задачей о покрытии. Применение размерности Вапника - Червоненкиса к некоторым другим задачам комбинаторной геометрии.
3. Графы и случайные графы.
3.1. Проблема Нелсона - Эрдеша - Хадвигера в терминах теории графов.
3.2. Построение плоского графа с хроматическим числом 4 и со сколь угодно большим обхватом.
3.3. Несколько слов о случайном графе. Хроматическое число случайного графа. Связь с проблемой Нелсона - Эрдеша - Хадвигера.
