Об этом курсе
4.9
Оценки: 295
Рецензии: 35
100% онлайн

100% онлайн

Начните сейчас и учитесь по собственному графику.
Гибкие сроки

Гибкие сроки

Назначьте сроки сдачи в соответствии со своим графиком.
Часов на завершение

Прибл. 21 часа на выполнение

Предполагаемая нагрузка: 5 hours/week...
Доступные языки

Русский

Субтитры: Русский
100% онлайн

100% онлайн

Начните сейчас и учитесь по собственному графику.
Гибкие сроки

Гибкие сроки

Назначьте сроки сдачи в соответствии со своим графиком.
Часов на завершение

Прибл. 21 часа на выполнение

Предполагаемая нагрузка: 5 hours/week...
Доступные языки

Русский

Субтитры: Русский

Программа курса: что вы изучите

Неделя
1
Часов на завершение
3 ч. на завершение

Введение. Базовые понятия теории графов

В первую неделю курса мы познакомимся с понятием графа, научимся отличать граф от его изображения, поговорим о разных видах графов. Мы вспомним, с чего началась теория графов, научимся представлять в виде графа структуру интернета. Мы обсудим такие важные понятия, как маршруты в графах, степень вершины, связность, а также начнем говорить про важный класс графов - деревья....
Reading
17 видео ((всего 104 мин.)), 6 материалов для самостоятельного изучения, 1 тест
Video17 видео
МФТИ1мин
Примеры графов. Граф и его изображение10мин
Ориентированные графы4мин
Кёнигсбергские мосты. Мультиграфы5мин
Граф интернета. Псевдографы4мин
Определение графа5мин
Маршруты в графах10мин
Связность, подграфы7мин
Степень вершины3мин
Деревья, эквивалентные определения дерева5мин
Знакомства6мин
Число мультиграфов4мин
Путь в графе5мин
Перенумерация цикла8мин
Последовательности степеней9мин
Замкнутый маршрут9мин
Reading6 материала для самостоятельного изучения
МФТИ10мин
Теоретический материал к семинару10мин
Задачи к семинару10мин
Решение задач10мин
Дополнительные задачи к неделе 110мин
Конспект лекции 110мин
Quiz1 практическое упражнение
Задание к неделе 118мин
Неделя
2
Часов на завершение
3 ч. на завершение

Эквивалентные определения дерева. Планарные графы

На этой неделе мы научимся определять деревья четырьмя различными способами, и поговорим о том, как правильно раскрашивать географические карты. Мы вспомним знаменитую теорему о четырех красках, а также критерий Куратовского о том, как определить, можно ли нарисовать данный граф на плоскости без пересечений ребер. В последней части лекции мы обсудим формулу Эйлера для планарных графов и некоторые из её множественных следствий....
Reading
17 видео ((всего 147 мин.)), 4 материалов для самостоятельного изучения, 1 тест
Video17 видео
Доказательство второй импликации13мин
Доказательство третьей импликации9мин
Доказательство четвертой импликации6мин
Планарность. Гипотеза о четырех красках10мин
Примеры непланарных графов5мин
Критерий Куратовского7мин
Плоские графы, грани и теорема Жордана8мин
Формула Эйлера10мин
Следствие для числа ребер13мин
Хроматическое число планарных графов8мин
Доказательство оценки хроматического числа13мин
Минимальное число ребер2мин
Число пересечений в полном графе2мин
Число ребер в планарном графе и формула Эйлера4мин
Характеризация двудольных графов15мин
Двудольные планарные графы9мин
Reading4 материала для самостоятельного изучения
Теоретический материал к семинару10мин
Задачи к семинару10мин
Решения задач10мин
Дополнительные задачи к неделе 210мин
Quiz1 практическое упражнение
Задание к неделе 218мин
Неделя
3
Часов на завершение
3 ч. на завершение

Формула Кэли. Унициклические графы. Эйлеровы циклы

