Об этом курсе
Недавно просмотрено: 22,589

100% онлайн

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

Гибкие сроки

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

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

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

Русский

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

100% онлайн

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

Гибкие сроки

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

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

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

Русский

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

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

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

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

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

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

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

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

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

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

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

20%

получил значимые преимущества в карьере благодаря этому курсу

25%

стал больше зарабатывать или получил повышение

Лучшие отзывы о курсе Теория графов

автор: DDOct 30th 2016

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

автор: DMNov 8th 2016

Отличный курс, правда местами задания сложные, но зато есть над чем поломать голову) Это тот курс, который даст хорошие знания и для окончания которого действительно стоит постараться.

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

Avatar

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

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

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

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

О Московский физико-технический институт

Московский физико-технический институт (Физтех) является одним из ведущих вузов страны и входит в основные рейтинги лучших университетов мира. Институт обладает не только богатой историей – основателями и профессорами института были Нобелевские лауреаты Пётр Капица, Лев Ландау и Николай Семенов – но и большой научно-исследовательской базой. Основой образования в МФТИ является уникальная «система Физтеха», сформулированная Петром Капицей: кропотливый отбор одаренных и склонных к творческой работе абитуриентов; участие в обучении ведущих научных работников; индивидуальный подход к отдельным студентам с целью развития их творческих задатков; воспитание с первых шагов в атмосфере технических исследований и конструктивного творчества с использованием потенциала лучших лабораторий страны. Среди выпускников МФТИ — нобелевские лауреаты Андрей Гейм и Константин Новоселов, основатель компании ABBYY Давид Ян, один из авторов архитектурных принципов построения вычислительных комплексов Борис Бабаян и др....

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

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

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

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