About this Course
4.9
340개의 평가
41개의 리뷰

100% 온라인

지금 바로 시작해 나만의 일정에 따라 학습을 진행하세요.

탄력적인 마감일

일정에 따라 마감일을 재설정합니다.

완료하는 데 약 22시간 필요

권장: 5 hours/week...

러시아어

자막: 러시아어

100% 온라인

지금 바로 시작해 나만의 일정에 따라 학습을 진행하세요.

탄력적인 마감일

일정에 따라 마감일을 재설정합니다.

완료하는 데 약 22시간 필요

권장: 5 hours/week...

러시아어

자막: 러시아어

강의 계획 - 이 강좌에서 배울 내용

1
완료하는 데 3시간 필요

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

В первую неделю курса мы познакомимся с понятием графа, научимся отличать граф от его изображения, поговорим о разных видах графов. Мы вспомним, с чего началась теория графов, научимся представлять в виде графа структуру интернета. Мы обсудим такие важные понятия, как маршруты в графах, степень вершины, связность, а также начнем говорить про важный класс графов - деревья....
17 videos (Total 104 min), 6 readings, 1 quiz
17개의 동영상
МФТИ1m
Примеры графов. Граф и его изображение10m
Ориентированные графы4m
Кёнигсбергские мосты. Мультиграфы5m
Граф интернета. Псевдографы4m
Определение графа5m
Маршруты в графах10m
Связность, подграфы7m
Степень вершины3m
Деревья, эквивалентные определения дерева5m
Знакомства6m
Число мультиграфов4m
Путь в графе5m
Перенумерация цикла8m
Последовательности степеней9m
Замкнутый маршрут9m
6개의 읽기 자료
МФТИ10m
Теоретический материал к семинару10m
Задачи к семинару10m
Решение задач10m
Дополнительные задачи к неделе 110m
Конспект лекции 110m
1개 연습문제
Задание к неделе 118m
2
완료하는 데 3시간 필요

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

На этой неделе мы научимся определять деревья четырьмя различными способами, и поговорим о том, как правильно раскрашивать географические карты. Мы вспомним знаменитую теорему о четырех красках, а также критерий Куратовского о том, как определить, можно ли нарисовать данный граф на плоскости без пересечений ребер. В последней части лекции мы обсудим формулу Эйлера для планарных графов и некоторые из её множественных следствий....
17 videos (Total 147 min), 4 readings, 1 quiz
17개의 동영상
Доказательство второй импликации13m
Доказательство третьей импликации9m
Доказательство четвертой импликации6m
Планарность. Гипотеза о четырех красках10m
Примеры непланарных графов5m
Критерий Куратовского7m
Плоские графы, грани и теорема Жордана8m
Формула Эйлера10m
Следствие для числа ребер13m
Хроматическое число планарных графов8m
Доказательство оценки хроматического числа13m
Минимальное число ребер2m
Число пересечений в полном графе2m
Число ребер в планарном графе и формула Эйлера4m
Характеризация двудольных графов15m
Двудольные планарные графы9m
4개의 읽기 자료
Теоретический материал к семинару10m
Задачи к семинару10m
Решения задач10m
Дополнительные задачи к неделе 210m
1개 연습문제
Задание к неделе 218m
3
완료하는 데 3시간 필요

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

На этой неделе мы перечислим все деревья. Для этого нам потребуется перенять опыт древних по подсчету баранов (или козлов). Не остановившись на этом, перечислим и все леса и унициклические графы. Затем мы вернемся к задаче о Кёнигсбергских мостах и получим полное решение этого вопроса....
15 videos (Total 115 min), 4 readings, 1 quiz
15개의 동영상
Доказательство формулы. Кодирование деревьев5m
Построение кодов Прюфера5m
Взаимно однозначное соответствие кодов и деревьев. Декодирование8m
Формула для числа унициклических графов6m
Доказательство формулы14m
Эйлеровы циклы5m
Критерий эйлеровости3m
Первая часть доказательства критерия11m
Вторая часть доказательства критерия12m
Центр дерева6m
Деревья с заданной последовательностью степеней11m
Код Прюфера из различных чисел3m
Число неизоморфных деревьев6m
Ориентация графа4m
4개의 읽기 자료
Теоретический материал к семинару10m
Задачи к семинару10m
Решения задач10m
Дополнительные задачи к неделе 310m
1개 연습문제
Задание к неделе 316m
4
완료하는 데 4시간 필요

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

На этой неделе мы продолжим обсуждать циклы, проходящие через весь граф. На этот раз мы поговорим про циклы, проходящие через все вершины графа. В отличие от эйлеровых циклов, здесь нет необходимого и достаточного критерия наличия такого цикла. Есть только достаточные условия, и мы обсудим два таких условия, довольно разных по своей природе. По пути мы обсудим такие важные характеристики графа, как независимое число и k-связность. В качестве дополнения, мы расскажем об одном очень интересном классе графов, для которого один из критериев работает, а другой - нет....
21 videos (Total 166 min), 6 readings, 1 quiz
21개의 동영상
Множества соседей концов максимального пути9m
Завершение доказательства теоремы Дирака9m
Независимые множества5m
Вершинная связность. Критерий Хватала4m
Доказательство. В графе есть циклы6m
Подграф без максимального цикла5m
Соседи связной компоненты5m
Соседи компоненты и максимальный цикл7m
Число соседей больше связности7m
Завершение доказательства9m
Число гамильтоновых циклов в полном двудольном графе3m
Число независимости, связность10m
Непересекающиеся гамильтоновы циклы12m
Сравнение двух признаков гамильтоновости на конкретном графе. Определение графа6m
Работает ли признак Дирака?6m
Признак Хватала. Оценка связности через общих соседей6m
Число общих соседей8m
Примеры независимых множеств, теорема о числе независимости11m
Доказательство теоремы10m
Связь с теорией кодирования6m
6개의 읽기 자료
Пример гамильтонова графа10m
Теоретический материал к семинару10m
Задачи к семинару10m
Комментарий к лекции10m
Решения задач10m
Дополнительные задачи к неделе 410m
1개 연습문제
Задание к неделе 418m
5
완료하는 데 3시간 필요

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

