关于此课程： Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются "планарными". Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день. Граф как математический объект оказался полезным во многих теоретических и практических задачах. Наверное, дело в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. Этот курс служит введением в современную теорию графов. Мы, конечно, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов. Материал изложен с самых основ и на доступном языке. Целью этого курса является не только познакомить вас с вопросами и методами теории графов, но и развить у неподготовленных слушателей культуру математического мышления. Поэтому курс доступен широкому кругу слушателей. Для освоения материала будет достаточно знания математики на хорошем школьном уровне и базовых знаний комбинаторики. Курс состоит из 7 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов.
制作方： 莫斯科物理科学与技术学院
教学方： Андрей Райгородский, профессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
教学方： Андрей Купавский, кандидат физико-математических наук
Кафедра дискретной математики ФИВТ МФТИ
| 语言 | Russian |
| 如何通过 | 通过所有计分作业以完成课程。 |
| 用户评分 |
授课大纲
第 1 周
Введение. Базовые понятия теории графов
В первую неделю курса мы познакомимся с понятием графа, научимся отличать граф от его изображения, поговорим о разных видах графов. Мы вспомним, с чего началась теория графов, научимся представлять в виде графа структуру интернета. Мы обсудим такие важные понятия, как маршруты в графах, степень вершины, связность, а также начнем говорить про важный класс графов - деревья.
17 视频, 6 阅读材料
- 视频: Введение
- 视频: МФТИ
- Reading: МФТИ
- 视频: Примеры графов. Граф и его изображение
- 视频: Ориентированные графы
- 视频: Кёнигсбергские мосты. Мультиграфы
- 视频: Граф интернета. Псевдографы
- 视频: Определение графа
- 视频: Маршруты в графах
- 视频: Связность, подграфы
- 视频: Степень вершины
- 视频: Деревья, эквивалентные определения дерева
- Reading: Теоретический материал к семинару
- Reading: Задачи к семинару
- 视频: Знакомства
- 视频: Число мультиграфов
- 视频: Путь в графе
- 视频: Перенумерация цикла
- 视频: Последовательности степеней
- 视频: Замкнутый маршрут
- Reading: Решение задач
- Reading: Дополнительные задачи к неделе 1
- Reading: Конспект лекции 1
已评分: Задание к неделе 1
第 2 周
Эквивалентные определения дерева. Планарные графы
На этой неделе мы научимся определять деревья четырьмя различными способами, и поговорим о том, как правильно раскрашивать географические карты. Мы вспомним знаменитую теорему о четырех красках, а также критерий Куратовского о том, как определить, можно ли нарисовать данный граф на плоскости без пересечений ребер. В последней части лекции мы обсудим формулу Эйлера для планарных графов и некоторые из её множественных следствий.
17 视频, 4 阅读材料
- 视频: Формулировка теоремы. Доказательство первой импликации
- 视频: Доказательство второй импликации
- 视频: Доказательство третьей импликации
- 视频: Доказательство четвертой импликации
- 视频: Планарность. Гипотеза о четырех красках
- 视频: Примеры непланарных графов
- 视频: Критерий Куратовского
- 视频: Плоские графы, грани и теорема Жордана
- 视频: Формула Эйлера
- 视频: Следствие для числа ребер
- 视频: Хроматическое число планарных графов
- 视频: Доказательство оценки хроматического числа
- Reading: Теоретический материал к семинару
- Reading: Задачи к семинару
- 视频: Минимальное число ребер
- 视频: Число пересечений в полном графе
- 视频: Число ребер в планарном графе и формула Эйлера
- 视频: Характеризация двудольных графов
- 视频: Двудольные планарные графы
- Reading: Решения задач
- Reading: Дополнительные задачи к неделе 2
已评分: Задание к неделе 2
第 3 周
Формула Кэли. Унициклические графы. Эйлеровы циклы
На этой неделе мы перечислим все деревья. Для этого нам потребуется перенять опыт древних по подсчету баранов (или козлов). Не остановившись на этом, перечислим и все леса и унициклические графы. Затем мы вернемся к задаче о Кёнигсбергских мостах и получим полное решение этого вопроса.
15 视频, 4 阅读材料
- 视频: Число деревьев
- 视频: Доказательство формулы. Кодирование деревьев
- 视频: Построение кодов Прюфера
- 视频: Взаимно однозначное соответствие кодов и деревьев. Декодирование
- 视频: Формула для числа унициклических графов
- 视频: Доказательство формулы
- 视频: Эйлеровы циклы
- 视频: Критерий эйлеровости
- 视频: Первая часть доказательства критерия
- 视频: Вторая часть доказательства критерия
- Reading: Теоретический материал к семинару
- Reading: Задачи к семинару
- 视频: Центр дерева
- 视频: Деревья с заданной последовательностью степеней
- 视频: Код Прюфера из различных чисел
- 视频: Число неизоморфных деревьев
- 视频: Ориентация графа
- Reading: Решения задач
- Reading: Дополнительные задачи к неделе 3
已评分: Задание к неделе 3
第 4 周
Гамильтоновы циклы
На этой неделе мы продолжим обсуждать циклы, проходящие через весь граф. На этот раз мы поговорим про циклы, проходящие через все вершины графа. В отличие от эйлеровых циклов, здесь нет необходимого и достаточного критерия наличия такого цикла. Есть только достаточные условия, и мы обсудим два таких условия, довольно разных по своей природе. По пути мы обсудим такие важные характеристики графа, как независимое число и k-связность. В качестве дополнения, мы расскажем об одном очень интересном классе графов, для которого один из критериев работает, а другой - нет.
21 视频, 5 阅读材料
- 视频: Гамильтоновы циклы, теорема Дирака
- 视频: Множества соседей концов максимального пути
- 视频: Завершение доказательства теоремы Дирака
- 视频: Независимые множества
- 视频: Вершинная связность. Критерий Хватала
- 视频: Доказательство. В графе есть циклы
- 视频: Подграф без максимального цикла
- 视频: Соседи связной компоненты
- 视频: Соседи компоненты и максимальный цикл
- 视频: Число соседей больше связности
- 视频: Завершение доказательства
- Reading: Пример гамильтонова графа
- Reading: Теоретический материал к семинару
- Reading: Задачи к семинару
- 视频: Число гамильтоновых циклов в полном двудольном графе
- 视频: Число независимости, связность
- 视频: Непересекающиеся гамильтоновы циклы
- Reading: Решения задач
- Reading: Дополнительные задачи к неделе 4
- 视频: Сравнение двух признаков гамильтоновости на конкретном графе. Определение графа
- 视频: Работает ли признак Дирака?
- 视频: Признак Хватала. Оценка связности через общих соседей
- 视频: Число общих соседей
- 视频: Примеры независимых множеств, теорема о числе независимости
- 视频: Доказательство теоремы
- 视频: Связь с теорией кодирования
已评分: Задание к неделе 4
第 5 周
Паросочетания. Теоремы Холла и Кёнига
На этой неделе мы поговорим про паросочетания. Мы узнаем, что нужно, чтобы переженить всех юношей и девушек по любви. Мы обсудим две классических теоремы, у одной из которых очень изящное доказательство по индукции, а у другой не менее изящное доказательство алгоритмическое. А на семинаре мы узнаем, что эти две теоремы эквивалентны.
15 视频, 4 阅读材料
- 视频: Задача о свадьбах. Паросочетания
- 视频: Необходимое условие существования паросочетания. Теорема Холла
- 视频: Доказательство теоремы Холла. Два случая
- 视频: Разбор случая 1
- 视频: Разбор случая 2
- 视频: Вершинное покрытие, теорема Кёнига
- 视频: Первая часть доказательства. Чередующиеся цепи
- 视频: Вторая часть доказательства. Разбиение множества вершин
- 视频: Третья часть доказательства. Построение вершинного покрытия
- 视频: Завершение доказательства. Вершинное покрытие работает
- Reading: Теоретический материал к семинару
- Reading: Задачи к семинару
- 视频: Теорема Холла из теоремы Кёнига
- 视频: Теорема Кёнига из теоремы Холла
- 视频: Паросочетания и степени вершин
- 视频: Паросочетания в деревьях
- 视频: К-регулярный двудольный граф
- Reading: Решения задач
- Reading: Дополнительные задачи к неделе 5
已评分: Задание к неделе 5
第 6 周
Экстремальная теория графов. Теорема Турана
На этой неделе мы начнем разговор про экстремальную теорию графов, которая ставит вопросы про то, с какого момента графы начинают обладать тем или иным свойством. В частности, мы выясним, сколько ребер должен иметь граф, чтобы он гарантированно содержал треугольник. В конце лекции мы узнаем, что графы на плоскости в экстремальных задачах ведут себя несколько по-другому, нежели графы абстрактные.
13 视频, 4 阅读材料
- 视频: Число независимости, кликовое число
- 视频: Теорема Турана
- 视频: Доказательство теоремы Турана
- 视频: Пример графа, на котором оценка Турана достигается
- 视频: Теорема Турана в терминах кликового числа
- 视频: Задача про графы на плоскости
- 视频: Решение задачи
- Reading: Теоретический материал к семинару
- Reading: Задачи к семинару
- 视频: Двудольный подграф
- 视频: Вершинное покрытие для графа без треугольников
- 视频: Граф без четных циклов
- 视频: Хроматическое число и число независимости
- 视频: Хроматическое число и максимальная степень
- 视频: Хроматическое число графа и его дополнения
- Reading: Решения задач
- Reading: Дополнительные задачи к неделе 6
已评分: Задание к неделе 6
第 7 周
Теория Рамсея
На заключительной лекции мы поговорим про теорию Рамсея. Вы узнаете много нового о знакомствах, о том, сколько раз можно в одном доказательстве применить принцип Дирихле и о том, что доказать существование графа и привести пример такого графа - это зачастую совсем разные по сложности задачи.
20 视频, 4 阅读材料
- 视频: Теорема про знакомства среди шести человек
- 视频: Начало доказательства. Применение принципа Дирихле
- 视频: Завершение доказательства
- 视频: Формулировка в терминах независимых множеств и раскрасок
- 视频: Пяти вершин недостаточно
- 视频: Определение чисел Рамсея
- 视频: Значения R(s,t) для малых s
- 视频: Верхняя оценка чисел Рамсея с помощью рекурсии
- 视频: Доказательство. Принцип Дирихле
- 视频: Завершение доказательства
- 视频: Численные верхние оценки чисел Рамсея
- 视频: Нижняя оценка числа Рамсея. Что требуется доказать?
- 视频: Подсчет графов с большими полными подграфами
- 视频: Вычисления. Завершение доказательства теоремы
- 视频: Обсуждение нижних оценок
- Reading: Теоретический материал к семинару
- Reading: Задачи к семинару
- 视频: Число Рамсея для звезды
- 视频: Число Рамсея для дерева и полного графа
- 视频: Раскраска плоскости
- 视频: Монотонные последовательности
- 视频: Пути или звезды
- Reading: Решение задач
- Reading: Дополнительные задачи к неделе 7
已评分: Задание к неделе 7
第 8 周
Экзамен
Заключительная работа по материалу всего курса
已评分: Экзамен. Один граф
常见问题解答
运作方式
Coursework
Each course is like an interactive textbook, featuring pre-recorded videos, quizzes and projects.
Help from Your Peers
Connect with thousands of other learners and debate ideas, discuss course material, and get help mastering concepts.
Certificates
Earn official recognition for your work, and share your success with friends, colleagues, and employers.
制作方
莫斯科物理科学与技术学院
Московский физико-технический институт (неофициально известный как МФТИ или Физтех) является одним из самых престижных в мире учебных и научно-исследовательских институтов. Он готовит высококвалифицированных специалистов в области теоретической и прикладной физики, прикладной математики, информатики, биотехнологии и смежных дисциплин. Физтех был основан в 1951 году Нобелевской премии лауреатами Петром Капицей, Николаем Семеновым, Львом Ландау и Сергеем Христиановичем. Основой образования в МФТИ является уникальная «система Физтеха»: кропотливое воспитание и отбор самых талантливых абитуриентов, фундаментальное образование высшего класса и раннее вовлечение студентов в реальную научно-исследовательскую работу. Среди выпускников МФТИ есть Нобелевские лауреаты, основатели всемирно известных компаний, известные космонавты, изобретатели, инженеры.
评分和审阅
Concise intro to graph theory. Very good
Great!
Интересно - но сложно :))
Очень хорошее введение в теорию графов, которое предполагает владение только основами комбинаторики. Подача и подбор лекционного материала выше всяких похвал. Этот курс не предполагает получения глубоких знаний в этой области, однако для быстрого обучения базовым навыкам вполне подойдет. Разбору задач уделяется значительно меньше времени, и овладеть способностью решать задачи по заданным материалам достаточно сложно, но его вполне хватает для закрепления пройденного материала. В конечном счете все зависит от ваших целей.