Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются "планарными". Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день.
Граф как математический объект оказался полезным во многих теоретических и практических задачах. Наверное, дело в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии.
Этот курс служит введением в современную теорию графов. Мы, конечно, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов.
Материал изложен с самых основ и на доступном языке. Целью этого курса является не только познакомить вас с вопросами и методами теории графов, но и развить у неподготовленных слушателей культуру математического мышления. Поэтому курс доступен широкому кругу слушателей. Для освоения материала будет достаточно знания математики на хорошем школьном уровне и базовых знаний комбинаторики.
Курс состоит из 7 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов.
Создатели курса: МФТИ
Внешние ресурсы: В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. Лекции по теории графов. М.: Книжный дом «Либроком», 2009. А. А. Зыков. Теория конечных графов. Новосибирск: Наука, 1969. М. Свами, К. Тхуласираман. Графы, сети и алгоритмы. М.: Мир, 1984. M. Aigner, G. M. Ziegler. Proofs From THE BOOK. Fourth Edition. Springer, 2009. B. Bollobás. Modern Graph Theory. Springer, 1998. J. A. Bondy, U. S. R. Murty. Graph Theory. Springer, 2008.
Требования к участникам
-
Курс займет 7 недель
-
Курс доступен широкому кругу слушателей
-
Достаточно знания математики и базовых знаний комбинаторики
-
Сертификат участника обычно выдается при достижении 50% от общего рейтинга при условии сдачи работ до дедлайна. Сертификат с отличием, как правило, выдается при достижении 75% от общего рейтинга при условии сдачи работ до дедлайна
Курс является частью
Программа курса
Как проходит обучение?
- Видеоматериалы
- Оцениваемые задания
- Раздел обсуждений с сокурсниками и преподавателями
- Возможность получения подтвержденного сертификата МФТИ
Возможно прохождение курса в бесплатном режиме