Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются "планарными". Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день.
Граф как математический объект оказался полезным во многих теоретических и практических задачах. Наверное, дело в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии.
Этот курс служит введением в современную теорию графов. Мы, конечно, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов.
Материал изложен с самых основ и на доступном языке. Целью этого курса является не только познакомить вас с вопросами и методами теории графов, но и развить у неподготовленных слушателей культуру математического мышления. Поэтому курс доступен широкому кругу слушателей. Для освоения материала будет достаточно знания математики на хорошем школьном уровне и базовых знаний комбинаторики.
Курс состоит из 7 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов.
Na lição
Формула Кэли. Унициклические графы. Эйлеровы циклы
На этой неделе мы перечислим все деревья. Для этого нам потребуется перенять опыт древних по подсчету баранов (или козлов). Не остановившись на этом, перечислим и все леса и унициклические графы. Затем мы вернемся к задаче о Кёнигсбергских мостах и получим полное решение этого вопроса.