Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

Moscow Institute of Physics and Technology

Случайные графы

Moscow Institute of Physics and Technology via Coursera

This course may be unavailable.

Overview

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен?

Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины.

Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети.

Прослушав этот курс, вы проникнетесь чрезвычайно красивой математической теорией и научитесь решать комбинаторные и алгоритмические задачи на случайных графах. Все эти знания позволят нам затем перейти к курсу веб-графов, в котором мы расскажем о самых современных приложениях вероятностно-графовых моделей и конструкций.

Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.

Syllabus

  • Две модели случайного графа
    • Случайный граф Эрдеша-Реньи: биномиальная модель и равномерная модель. Свойства случайного графа. Свойство связности. Пороговая вероятность для свойства связности. Пороговая вероятность для свойства связности. Возникновение гигантской компоненты в случайном графе.
  • Теорема о пороговой вероятности для свойства связности
    • Неравенство Маркова и Чебышева. Доказательство теоремы о пороговой вероятности для свойства связности случайного графа.
  • Вероятностный метод
    • Хроматическое число, число независимости и кликовое число. Обхват графа. Теорема о существовании графа с большим обхватом и большим хроматическим числом.
  • Хроматическое число случайного графа
    • Оценки хроматического числа случайного графа G(n,p) при различных p=p(n).
  • Алгоритмы на случайном графе
    • Жадный алгоритм раскраски. Жадное хроматическое число, жадное число независимости и жадное кликовое число. Теорема о жадном хроматическом числе и жадном числе независимости случайного графа.
  • Малые подграфы в случайном графе
    • Распределение малых подрафов в случайном графе: пороговые вероятности и Пуассоновская предельная теорема на пороге.
  • Итоговый тест
    • Заключительный экзамен, содержащий задачи по всем пройденным темам

Taught by

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

Reviews

Start your review of Случайные графы

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.