À propos de ce cours
10,393

100 % en ligne

Commencez dès maintenant et apprenez aux horaires qui vous conviennent.

Dates limites flexibles

Réinitialisez les dates limites selon votre disponibilité.

Approx. 22 heures pour terminer

Recommandé : 5 hours/week...

Russe

Sous-titres : Russe

100 % en ligne

Commencez dès maintenant et apprenez aux horaires qui vous conviennent.

Dates limites flexibles

Réinitialisez les dates limites selon votre disponibilité.

Approx. 22 heures pour terminer

Recommandé : 5 hours/week...

Russe

Sous-titres : Russe

Programme du cours : ce que vous apprendrez dans ce cours

Semaine
1
3 heures pour terminer

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

В первую неделю курса мы познакомимся с понятием графа, научимся отличать граф от его изображения, поговорим о разных видах графов. Мы вспомним, с чего началась теория графов, научимся представлять в виде графа структуру интернета. Мы обсудим такие важные понятия, как маршруты в графах, степень вершины, связность, а также начнем говорить про важный класс графов - деревья....
17 vidéos (Total 104 min), 6 lectures, 1 quiz
17 vidéos
МФТИ1 min
Примеры графов. Граф и его изображение10 min
Ориентированные графы4 min
Кёнигсбергские мосты. Мультиграфы5 min
Граф интернета. Псевдографы4 min
Определение графа5 min
Маршруты в графах10 min
Связность, подграфы7 min
Степень вершины3 min
Деревья, эквивалентные определения дерева5 min
Знакомства6 min
Число мультиграфов4 min
Путь в графе5 min
Перенумерация цикла8 min
Последовательности степеней9 min
Замкнутый маршрут9 min
6 lectures
МФТИ10 min
Теоретический материал к семинару10 min
Задачи к семинару10 min
Решение задач10 min
Дополнительные задачи к неделе 110 min
Конспект лекции 110 min
1 exercice pour s'entraîner
Задание к неделе 118 min
Semaine
2
3 heures pour terminer

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

На этой неделе мы научимся определять деревья четырьмя различными способами, и поговорим о том, как правильно раскрашивать географические карты. Мы вспомним знаменитую теорему о четырех красках, а также критерий Куратовского о том, как определить, можно ли нарисовать данный граф на плоскости без пересечений ребер. В последней части лекции мы обсудим формулу Эйлера для планарных графов и некоторые из её множественных следствий....
17 vidéos (Total 147 min), 4 lectures, 1 quiz
17 vidéos
Доказательство второй импликации13 min
Доказательство третьей импликации9 min
Доказательство четвертой импликации6 min
Планарность. Гипотеза о четырех красках10 min
Примеры непланарных графов5 min
Критерий Куратовского7 min
Плоские графы, грани и теорема Жордана8 min
Формула Эйлера10 min
Следствие для числа ребер13 min
Хроматическое число планарных графов8 min
Доказательство оценки хроматического числа13 min
Минимальное число ребер2 min
Число пересечений в полном графе2 min
Число ребер в планарном графе и формула Эйлера4 min
Характеризация двудольных графов15 min
Двудольные планарные графы9 min
4 lectures
Теоретический материал к семинару10 min
Задачи к семинару10 min
Решения задач10 min
Дополнительные задачи к неделе 210 min
1 exercice pour s'entraîner
Задание к неделе 218 min
Semaine
3
3 heures pour terminer

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

На этой неделе мы перечислим все деревья. Для этого нам потребуется перенять опыт древних по подсчету баранов (или козлов). Не остановившись на этом, перечислим и все леса и унициклические графы. Затем мы вернемся к задаче о Кёнигсбергских мостах и получим полное решение этого вопроса....
15 vidéos (Total 115 min), 4 lectures, 1 quiz
15 vidéos
Доказательство формулы. Кодирование деревьев5 min
Построение кодов Прюфера5 min
Взаимно однозначное соответствие кодов и деревьев. Декодирование8 min
Формула для числа унициклических графов6 min
Доказательство формулы14 min
Эйлеровы циклы5 min
Критерий эйлеровости3 min
Первая часть доказательства критерия11 min
Вторая часть доказательства критерия12 min
Центр дерева6 min
Деревья с заданной последовательностью степеней11 min
Код Прюфера из различных чисел3 min
Число неизоморфных деревьев6 min
Ориентация графа4 min
4 lectures
Теоретический материал к семинару10 min
Задачи к семинару10 min
Решения задач10 min
Дополнительные задачи к неделе 310 min
1 exercice pour s'entraîner
Задание к неделе 316 min
Semaine
4
4 heures pour terminer

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

