課程信息
4.9
287 個評分
34 個審閱
100% 在線

100% 在線

立即開始,按照自己的計劃學習。
可靈活調整截止日期

可靈活調整截止日期

根據您的日程表重置截止日期。
完成時間(小時)

完成時間大約為23 小時

建議:5 hours/week...
可選語言

俄語(Russian)

字幕:俄語(Russian)...
100% 在線

100% 在線

立即開始,按照自己的計劃學習。
可靈活調整截止日期

可靈活調整截止日期

根據您的日程表重置截止日期。
完成時間(小時)

完成時間大約為23 小時

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

常見問題

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

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

還有其他問題嗎?請訪問 學生幫助中心