На этой неделе мы поговорим про паросочетания. Мы узнаем, что нужно, чтобы переженить всех юношей и девушек по любви. Мы обсудим две классических теоремы, у одной из которых очень изящное доказательство по индукции, а у другой не менее изящное доказательство алгоритмическое. А на семинаре мы узнаем, что эти две теоремы эквивалентны....
15 videos (Total 150 min), 4 readings, 1 quiz
15개의 동영상
Необходимое условие существования паросочетания. Теорема Холла8m
Доказательство теоремы Холла. Два случая6m
Разбор случая 110m
Разбор случая 212m
Вершинное покрытие, теорема Кёнига6m
Первая часть доказательства. Чередующиеся цепи12m
Вторая часть доказательства. Разбиение множества вершин8m
Третья часть доказательства. Построение вершинного покрытия10m
Завершение доказательства. Вершинное покрытие работает10m
Теорема Холла из теоремы Кёнига9m
Теорема Кёнига из теоремы Холла11m
Паросочетания и степени вершин10m
Паросочетания в деревьях5m
К-регулярный двудольный граф15m
4개의 읽기 자료
Теоретический материал к семинару10m
Задачи к семинару10m
Решения задач10m
Дополнительные задачи к неделе 510m
1개 연습문제
Задание к неделе 518m
6
완료하는 데 3시간 필요

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

На этой неделе мы начнем разговор про экстремальную теорию графов, которая ставит вопросы про то, с какого момента графы начинают обладать тем или иным свойством. В частности, мы выясним, сколько ребер должен иметь граф, чтобы он гарантированно содержал треугольник. В конце лекции мы узнаем, что графы на плоскости в экстремальных задачах ведут себя несколько по-другому, нежели графы абстрактные. ...
13 videos (Total 123 min), 4 readings, 1 quiz
13개의 동영상
Теорема Турана6m
Доказательство теоремы Турана16m
Пример графа, на котором оценка Турана достигается7m
Теорема Турана в терминах кликового числа7m
Задача про графы на плоскости9m
Решение задачи15m
Двудольный подграф13m
Вершинное покрытие для графа без треугольников4m
Граф без четных циклов10m
Хроматическое число и число независимости6m
Хроматическое число и максимальная степень7m
Хроматическое число графа и его дополнения11m
4개의 읽기 자료
Теоретический материал к семинару10m
Задачи к семинару10m
Решения задач10m
Дополнительные задачи к неделе 610m
1개 연습문제
Задание к неделе 618m
7
완료하는 데 3시간 필요

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

На заключительной лекции мы поговорим про теорию Рамсея. Вы узнаете много нового о знакомствах, о том, сколько раз можно в одном доказательстве применить принцип Дирихле и о том, что доказать существование графа и привести пример такого графа - это зачастую совсем разные по сложности задачи....
20 videos (Total 148 min), 4 readings, 1 quiz
20개의 동영상
Начало доказательства. Применение принципа Дирихле4m
Завершение доказательства6m
Формулировка в терминах независимых множеств и раскрасок5m
Пяти вершин недостаточно2m
Определение чисел Рамсея4m
Значения R(s,t) для малых s13m
Верхняя оценка чисел Рамсея с помощью рекурсии2m
Доказательство. Принцип Дирихле7m
Завершение доказательства10m
Численные верхние оценки чисел Рамсея12m
Нижняя оценка числа Рамсея. Что требуется доказать?3m
Подсчет графов с большими полными подграфами12m
Вычисления. Завершение доказательства теоремы4m
Обсуждение нижних оценок4m
Число Рамсея для звезды5m
Число Рамсея для дерева и полного графа13m
Раскраска плоскости6m
Монотонные последовательности9m
Пути или звезды13m
4개의 읽기 자료
Теоретический материал к семинару10m
Задачи к семинару10m
Решение задач10m
Дополнительные задачи к неделе 710m
1개 연습문제
Задание к неделе 714m
8
완료하는 데 18분 필요

Экзамен

Заключительная работа по материалу всего курса...
1 quiz
1개 연습문제
Экзамен. Один граф18m
4.9
41개의 리뷰Chevron Right

20%

이 강좌를 통해 확실한 경력상 이점 얻기

25%

급여 인상 또는 승진하기

최상위 리뷰

대학: DDOct 30th 2016

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

대학: DMNov 8th 2016

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

강사

Avatar

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

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

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

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

모스크바 물리 기술원 정보

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

자주 묻는 질문

  • 강좌에 등록하면 바로 모든 비디오, 테스트 및 프로그래밍 과제(해당하는 경우)에 접근할 수 있습니다. 상호 첨삭 과제는 이 세션이 시작된 경우에만 제출하고 검토할 수 있습니다. 강좌를 구매하지 않고 살펴보기만 하면 특정 과제에 접근하지 못할 수 있습니다.

  • 수료증을 구매하면 성적 평가 과제를 포함한 모든 강좌 자료에 접근할 수 있습니다. 강좌를 완료하면 전자 수료증이 성취도 페이지에 추가되며, 해당 페이지에서 수료증을 인쇄하거나 LinkedIn 프로필에 수료증을 추가할 수 있습니다. 강좌 콘텐츠만 읽고 살펴보려면 해당 강좌를 무료로 청강할 수 있습니다.

궁금한 점이 더 있으신가요? 학습자 도움말 센터를 방문해 보세요.