Теория графов [1] Основные понятия теории графов // Андрей Райгородский

Граф как математический объект оказывается полезным во многих теоретических и практических задачах. Дело, пожалуй, в том, что сложность его структуры хорошо отвечает возможностям человеческого мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. В этом курсе будут обсуждены классические задачи и некоторые недавние результаты и тенденции, например, экстремальная теория графов. Райгородский Андрей Михайлович — доктор физико-математических наук, профессор МФТИ и МГУ.