Acerca de este Curso
12,042 vistas recientes

100 % en línea

Comienza de inmediato y aprende a tu propio ritmo.

Fechas límite flexibles

Restablece las fechas límite en función de tus horarios.

Aprox. 22 horas para completar

Sugerido: 5 hours/week...

Ruso (Russian)

Subtítulos: Ruso (Russian)

100 % en línea

Comienza de inmediato y aprende a tu propio ritmo.

Fechas límite flexibles

Restablece las fechas límite en función de tus horarios.

Aprox. 22 horas para completar

Sugerido: 5 hours/week...

Ruso (Russian)

Subtítulos: Ruso (Russian)

Programa - Qué aprenderás en este curso

Semana
1
3 horas para completar

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

В первую неделю курса мы познакомимся с понятием графа, научимся отличать граф от его изображения, поговорим о разных видах графов. Мы вспомним, с чего началась теория графов, научимся представлять в виде графа структуру интернета. Мы обсудим такие важные понятия, как маршруты в графах, степень вершины, связность, а также начнем говорить про важный класс графов - деревья.

...
17 videos (Total 104 minutos), 6 readings, 1 quiz
17 videos
МФТИ1m
Примеры графов. Граф и его изображение10m
Ориентированные графы4m
Кёнигсбергские мосты. Мультиграфы5m
Граф интернета. Псевдографы4m
Определение графа5m
Маршруты в графах10m
Связность, подграфы7m
Степень вершины3m
Деревья, эквивалентные определения дерева5m
Знакомства6m
Число мультиграфов4m
Путь в графе5m
Перенумерация цикла8m
Последовательности степеней9m
Замкнутый маршрут9m
6 lecturas
МФТИ10m
Теоретический материал к семинару10m
Задачи к семинару10m
Решение задач10m
Дополнительные задачи к неделе 110m
Конспект лекции 110m
1 ejercicio de práctica
Задание к неделе 118m
Semana
2
3 horas para completar

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

На этой неделе мы научимся определять деревья четырьмя различными способами, и поговорим о том, как правильно раскрашивать географические карты. Мы вспомним знаменитую теорему о четырех красках, а также критерий Куратовского о том, как определить, можно ли нарисовать данный граф на плоскости без пересечений ребер. В последней части лекции мы обсудим формулу Эйлера для планарных графов и некоторые из её множественных следствий.

...
17 videos (Total 147 minutos), 4 readings, 1 quiz
17 videos
Доказательство второй импликации13m
Доказательство третьей импликации9m
Доказательство четвертой импликации6m
Планарность. Гипотеза о четырех красках10m
Примеры непланарных графов5m
Критерий Куратовского7m
Плоские графы, грани и теорема Жордана8m
Формула Эйлера10m
Следствие для числа ребер13m
Хроматическое число планарных графов8m
Доказательство оценки хроматического числа13m
Минимальное число ребер2m
Число пересечений в полном графе2m
Число ребер в планарном графе и формула Эйлера4m
Характеризация двудольных графов15m
Двудольные планарные графы9m
4 lecturas
Теоретический материал к семинару10m
Задачи к семинару10m
Решения задач10m
Дополнительные задачи к неделе 210m
1 ejercicio de práctica
Задание к неделе 218m
Semana
3
3 horas para completar

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

На этой неделе мы перечислим все деревья. Для этого нам потребуется перенять опыт древних по подсчету баранов (или козлов). Не остановившись на этом, перечислим и все леса и унициклические графы. Затем мы вернемся к задаче о Кёнигсбергских мостах и получим полное решение этого вопроса.

...
15 videos (Total 115 minutos), 4 readings, 1 quiz
15 videos
Доказательство формулы. Кодирование деревьев5m
Построение кодов Прюфера5m
Взаимно однозначное соответствие кодов и деревьев. Декодирование8m
Формула для числа унициклических графов6m
Доказательство формулы14m
Эйлеровы циклы5m
Критерий эйлеровости3m
Первая часть доказательства критерия11m
Вторая часть доказательства критерия12m
Центр дерева6m
Деревья с заданной последовательностью степеней11m
Код Прюфера из различных чисел3m
Число неизоморфных деревьев6m
Ориентация графа4m
4 lecturas
Теоретический материал к семинару10m
Задачи к семинару10m
Решения задач10m
Дополнительные задачи к неделе 310m
1 ejercicio de práctica
Задание к неделе 316m
Semana
4
4 horas para completar

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

На этой неделе мы продолжим обсуждать циклы, проходящие через весь граф. На этот раз мы поговорим про циклы, проходящие через все вершины графа. В отличие от эйлеровых циклов, здесь нет необходимого и достаточного критерия наличия такого цикла. Есть только достаточные условия, и мы обсудим два таких условия, довольно разных по своей природе. По пути мы обсудим такие важные характеристики графа, как независимое число и k-связность. В качестве дополнения, мы расскажем об одном очень интересном классе графов, для которого один из критериев работает, а другой - нет.

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

20%

consiguió un beneficio tangible en su carrera profesional gracias a este curso

25%

consiguió un aumento de sueldo o ascenso

Principales revisiones sobre Теория графов

por DDOct 30th 2016

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

por DMNov 8th 2016

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

Instructores

Avatar

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

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

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

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

Acerca de Instituto de Física y Tecnología de Moscú

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

Preguntas Frecuentes

  • Una vez que te inscribes para obtener un Certificado, tendrás acceso a todos los videos, cuestionarios y tareas de programación (si corresponde). Las tareas calificadas por compañeros solo pueden enviarse y revisarse una vez que haya comenzado tu sesión. Si eliges explorar el curso sin comprarlo, es posible que no puedas acceder a determinadas tareas.

  • Cuando compras un Certificado, obtienes acceso a todos los materiales del curso, incluidas las tareas calificadas. Una vez que completes el curso, se añadirá tu Certificado electrónico a la página Logros. Desde allí, puedes imprimir tu Certificado o añadirlo a tu perfil de LinkedIn. Si solo quieres leer y visualizar el contenido del curso, puedes participar del curso como oyente sin costo.

¿Tienes más preguntas? Visita el Centro de Ayuda al Alumno.