Теория графов

О курсе

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

Результат

По итогам успешного прохождения курса слушатель познакомится с понятием графа, с видами и различными характеристиками и свойствами графов. Слушатель узнает о задаче о правильных раскрасках и о возможности нарисовать данный граф на плоскости без пересечений ребер, а также научится разными способами определять деревья и перечислять их. Наконец, слушатель познакомится с понятиями эйлеровых и гамильтоновых циклов, паросочетаний и даже прикоснется к задачам экстремальной теории графов.

О преподавателях

Райгородский Андрей МихайловичДиректор Физтех-школы прикладной математики и информатики, главный научный сотрудник - заведующий лабораторией продвинутой комбинаторики и сетевых приложений, заведующий лабораторией прикладных исследований МФТИ - Сбербанк, заведующий кафедрой дискретной математики ФИВТ, руководитель совместных исследовательских программ Яндекса и МФТИ, главный редактор журнала Moscow Journal of Combinatorics and Number Theory

Входные требования

Материал изложен с самых основ и на доступном языке. Целью этого курса является не только познакомить вас с вопросами и методами теории графов, но и развить у неподготовленных слушателей культуру математического мышления. Поэтому курс доступен широкому кр

угу слушателей. Для освоения материала будет достаточно знания математики на хорошем школьном уровне и базовых знаний комбинаторики.

Содержание курса

Понятие графа и виды графов.
Различные применения графов: от Кенигсберских мостов до Интернета.
Связность графа, подграфы и степень вершины.
Эквивалентные определения деревьев.
Планарность и критерий Куратовского
Формула Эйлера.
Хроматическое число планарного графа.
Перечисление деревьев: код Прюфера и формула Кэли.
Формула для числа унициклических графов.
Эйлеровы циклы и критерий эйлеровости.
Гамильтоновы циклы. Критерий Дирака и критерий Хватала.
Паросочетания. Теорема Холла и Кенига.
Экстремальная теория графов. Теорема Турана.
Аналог теоремы Турана для графов на плоскости.
Теория Рамсея. Знакомства среди шести человек.
Определение числа Рамсея.
Нижняя и верхняя оценки чисел Рамсея.

Профессии, специальности и направления подготовки	09.03.01 Информатика и вычислительная техника 16.00.00 Физико-технические науки и технологии 09.00.00 Информатика и вычислительная техника 01.00.00 Математика и механика 03.00.00 Физика и астрономия 10.00.00 Информационная безопасность
Область деятельности	Инженерное дело, технологии и технические науки Математические и естественные науки
Дата окончания записи	17.12.2021
Трудоёмкость в з.е.	3.0
Количество лекций	12
Дата ближайшего старта	01.09.2021
Дата окончания	17.12.2021
ID курса	9117d4dd1136455da6c7b6e56fe06c75
К-во обучающихся на версии курса	17823
Язык	Русский
Длительность	12 недель
Сертификат	Есть
Версия	7

О курсе

Результат

О преподавателях

Входные требования

Содержание курса

Рекомендуемые курсы

Рецензии и оценки

Отсутствует текст отзыва.