Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен?
Случайные графы
Moscow Institute of Physics and TechnologyAbout this Course
4,302 recent views
Shareable Certificate
Earn a Certificate upon completion
100% online
Start instantly and learn at your own schedule.
Flexible deadlines
Reset deadlines in accordance to your schedule.
Approx. 21 hours to complete
Russian
Subtitles: Russian
Shareable Certificate
Earn a Certificate upon completion
100% online
Start instantly and learn at your own schedule.
Flexible deadlines
Reset deadlines in accordance to your schedule.
Approx. 21 hours to complete
Russian
Subtitles: Russian
Offered by
Moscow Institute of Physics and Technology
Московский физико-технический институт (Физтех) является одним из ведущих вузов страны и входит в основные рейтинги лучших университетов мира. Институт обладает не только богатой историей – основателями и профессорами института были Нобелевские лауреаты Пётр Капица, Лев Ландау и Николай Семенов – но и большой научно-исследовательской базой.
Syllabus - What you will learn from this course
3 hours to complete
Две модели случайного графа
Случайный граф Эрдеша-Реньи: биномиальная модель и равномерная модель. Свойства случайного графа. Свойство связности. Пороговая вероятность для свойства связности. Пороговая вероятность для свойства связности. Возникновение гигантской компоненты в случайном графе.
3 hours to complete
15 videos (Total 94 min), 4 readings, 2 quizzes
15 videos
МФТИ1m
История зарождения понятия случайного графа4m
Биномиальная модель случайного графа12m
Связность случайного графа на четырех вершинах3m
Эволюция случайного графа6m
Равномерная модель случайного графа3m
Пороговая вероятность для свойства связности: формулировка теоремы14m
Нижняя оценка вероятности связности: формулировка теоремы12m
Теорема о появлении гигантской компоненты в случайном графе10m
Задача о монотонности вероятности4m
Задача о промежуточных значениях вероятности5m
Задача о дополнительных ребрах3m
Задача об одном ребре2m
Задача о дереве4m
Задача о простом цикле3m
4 readings
МФТИ10m
Комментарий к лекции10m
Дополнительные задачи10m
Конспект лекции10m
2 practice exercises
Задачи к семинару 130m
Итоговые задания по неделе 130m
4 hours to complete
Теорема о пороговой вероятности для свойства связности
Неравенство Маркова и Чебышева. Доказательство теоремы о пороговой вероятности для свойства связности случайного графа.
4 hours to complete
16 videos (Total 132 min), 3 readings, 2 quizzes
16 videos
Напоминание теоремы о пороговой вероятности для свойства связности2m
Применение неравенства Чебышева9m
Оценивание математического ожидания10m
Оценивание дисперсии10m
Вероятность существования изолированной вершины5m
Разложение случайного графа на компоненты связности2m
Оценивание математического ожидания числа компонент связности15m
Представление оценки в виде суммы двух слагаемых5m
Предел первого слагаемого10m
Предел второго слагаемого9m
Задача о количестве изолированных вершин в случайном двудольном графе8m
Задача о существовании изолированной вершины в случайном двудольном графе17m
Задача об одной изолированной вершине4m
Задача о количестве вершин степени 14m
Задача о связности случайного графа при большой вероятности проведения ребра8m
3 readings
Комментарий к задаче о существовании изолированной вершины в случайном двудольном графе10m
Дополнительные задачи10m
Конспект лекции10m
2 practice exercises
Задачи к семинару 230m
Итоговые задания по неделе 230m
3 hours to complete
Вероятностный метод
Хроматическое число, число независимости и кликовое число. Обхват графа. Теорема о существовании графа с большим обхватом и большим хроматическим числом.
3 hours to complete
15 videos (Total 102 min), 3 readings, 2 quizzes
15 videos
Обхват графа2m
Теорема о графе с большим обхватом и большим хроматическим числом: формулировка теоремы и идея доказательства5m
Введение случайности5m
Оценка математического ожидания числа циклов15m
Применение неравенства Маркова для оценивания обхвата3m
Оценка математического ожидания числа независимых множеств7m
Применение неравенства Маркова для оценивания числа независимости6m
Существование графа с большим хроматическим числом и малым количеством циклов1m
Модификация графа6m
Задача о количестве 4-циклов в случайном двудольном графе15m
Задача об отсутствии циклов в равномерной модели1m
Задача о хроматическом числе случайного графа в равномерной модели4m
Задача об оценке числа независимости7m
Задача о хроматическом числе случайного графа с 5 ребрами7m
3 readings
Замечание: существование длинных циклов10m
Дополнительные задачи10m
Конспект лекции10m
2 practice exercises
Задачи к семинару 330m
Итоговые задания по неделе 330m
3 hours to complete
Хроматическое число случайного графа
Оценки хроматического числа случайного графа G(n,p) при различных p=p(n).
3 hours to complete
14 videos (Total 113 min), 3 readings, 2 quizzes
14 videos
Доказательство теоремы11m
Хроматическое число случайного графа без ребер5m
Хроматическое число сильно разреженного случайного графа4m
Доказательство того, что в случайном разреженном графе отсутствуют циклы6m
Хроматическое число случайного графа G(n,c/n)10m
Хроматическое число слабо разреженного графа9m
Точная асимптотика хроматического числа G(n,0.5)5m
Идея доказательства теоремы Боллобаша7m
Алгоритм покраски10m
Задача о хроматическом числе и обхвате случайного двудольного графа10m
Задача о хроматическом числа графа G(6,5)5m
Задача о древесных компонентах случайного графа14m
Задача об оценке хроматического числа случайного графа специального вида3m
3 readings
Комментарий к лекции: тройка вместо двойки10m
Дополнительные задачи10m
Конспект лекции10m
2 practice exercises
Задачи к семинару 430m
Итоговые задания по неделе 430m
Reviews
TOP REVIEWS FROM СЛУЧАЙНЫЕ ГРАФЫ
by VTOct 17, 2016
Прошел курс исключительно из за лектора. Даже не знаю, пригодится ли мне на практике, но очень захватывающе изложено.
Frequently Asked Questions
When will I have access to the lectures and assignments?
Access to lectures and assignments depends on your type of enrollment. If you take a course in audit mode, you will be able to see most course materials for free. To access graded assignments and to earn a Certificate, you will need to purchase the Certificate experience, during or after your audit. If you don't see the audit option:
- The course may not offer an audit option. You can try a Free Trial instead, or apply for Financial Aid.
- The course may offer 'Full Course, No Certificate' instead. This option lets you see all course materials, submit required assessments, and get a final grade. This also means that you will not be able to purchase a Certificate experience.
What will I get if I purchase the Certificate?
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.
Is financial aid available?
Yes, Coursera provides financial aid to learners who cannot afford the fee. Apply for it by clicking on the Financial Aid link beneath the "Enroll" button on the left. You’ll be prompted to complete an application and will be notified if you are approved. Learn more.
More questions? Visit the Learner Help Center.
