课程信息
4.9
295 个评分
35 个审阅
100% 在线

100% 在线

立即开始,按照自己的计划学习。
可灵活调整截止日期

可灵活调整截止日期

根据您的日程表重置截止日期。
完成时间(小时)

完成时间大约为21 小时

建议:5 hours/week...
可选语言

俄语(Russian)

字幕:俄语(Russian)
100% 在线

100% 在线

立即开始,按照自己的计划学习。
可灵活调整截止日期

可灵活调整截止日期

根据您的日程表重置截止日期。
完成时间(小时)

完成时间大约为21 小时

建议:5 hours/week...
可选语言

俄语(Russian)

字幕:俄语(Russian)

教学大纲 - 您将从这门课程中学到什么

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

常见问题

  • 注册以便获得证书后,您将有权访问所有视频、测验和编程作业(如果适用)。只有在您的班次开课之后,才可以提交和审阅同学互评作业。如果您选择在不购买的情况下浏览课程,可能无法访问某些作业。

  • 您购买证书后,将有权访问所有课程材料,包括评分作业。完成课程后,您的电子课程证书将添加到您的成就页中,您可以通过该页打印您的课程证书或将其添加到您的领英档案中。如果您只想阅读和查看课程内容,可以免费旁听课程。

还有其他问题吗?请访问 学生帮助中心