- From www.coursera.org
Теория графов
- Self-paced
- Free Access
- Fee-based Certificate
- 8 Sequences
- Introductive Level
Course details
Syllabus
- Week 1 - Введение. Базовые понятия теории графов
В первую неделю курса мы познакомимся с понятием графа, научимся отличать граф от его изображения, поговорим о разных видах графов. Мы вспомним, с чего началась теория графов, научимся представлять в виде графа структуру интернета. Мы обсудим такие важные поня... - Week 2 - Эквивалентные определения дерева. Планарные графы
На этой неделе мы научимся определять деревья четырьмя различными способами, и поговорим о том, как правильно раскрашивать географические карты. Мы вспомним знаменитую теорему о четырех красках, а также критерий Куратовского о том, как определить, можно ли на... - Week 3 - Формула Кэли. Унициклические графы. Эйлеровы циклы
На этой неделе мы перечислим все деревья. Для этого нам потребуется перенять опыт древних по подсчету баранов (или козлов). Не остановившись на этом, перечислим и все леса и унициклические графы. Затем мы вернемся к задаче о Кёнигсбергских мостах и получим пол... - Week 4 - Гамильтоновы циклы
На этой неделе мы продолжим обсуждать циклы, проходящие через весь граф. На этот раз мы поговорим про циклы, проходящие через все вершины графа. В отличие от эйлеровых циклов, здесь нет необходимого и достаточного критерия наличия такого цикла. Есть только дос... - Week 5 - Паросочетания. Теоремы Холла и Кёнига
На этой неделе мы поговорим про паросочетания. Мы узнаем, что нужно, чтобы переженить всех юношей и девушек по любви. Мы обсудим две классических теоремы, у одной из которых очень изящное доказательство по индукции, а у другой не менее изящное доказательство а... - Week 6 - Экстремальная теория графов. Теорема Турана
На этой неделе мы начнем разговор про экстремальную теорию графов, которая ставит вопросы про то, с какого момента графы начинают обладать тем или иным свойством. В частности, мы выясним, сколько ребер должен иметь граф, чтобы он гарантированно содержал треуго... - Week 7 - Теория Рамсея
На заключительной лекции мы поговорим про теорию Рамсея. Вы узнаете много нового о знакомствах, о том, сколько раз можно в одном доказательстве применить принцип Дирихле и о том, что доказать существование графа и привести пример такого графа - это зачастую со... - Week 8 - Экзамен
Заключительная работа по материалу всего курса
Prerequisite
Instructors
Андрей Райгородский
профессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Андрей Купавский
кандидат физико-математических наук
Кафедра дискретной математики ФИВТ МФТИ
Editor
The Moscow Institute of Physics and Technology (State University), or MFTI, is a Russian university located in Dolgoproudny and Moscow.
The Moscow Institute of Physics and Technology was founded in February 1946 by the Russian Academy of Sciences at the urging of physicist Piotr Kapitsa: the aim was to create an elite scientific university. It was here that the Phystech pedagogy was instituted, enabling hand-picked students to put together their own study and research programme under the guidance of a tutor.
Platform
Coursera is a digital company offering massive open online course founded by computer teachers Andrew Ng and Daphne Koller Stanford University, located in Mountain View, California.
Coursera works with top universities and organizations to make some of their courses available online, and offers courses in many subjects, including: physics, engineering, humanities, medicine, biology, social sciences, mathematics, business, computer science, digital marketing, data science, and other subjects.