Теория графов
Часть 1. Основные понятия теории графов |
Часть 2. Эквивалентные определения дерева и планорность |
Часть 3. Эйлеровость графа. Число деревьев. Число унициклических графов |
Граф как математический объект оказывается полезным во многих теоретических и практических задачах. Дело, пожалуй, в том, что сложность его структуры хорошо отвечает возможностям человеческого мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. В этом курсе будут обсуждены классические задачи и некоторые недавние результаты и тенденции, например, экстремальная теория графов.
Райгородский Андрей Михайлович — доктор физико-математических наук, профессор МФТИ и МГУ.
Похожее
-
Андрей Райгородский
В сороковые годы XX века известными математиками П. Эрдёшом и Г. Хадвигером была поставлена одна из самых коротко формулируемых и в то же время одна из самых ярких и трудных задач комбинаторной геометрии — задача о нахождении хроматического числа евклидова пространства R^n, то есть минимального числа цветов, в которые можно так раскрасить точки пространства, чтобы точки, отстоящие друг от друга на расстояние 1, оказались раскрашенными в разные цвета. Эта задача до сих пор не решена даже для n=2, то есть для евклидовой плоскости, хотя простотой и естественностью своей постановки она сразу привлекла внимание всех математиков.
-
Андрей Райгородский
В сороковые годы XX века известными математиками П. Эрдёшом и Г. Хадвигером была поставлена одна из самых коротко формулируемых и в то же время одна из самых ярких и трудных задач комбинаторной геометрии — задача о нахождении хроматического числа евклидова пространства R^n, т. е. минимального числа цветов, в которые можно так раскрасить точки пространства, чтобы точки, отстоящие друг от друга на расстояние 1, оказались раскрашенными в разные цвета. Эта задача до сих пор не решена даже для n=2, т. е. для плоскости, хотя простотой и естественностью своей постановки она сразу привлекла внимание всех математиков. К настоящему времени разработано много интересных и остроумных подходов к её (пока частичному) решению. Текст брошюры представляет собой запись лекции, прочитанной автором 7 декабря 2002 года на Малом мехмате МГУ для школьников 9–11 классов.
-
Несколько дней назад сообщество математиков — специалистов в теории графов было взволновано сообщением о том, что выдвинутая Стефеном Хидетниеми (Stephen T. Hedetniemi) в 1966 году гипотеза оказалась неверной. Оказывается, хроматическое число тензорного произведения двух графов может быть меньше минимума хроматических чисел сомножителей, а не всегда равно этому минимуму, как когда-то предположил Хидетниеми. Как построить контрпример к этой гипотезе, придумал молодой московский математик Ярослав Шитов.
-
Георгий Шабат
Детские рисунки (dessins d'enfants) – термин, введённый Александром Гротендиком в 70-е годы прошлого века. С «детской» точки зрения этот термин означает граф, вложенный в поверхность; с взрослой – это объект, в котором закодированы различные структуры, относящиеся к далёким друг от друга областям математики. Под подсчётом детских рисунков понимается подсчёт количества детских рисунков ограниченной сложности, которая будет определена. В последние годы были получены замечательные результаты о количествах детских рисунков. Элементарная часть этих результатов будет изложена в курсе.
-
Гаянэ Панина
Курс представляет собой букет из трёх очень старых и трёх очень новых идей. Основной объект — число целых (т.е. с целыми координатами) точек в многограннике. Зачем нужны целые точки? Несколько примеров: многогранник Ньютона, Теорема Бриона — для начала без доказательства, просто в качестве фокуса, а также подсчёт целых метрических ленточных графов. Число целых точек в выпуклом многограннике ведёт себя как полином. Согласно конструкции, в полином, вычисляющий число целых точек, имеет смысл подставлять лишь положительные числа. Чтобы придать смысл отрицательной подстановке, нужны виртуальные многогранники. Двойственность Эрхарта и её естественное обобщение. Секрет фокуса Бриона.
-
Александр Буфетов, Александр Комлов
Рассмотрим конечный связный граф. Сколько в нем остовных деревьев — деревьев, содержащих все вершины графа? А какая их доля содержит данный набор ребер? Цель нашего курса — дать элементарное введение в теорию детерминантных процессов. Мы планируем обсудить недавние достижения и сформулировать нерешенные проблемы. Программа занятий: детерминанты и пфаффианы; остовные деревья; случайные матрицы; мультипликативные функционалы.
-
Гаянэ Панина
Вот три тесно связанные между собой задачи, которые мы будем обсуждать: Как распрямить плотницкую линейку? Можно ли нарисовать на сфере правильно раскрашенный граф? Верна ли старая гипотеза А. Д. Александрова о характеризации сферы? Попутно будет сформулировано много задач разного уровня сложности (именно исследовательских задач, а не упражнений!). Часть из них — для умеющих и любящих программировать. В курсе будет много картинок.
-
Сергей Новиков
Лекция будет посвящена некоторым нестандартным аспектам элементарной симплектической геометрии и линейной алгебры и их применению для нужд квантовой теории рассеяния. Для большинства математиков этот язык непривычен, поэтому все необходимые понятия будут введены самым элементарным образом.
-
Андрей Райгородский, Нелли Литвак
Отрывок из книги математиков Андрея Райгородского и Нелли Литвак, посвященный истории онлайн-рекламы, нобелевскому лауреату Уильяму Викри и стоимости одного клика.
-
Теплым весенним утром Джун Ху шел в зал Макдоннелла Пристонского университета, где его ждали студенты. Однако он не был уверен, что идет в нужном направлении. Ху работает в элитарном Институте перспективных исследований, который располагается неподалеку от студгородка Принстона. Будучи сотрудником института, Ху не обязан преподавать. Тем не менее, он вызвался прочитать студентам продвинутый курс по коммутативной алгебре.
Далее >>>
|
|