На этой неделе мы продолжим обсуждать циклы, проходящие через весь граф. На этот раз мы поговорим про циклы, проходящие через все вершины графа. В отличие от эйлеровых циклов, здесь нет необходимого и достаточного критерия наличия такого цикла. Есть только достаточные условия, и мы обсудим два таких условия, довольно разных по своей природе. По пути мы обсудим такие важные характеристики графа, как независимое число и k-связность. В качестве дополнения, мы расскажем об одном очень интересном классе графов, для которого один из критериев работает, а другой - нет....
21 vidéos (Total 166 min), 6 lectures, 1 quiz
21 vidéos
Множества соседей концов максимального пути9 min
Завершение доказательства теоремы Дирака9 min
Независимые множества5 min
Вершинная связность. Критерий Хватала4 min
Доказательство. В графе есть циклы6 min
Подграф без максимального цикла5 min
Соседи связной компоненты5 min
Соседи компоненты и максимальный цикл7 min
Число соседей больше связности7 min
Завершение доказательства9 min
Число гамильтоновых циклов в полном двудольном графе3 min
Число независимости, связность10 min
Непересекающиеся гамильтоновы циклы12 min
Сравнение двух признаков гамильтоновости на конкретном графе. Определение графа6 min
Работает ли признак Дирака?6 min
Признак Хватала. Оценка связности через общих соседей6 min
Число общих соседей8 min
Примеры независимых множеств, теорема о числе независимости11 min
Доказательство теоремы10 min
Связь с теорией кодирования6 min
6 lectures
Пример гамильтонова графа10 min
Теоретический материал к семинару10 min
Задачи к семинару10 min
Комментарий к лекции10 min
Решения задач10 min
Дополнительные задачи к неделе 410 min
1 exercice pour s'entraîner
Задание к неделе 418 min
Semaine
5
3 heures pour terminer

Паросочетания. Теоремы Холла и Кёнига

На этой неделе мы поговорим про паросочетания. Мы узнаем, что нужно, чтобы переженить всех юношей и девушек по любви. Мы обсудим две классических теоремы, у одной из которых очень изящное доказательство по индукции, а у другой не менее изящное доказательство алгоритмическое. А на семинаре мы узнаем, что эти две теоремы эквивалентны....
15 vidéos (Total 150 min), 4 lectures, 1 quiz
15 vidéos
Необходимое условие существования паросочетания. Теорема Холла8 min
Доказательство теоремы Холла. Два случая6 min
Разбор случая 110 min
Разбор случая 212 min
Вершинное покрытие, теорема Кёнига6 min
Первая часть доказательства. Чередующиеся цепи12 min
Вторая часть доказательства. Разбиение множества вершин8 min
Третья часть доказательства. Построение вершинного покрытия10 min
Завершение доказательства. Вершинное покрытие работает10 min
Теорема Холла из теоремы Кёнига9 min
Теорема Кёнига из теоремы Холла11 min
Паросочетания и степени вершин10 min
Паросочетания в деревьях5 min
К-регулярный двудольный граф15 min
4 lectures
Теоретический материал к семинару10 min
Задачи к семинару10 min
Решения задач10 min
Дополнительные задачи к неделе 510 min
1 exercice pour s'entraîner
Задание к неделе 518 min
Semaine
6
3 heures pour terminer

Экстремальная теория графов. Теорема Турана