На этой неделе мы перечислим все деревья. Для этого нам потребуется перенять опыт древних по подсчету баранов (или козлов). Не остановившись на этом, перечислим и все леса и унициклические графы. Затем мы вернемся к задаче о Кёнигсбергских мостах и получим полное решение этого вопроса....
Reading
15 видео ((всего 115 мин.)), 4 материалов для самостоятельного изучения, 1 тест
Video15 видео
Доказательство формулы. Кодирование деревьев5мин
Построение кодов Прюфера5мин
Взаимно однозначное соответствие кодов и деревьев. Декодирование8мин
Формула для числа унициклических графов6мин
Доказательство формулы14мин
Эйлеровы циклы5мин
Критерий эйлеровости3мин
Первая часть доказательства критерия11мин
Вторая часть доказательства критерия12мин
Центр дерева6мин
Деревья с заданной последовательностью степеней11мин
Код Прюфера из различных чисел3мин
Число неизоморфных деревьев6мин
Ориентация графа4мин
Reading4 материала для самостоятельного изучения
Теоретический материал к семинару10мин
Задачи к семинару10мин
Решения задач10мин
Дополнительные задачи к неделе 310мин
Quiz1 практическое упражнение
Задание к неделе 316мин
Неделя
4
Часов на завершение
4 ч. на завершение

Гамильтоновы циклы

На этой неделе мы продолжим обсуждать циклы, проходящие через весь граф. На этот раз мы поговорим про циклы, проходящие через все вершины графа. В отличие от эйлеровых циклов, здесь нет необходимого и достаточного критерия наличия такого цикла. Есть только достаточные условия, и мы обсудим два таких условия, довольно разных по своей природе. По пути мы обсудим такие важные характеристики графа, как независимое число и k-связность. В качестве дополнения, мы расскажем об одном очень интересном классе графов, для которого один из критериев работает, а другой - нет....
Reading
21 видео ((всего 166 мин.)), 6 материалов для самостоятельного изучения, 1 тест
Video21 видео
Множества соседей концов максимального пути9мин
Завершение доказательства теоремы Дирака9мин
Независимые множества5мин
Вершинная связность. Критерий Хватала4мин
Доказательство. В графе есть циклы6мин
Подграф без максимального цикла5мин
Соседи связной компоненты5мин
Соседи компоненты и максимальный цикл7мин
Число соседей больше связности7мин
Завершение доказательства9мин
Число гамильтоновых циклов в полном двудольном графе3мин
Число независимости, связность10мин
Непересекающиеся гамильтоновы циклы12мин
Сравнение двух признаков гамильтоновости на конкретном графе. Определение графа6мин
Работает ли признак Дирака?6мин
Признак Хватала. Оценка связности через общих соседей6мин
Число общих соседей8мин
Примеры независимых множеств, теорема о числе независимости11мин
Доказательство теоремы10мин
Связь с теорией кодирования6мин
Reading6 материала для самостоятельного изучения
Пример гамильтонова графа10мин
Теоретический материал к семинару10мин
Задачи к семинару10мин
Комментарий к лекции10мин
Решения задач10мин
Дополнительные задачи к неделе 410мин
Quiz1 практическое упражнение
Задание к неделе 418мин

Преподавателя

Avatar

Андрей Райгородский

профессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Avatar

Андрей Купавский

кандидат физико-математических наук
Кафедра дискретной математики ФИВТ МФТИ

О Moscow Institute of Physics and Technology

Московский физико-технический институт (неофициально известный как МФТИ или Физтех) является одним из самых престижных в мире учебных и научно-исследовательских институтов. Он готовит высококвалифицированных специалистов в области теоретической и прикладной физики, прикладной математики, информатики, биотехнологии и смежных дисциплин. Физтех был основан в 1951 году Нобелевской премии лауреатами Петром Капицей, Николаем Семеновым, Львом Ландау и Сергеем Христиановичем. Основой образования в МФТИ является уникальная «система Физтеха»: кропотливое воспитание и отбор самых талантливых абитуриентов, фундаментальное образование высшего класса и раннее вовлечение студентов в реальную научно-исследовательскую работу. Среди выпускников МФТИ есть Нобелевские лауреаты, основатели всемирно известных компаний, известные космонавты, изобретатели, инженеры....

Часто задаваемые вопросы

  • Зарегистрировавшись на сертификацию, вы получите доступ ко всем видео, тестам и заданиям по программированию (если они предусмотрены). Задания по взаимной оценке сокурсниками можно сдавать и проверять только после начала сессии. Если вы проходите курс без оплаты, некоторые задания могут быть недоступны.

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

Остались вопросы? Посетите Центр поддержки учащихся.