Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://www.mccme.ru/dubna/2010/courses/rajgor.htm
Дата изменения: Mon May 31 20:33:34 2010 Дата индексирования: Sun Sep 12 05:10:25 2010 Кодировка: koi8-r Поисковые слова: mercury surface |
На главную страницу ЛШСМ-2010 | К списку курсов ЛШСМ-2010 |
Андрей Михайлович РайгородскийЭкстремальные задачи комбинаторики и теории геометрических графовА.М. Райгородский планирует провести 4 занятия. |
![]() |
Лекции будут посвящены одному из самых ярких разделов современной комбинаторики — теории геометрических графов. Основным объектом нашего исследования будет так называемый дистанционный граф (он же граф расстояний), вершины которого — это точки плоскости (или пространства более высокой размерности), а ребра — отрезки заданной длины. Этот объект весьма труден для исследования, и на многие — казалось бы, простые — вопросы о его свойствах нет окончательных ответов. Нас будут в первую очередь интересовать «экстремальные» характеристики графов расстояний. Среди них хроматическое число — минимальное количество цветов, в которые можно так покрасить вершины графа, чтобы вершины, соединенные ребром, были разноцветными; обхват — длина кратчайшего цикла в графе. Для отыскания этих характеристик мы познакомимся с основами линейно-алгебраического и вероятностного методов в комбинаторике. Кроме того, мы пронаблюдаем интересные связи между задачами комбинаторной геометрии и теории кодирования.
Бóльшая часть материала будет доступна старшеклассникам. Приблизительная структура лекций следующая.
Лекция 1. Определение дистанционного графа. Простейшие свойства: число ребер в случае плоскости и пространства, хроматические числа в маленьких размерностях и др. Обхват дистанционного графа. Клики (полные подграфы) в дистанционных графах.
Лекция 2. Задача о наибольшей мощности совокупности M = {M1,…, Ms} подмножеств конечного множества с запретами на величины |Mi ∩ Mj| . Линейно-алгебраический метод. Хроматические числа дистанционных графов в растущей размерности.
Лекция 3. Некоторые идеи теории кодирования. Построение дистанционных графов, не содержащих клик заданного размера и имеющих большое хроматическое число. Большое хроматическое число и большой обхват.
Лекция 4. Вероятностный метод. Уточнение результатов третьей лекции.