Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен?
oferecido por
Случайные графы
Instituto de Física e Tecnologia de MoscouInformações sobre o curso
oferecido por

Instituto de Física e Tecnologia de Moscou
Московский физико-технический институт (Физтех) является одним из ведущих вузов страны и входит в основные рейтинги лучших университетов мира. Институт обладает не только богатой историей – основателями и профессорами института были Нобелевские лауреаты Пётр Капица, Лев Ландау и Николай Семенов – но и большой научно-исследовательской базой.
Programa - O que você aprenderá com este curso
Две модели случайного графа
Случайный граф Эрдеша-Реньи: биномиальная модель и равномерная модель. Свойства случайного графа. Свойство связности. Пороговая вероятность для свойства связности. Пороговая вероятность для свойства связности. Возникновение гигантской компоненты в случайном графе.
Теорема о пороговой вероятности для свойства связности
Неравенство Маркова и Чебышева. Доказательство теоремы о пороговой вероятности для свойства связности случайного графа.
Вероятностный метод
Хроматическое число, число независимости и кликовое число. Обхват графа. Теорема о существовании графа с большим обхватом и большим хроматическим числом.
Хроматическое число случайного графа
Оценки хроматического числа случайного графа G(n,p) при различных p=p(n).
Avaliações
Principais avaliações do СЛУЧАЙНЫЕ ГРАФЫ
Прошел курс исключительно из за лектора. Даже не знаю, пригодится ли мне на практике, но очень захватывающе изложено.
Perguntas Frequentes – FAQ
Quando terei acesso às palestras e às tarefas?
O que recebo ao adquirir o Certificado?
Is financial aid available?
Mais dúvidas? Visite o Central de Ajuda ao Aprendiz.