- Sur www.coursera.org
Теория графов
![](https://cdn.edflex.com/media/cache/conceptor_200x100/conceptor/logo/5a16626e13c65c77f043b30da4f9a11e0bbb99aa.png)
- À son rythme
- Accès libre
- Certificat payant
- 8 séquences
- Niveau Introductif
Détails du cours
Déroulé
- Week 1 - Введение. Базовые понятия теории графов
В первую неделю курса мы познакомимся с понятием графа, научимся отличать граф от его изображения, поговорим о разных видах графов. Мы вспомним, с чего началась теория графов, научимся представлять в виде графа структуру интернета. Мы обсудим такие важные поня... - Week 2 - Эквивалентные определения дерева. Планарные графы
На этой неделе мы научимся определять деревья четырьмя различными способами, и поговорим о том, как правильно раскрашивать географические карты. Мы вспомним знаменитую теорему о четырех красках, а также критерий Куратовского о том, как определить, можно ли на... - Week 3 - Формула Кэли. Унициклические графы. Эйлеровы циклы
На этой неделе мы перечислим все деревья. Для этого нам потребуется перенять опыт древних по подсчету баранов (или козлов). Не остановившись на этом, перечислим и все леса и унициклические графы. Затем мы вернемся к задаче о Кёнигсбергских мостах и получим пол... - Week 4 - Гамильтоновы циклы
На этой неделе мы продолжим обсуждать циклы, проходящие через весь граф. На этот раз мы поговорим про циклы, проходящие через все вершины графа. В отличие от эйлеровых циклов, здесь нет необходимого и достаточного критерия наличия такого цикла. Есть только дос... - Week 5 - Паросочетания. Теоремы Холла и Кёнига
На этой неделе мы поговорим про паросочетания. Мы узнаем, что нужно, чтобы переженить всех юношей и девушек по любви. Мы обсудим две классических теоремы, у одной из которых очень изящное доказательство по индукции, а у другой не менее изящное доказательство а... - Week 6 - Экстремальная теория графов. Теорема Турана
На этой неделе мы начнем разговор про экстремальную теорию графов, которая ставит вопросы про то, с какого момента графы начинают обладать тем или иным свойством. В частности, мы выясним, сколько ребер должен иметь граф, чтобы он гарантированно содержал треуго... - Week 7 - Теория Рамсея
На заключительной лекции мы поговорим про теорию Рамсея. Вы узнаете много нового о знакомствах, о том, сколько раз можно в одном доказательстве применить принцип Дирихле и о том, что доказать существование графа и привести пример такого графа - это зачастую со... - Week 8 - Экзамен
Заключительная работа по материалу всего курса
Prérequis
Intervenants
Андрей Райгородский
профессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Андрей Купавский
кандидат физико-математических наук
Кафедра дискретной математики ФИВТ МФТИ
Éditeur
L'Institut de physique et de technique de Moscou (université d'État), ou MFTI, est une université russe située à Dolgoproudny et Moscou.
L'Institut de physique et de technologie de Moscou a été fondé en février 1946 par l'Académie des sciences de Russie à la demande pressante du physicien Piotr Kapitsa : l'objectif était de créer une université scientifique d'élite. C'est là que fut institué la pédagogie du Phystech, consistant à permettre à des étudiants triés sur le volet de composer leur propre programme d'études et de recherche sous la direction d'un tuteur.
![](https://cdn.edflex.com/media/cache/conceptor_200x100/conceptor/logo/5a16626e13c65c77f043b30da4f9a11e0bbb99aa.png)
Plateforme
Coursera est une entreprise numérique proposant des formations en ligne ouverte à tous fondée par les professeurs d'informatique Andrew Ng et Daphne Koller de l'université Stanford, située à Mountain View, Californie.
Ce qui la différencie le plus des autres plateformes MOOC, c'est qu'elle travaille qu'avec les meilleures universités et organisations mondiales et diffuse leurs contenus sur le web.
![](https://cdn.edflex.com/media/cache/conceptor_200x100/conceptor/logo/43fe7785dc4604070a5d6838e3200cdd2695597a.png)