Модели случайных графов

Модели случайных графов
978-5-4439-1025-3
Издательство МЦНМО

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

Наиболее яркие и красивые сюжеты науки о случайных графах, которая лежит на стыке комбинаторики, теории графов и теории вероятностей.

полистать mccme




Эта книга рассказывает об одной весьма красивой и богатой приложениями науке –– науке о случайных графах. Эта наука находится на стыке комбинаторики, теории графов и теории вероятностей. В основе ее лежит глубокая идея о том, что мощные инструменты современной теории вероятностей должны поспособствовать более верному осознанию природы графа, призваны помочь решению многих комбинаторных и теоретико-графовых задач.
Данная книга возникла на основе лекций, которые ее автор читал на школах «Современная математика» в Дубне и «Комбинаторная математика и теория алгоритмов» в Судиславле, а также в Школе Анализа Данных Яндекса. В ней мы не претендуем на исчерпывающее изложение теории, которая давно уже превратилась в огромную и бурно развивающуюся –– почти необозримую –– математическую дисциплину. У нас совсем другая цель. Мы хотим на максимально доступном уровне рассказать наиболее яркие и красивые сюжеты, связанные со случайными графами. В сущности, мы постараемся сделать книгу понятной студентам младших курсов университетов и даже старшеклассникам, всерьез увлекающимся математикой. В то же время мы дойдем до столь глубоких и нетривиальных фактов, что книга окажется полезной всем, кто интересуется комбинаторикой, вероятностью и их приложениями.
В целом структура книги следующая. В первой главе мы изложим основы теории вероятностей, знание которых необходимо для дальнейшего чтения. Читатель, знакомый с этими основами, может при желании пропустить эту главу. Однако стоит иметь в виду, что некоторые понятия, обсуждаемые в ней, не вполне элементарны. Например, таково понятие мартингала, которое в стандартных курсах теории вероятностей обычно не возникает.
Во второй главе мы расскажем о модели Эрдёша –– Реньи случайного графа, которая была предложена ровно полвека назад и с которой, по большому счету, и началась вся наука. Мы представим, в наглядной и увлекательной форме, несколько результатов, которые удается получить в рамках такой модели.
В третьей главе мы поговорим о моделях, которые естественным образом обобщают модель Эрдёша –– Реньи. С их помощью мы докажем ряд исключительно красивых утверждений в области комбинаторной геометрии.
Наконец, в четвертой главе мы выйдем, можно сказать, на передний край науки: мы обсудим модели Интернета и других больших или, как принято говорить, «реальных» сетей.
Заключительным разделом книги будет «приложение», в котором мы опишем ряд простых и в то же время довольно скучных понятий математического анализа. Разумеется, мы предполагаем хотя бы поверхностное знакомство читателя с пределами, производными и интегралами. Однако некоторые объекты и обозначения мы постараемся аккуратно ввести и прокомментировать. Хотя, повторим еще раз, наша книга отнюдь не является полноценной монографией, она, безусловно, закладывает основы теории и с нее удобно начинать изучение случайных графов, благо она предлагает сразу (как минимум) три принципиально различных направления исследований. Некоторые факты, доказанные в ней, совсем свежие, и они еще ждут правильного осмысления и развития. Мы приглашаем читателя на увлекательную экскурсию и надеемся, что если кому-то она будет просто интересной, то кому-то она поможет и с выбором задач для последующего их изучения.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *