À propos de ce cours
32,210 consultations récentes

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. 23 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. 23 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

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

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
4.9
43 avisChevron Right

20%

ont bénéficié d'un avantage concret dans leur carrières grâce à ce cours

25%

a obtenu une augmentation de salaire ou une promotion

Meilleurs avis pour Теория графов

par DDOct 30th 2016

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

par DMNov 8th 2016

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

Enseignants

Avatar

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

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

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

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

À propos de Institut de physique et de technologie de Moscou

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

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.