About this Course
4.9
278 ratings
33 reviews
Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются "планарными". Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день. Граф как математический объект оказался полезным во многих теоретических и практических задачах. Наверное, дело в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. Этот курс служит введением в современную теорию графов. Мы, конечно, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов. Материал изложен с самых основ и на доступном языке. Целью этого курса является не только познакомить вас с вопросами и методами теории графов, но и развить у неподготовленных слушателей культуру математического мышления. Поэтому курс доступен широкому кругу слушателей. Для освоения материала будет достаточно знания математики на хорошем школьном уровне и базовых знаний комбинаторики. Курс состоит из 7 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов....
Globe

100% online courses

Start instantly and learn at your own schedule.
Calendar

Flexible deadlines

Reset deadlines in accordance to your schedule.
Clock

Suggested: 5 hours/week

Approx. 24 hours to complete
Comment Dots

Russian

Subtitles: Russian
Globe

100% online courses

Start instantly and learn at your own schedule.
Calendar

Flexible deadlines

Reset deadlines in accordance to your schedule.
Clock

Suggested: 5 hours/week

Approx. 24 hours to complete
Comment Dots

Russian

Subtitles: Russian

Syllabus - What you will learn from this course

1

Section
Clock
3 hours to complete

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

В первую неделю курса мы познакомимся с понятием графа, научимся отличать граф от его изображения, поговорим о разных видах графов. Мы вспомним, с чего началась теория графов, научимся представлять в виде графа структуру интернета. Мы обсудим такие важные понятия, как маршруты в графах, степень вершины, связность, а также начнем говорить про важный класс графов - деревья....
Reading
17 videos (Total 104 min), 6 readings, 1 quiz
Video17 videos
МФТИ1m
Примеры графов. Граф и его изображение10m
Ориентированные графы4m
Кёнигсбергские мосты. Мультиграфы5m
Граф интернета. Псевдографы4m
Определение графа5m
Маршруты в графах10m
Связность, подграфы7m
Степень вершины3m
Деревья, эквивалентные определения дерева5m
Знакомства6m
Число мультиграфов4m
Путь в графе5m
Перенумерация цикла8m
Последовательности степеней9m
Замкнутый маршрут9m
Reading6 readings
МФТИ10m
Теоретический материал к семинару10m
Задачи к семинару10m
Решение задач10m
Дополнительные задачи к неделе 110m
Конспект лекции 110m
Quiz1 practice exercise
Задание к неделе 118m

2

Section
Clock
3 hours to complete

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

На этой неделе мы научимся определять деревья четырьмя различными способами, и поговорим о том, как правильно раскрашивать географические карты. Мы вспомним знаменитую теорему о четырех красках, а также критерий Куратовского о том, как определить, можно ли нарисовать данный граф на плоскости без пересечений ребер. В последней части лекции мы обсудим формулу Эйлера для планарных графов и некоторые из её множественных следствий....
Reading
17 videos (Total 147 min), 4 readings, 1 quiz
Video17 videos
Доказательство второй импликации13m
Доказательство третьей импликации9m
Доказательство четвертой импликации6m
Планарность. Гипотеза о четырех красках10m
Примеры непланарных графов5m
Критерий Куратовского7m
Плоские графы, грани и теорема Жордана8m
Формула Эйлера10m
Следствие для числа ребер13m
Хроматическое число планарных графов8m
Доказательство оценки хроматического числа13m
Минимальное число ребер2m
Число пересечений в полном графе2m
Число ребер в планарном графе и формула Эйлера4m
Характеризация двудольных графов15m
Двудольные планарные графы9m
Reading4 readings
Теоретический материал к семинару10m
Задачи к семинару10m
Решения задач10m
Дополнительные задачи к неделе 210m
Quiz1 practice exercise
Задание к неделе 218m

3

Section
Clock
3 hours to complete

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

На этой неделе мы перечислим все деревья. Для этого нам потребуется перенять опыт древних по подсчету баранов (или козлов). Не остановившись на этом, перечислим и все леса и унициклические графы. Затем мы вернемся к задаче о Кёнигсбергских мостах и получим полное решение этого вопроса....
Reading
15 videos (Total 115 min), 4 readings, 1 quiz
Video15 videos
Доказательство формулы. Кодирование деревьев5m
Построение кодов Прюфера5m
Взаимно однозначное соответствие кодов и деревьев. Декодирование8m
Формула для числа унициклических графов6m
Доказательство формулы14m
Эйлеровы циклы5m
Критерий эйлеровости3m
Первая часть доказательства критерия11m
Вторая часть доказательства критерия12m
Центр дерева6m
Деревья с заданной последовательностью степеней11m
Код Прюфера из различных чисел3m
Число неизоморфных деревьев6m
Ориентация графа4m
Reading4 readings
Теоретический материал к семинару10m
Задачи к семинару10m
Решения задач10m
Дополнительные задачи к неделе 310m
Quiz1 practice exercise
Задание к неделе 316m

4

Section
Clock
4 hours to complete

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

На этой неделе мы продолжим обсуждать циклы, проходящие через весь граф. На этот раз мы поговорим про циклы, проходящие через все вершины графа. В отличие от эйлеровых циклов, здесь нет необходимого и достаточного критерия наличия такого цикла. Есть только достаточные условия, и мы обсудим два таких условия, довольно разных по своей природе. По пути мы обсудим такие важные характеристики графа, как независимое число и k-связность. В качестве дополнения, мы расскажем об одном очень интересном классе графов, для которого один из критериев работает, а другой - нет....
Reading
21 videos (Total 166 min), 6 readings, 1 quiz
Video21 videos
Множества соседей концов максимального пути9m
Завершение доказательства теоремы Дирака9m
Независимые множества5m
Вершинная связность. Критерий Хватала4m
Доказательство. В графе есть циклы6m
Подграф без максимального цикла5m
Соседи связной компоненты5m
Соседи компоненты и максимальный цикл7m
Число соседей больше связности7m
Завершение доказательства9m
Число гамильтоновых циклов в полном двудольном графе3m
Число независимости, связность10m
Непересекающиеся гамильтоновы циклы12m
Сравнение двух признаков гамильтоновости на конкретном графе. Определение графа6m
Работает ли признак Дирака?6m
Признак Хватала. Оценка связности через общих соседей6m
Число общих соседей8m
Примеры независимых множеств, теорема о числе независимости11m
Доказательство теоремы10m
Связь с теорией кодирования6m
Reading6 readings
Пример гамильтонова графа10m
Теоретический материал к семинару10m
Задачи к семинару10m
Комментарий к лекции10m
Решения задач10m
Дополнительные задачи к неделе 410m
Quiz1 practice exercise
Задание к неделе 418m

Instructors

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

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

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

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

About Moscow Institute of Physics and Technology

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

Frequently Asked Questions

  • Once you enroll for a Certificate, you’ll have access to all videos, quizzes, and programming assignments (if applicable). Peer review assignments can only be submitted and reviewed once your session has begun. If you choose to explore the course without purchasing, you may not be able to access certain assignments.

  • When you purchase a Certificate you get access to all course materials, including graded assignments. Upon completing the course, your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile. If you only want to read and view the course content, you can audit the course for free.

More questions? Visit the Learner Help Center.