| RUS ENG |
| Полная версия |
|
|
|
| ВИДЕОТЕКА |
|
|
|||
|
Экстремальные задачи комбинаторики и теории геометрических графов. Лекция 1 А. М. Райгородский |
|||
|
Аннотация: Лекции будут посвящены одному из самых ярких разделов современной комбинаторики — теории геометрических графов. Основным объектом нашего исследования будет так называемый дистанционный граф (он же граф расстояний), вершины которого — это точки плоскости (или пространства более высокой размерности), а ребра — отрезки заданной длины. Этот объект весьма труден для исследования, и на многие — казалось бы, простые — вопросы о его свойствах нет окончательных ответов. Нас будут в первую очередь интересовать «экстремальные» характеристики графов расстояний. Среди них хроматическое число — минимальное количество цветов, в которые можно так покрасить вершины графа, чтобы вершины, соединенные ребром, были разноцветными; обхват — длина кратчайшего цикла в графе. Для отыскания этих характеристик мы познакомимся с основами линейно-алгебраического и вероятностного методов в комбинаторике. Кроме того, мы пронаблюдаем интересные связи между задачами комбинаторной геометрии и теории кодирования. Бо́льшая часть материала будет доступна старшеклассникам. Приблизительная структура лекций следующая. Лекция 1. Определение дистанционного графа. Простейшие свойства: число ребер в случае плоскости и пространства, хроматические числа в маленьких размерностях и др. Обхват дистанционного графа. Клики (полные подграфы) в дистанционных графах. Лекция 2. Задача о наибольшей мощности совокупности Лекция 3. Некоторые идеи теории кодирования. Построение дистанционных графов, не содержащих клик заданного размера и имеющих большое хроматическое число. Большое хроматическое число и большой обхват. Лекция 4. Вероятностный метод. Уточнение результатов третьей лекции.
|
|||