На этой неделе мы начнем разговор про экстремальную теорию графов, которая ставит вопросы про то, с какого момента графы начинают обладать тем или иным свойством. В частности, мы выясним, сколько ребер должен иметь граф, чтобы он гарантированно содержал треугольник. В конце лекции мы узнаем, что графы на плоскости в экстремальных задачах ведут себя несколько по-другому, нежели графы абстрактные. ...
13 vidéos (Total 123 min), 4 lectures, 1 quiz
13 vidéos
Теорема Турана6 min
Доказательство теоремы Турана16 min
Пример графа, на котором оценка Турана достигается7 min
Теорема Турана в терминах кликового числа7 min
Задача про графы на плоскости9 min
Решение задачи15 min
Двудольный подграф13 min
Вершинное покрытие для графа без треугольников4 min
Граф без четных циклов10 min
Хроматическое число и число независимости6 min
Хроматическое число и максимальная степень7 min
Хроматическое число графа и его дополнения11 min
4 lectures
Теоретический материал к семинару10 min
Задачи к семинару10 min
Решения задач10 min
Дополнительные задачи к неделе 610 min
1 exercice pour s'entraîner
Задание к неделе 618 min
Semaine
7
3 heures pour terminer

Теория Рамсея

На заключительной лекции мы поговорим про теорию Рамсея. Вы узнаете много нового о знакомствах, о том, сколько раз можно в одном доказательстве применить принцип Дирихле и о том, что доказать существование графа и привести пример такого графа - это зачастую совсем разные по сложности задачи....
20 vidéos (Total 148 min), 4 lectures, 1 quiz
20 vidéos
Начало доказательства. Применение принципа Дирихле4 min
Завершение доказательства6 min
Формулировка в терминах независимых множеств и раскрасок5 min
Пяти вершин недостаточно2 min
Определение чисел Рамсея4 min
Значения R(s,t) для малых s13 min
Верхняя оценка чисел Рамсея с помощью рекурсии2 min
Доказательство. Принцип Дирихле7 min
Завершение доказательства10 min
Численные верхние оценки чисел Рамсея12 min
Нижняя оценка числа Рамсея. Что требуется доказать?3 min
Подсчет графов с большими полными подграфами12 min
Вычисления. Завершение доказательства теоремы4 min
Обсуждение нижних оценок4 min
Число Рамсея для звезды5 min
Число Рамсея для дерева и полного графа13 min
Раскраска плоскости6 min
Монотонные последовательности9 min
Пути или звезды13 min
4 lectures
Теоретический материал к семинару10 min
Задачи к семинару10 min
Решение задач10 min
Дополнительные задачи к неделе 710 min
1 exercice pour s'entraîner
Задание к неделе 714 min
Semaine
8
18 minutes pour terminer

Экзамен

Заключительная работа по материалу всего курса...
1 quiz
1 exercice pour s'entraîner
Экзамен. Один граф18 min
4.9
41 avisChevron Right

20%

a bénéficié d'un avantage concret dans sa carrière grâce à ce cours

25%

a obtenu une augmentation de salaire ou une promotion

Meilleurs avis

par DDOct 30th 2016

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

par DMNov 8th 2016

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

Enseignants

Avatar

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

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

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

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

À propos de Institut de physique et de technologie de Moscou

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

Foire Aux Questions

  • Une fois que vous êtes inscrit(e) pour un Certificat, vous pouvez accéder à toutes les vidéos de cours, et à tous les quiz et exercices de programmation (le cas échéant). Vous pouvez soumettre des devoirs à examiner par vos pairs et en examiner vous-même uniquement après le début de votre session. Si vous préférez explorer le cours sans l'acheter, vous ne serez peut-être pas en mesure d'accéder à certains devoirs.

  • Lorsque vous achetez un Certificat, vous bénéficiez d'un accès à tout le contenu du cours, y compris les devoirs notés. Lorsque vous avez terminé et réussi le cours, votre Certificat électronique est ajouté à votre page Accomplissements. À partir de cette page, vous pouvez imprimer votre Certificat ou l'ajouter à votre profil LinkedIn. Si vous souhaitez seulement lire et visualiser le contenu du cours, vous pouvez accéder gratuitement au cours en tant qu'auditeur libre.

D'autres questions ? Visitez le Centre d'Aide pour les Etudiants.