Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен? Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины. Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети. Прослушав этот курс, вы проникнетесь чрезвычайно красивой математической теорией и научитесь решать комбинаторные и алгоритмические задачи на случайных графах. Все эти знания позволят нам затем перейти к курсу веб-графов, в котором мы расскажем о самых современных приложениях вероятностно-графовых моделей и конструкций. Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.
Постановка задачи
Loading...
From the course by Moscow Institute of Physics and Technology
Случайные графы
62 ratings
From the lesson
Малые подграфы в случайном графе
Распределение малых подрафов в случайном графе: пороговые вероятности и Пуассоновская предельная теорема на пороге.
Meet the Instructors
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Максим Жуковскийпреподаватель
кафедра дискретной математики МФТИ
Добрый день, друзья!
Ну, мы с вами уже довольно много всего изучили: связность случайного графа,
которая, в общем, имеет даже и прикладное значение, очень много поговорили о
раскрасках, о хроматическом числе и связанных с ним характеристиках.
С этой темы, конечно, пора слезать, и вот последняя в рамках этого курса,
на мой взгляд, действительно очень важная в том числе и с точки зрения приложений
тема — это тема о количестве подграфов заданного типа в случайном графе.
Ну, сейчас я поясню, о чем идет речь.
Это вещь действительно очень полезная.
Нужно понимать, сколько графов данного вида встречается в случайном графе.
То есть, на вас падает случайный граф и вы хотите понять, сколько в нем,
например, треугольников.
Или сколько в нем деревьев на 17-ти вершинах.
Ну, давайте введем соответствующие обозначения.
Значит, тема будет — количество вхождений конкретного графа в случайный граф.
Давайте конкретный граф обозначим буквой H.
Значит, H — это некоторый фиксированный граф,
некоторый фиксированный граф.
Как я уже сказал, это может быть треугольник, это может быть дерево,
это может быть какой-нибудь цикл на 17-ти вершинах, что хотите, ну,
в общем, это некоторый фиксированный раз и навсегда граф.
Вот, а буквой G мы будем, как обычно, обозначать случайный граф.
То есть, у нас, как всегда, есть случайный граф,
у которого множество вершин V, вполне себе определенное,
оно состоит из n элементов и может представляться как отрезок натурального
ряда от 1 до n, вот, и у него есть случайное множество ребер.
Давайте я запишу, действительно,
что множество вершин — это множество чисел от 1 до n.
Ну и, как водится, у случайного графа есть вероятность возникновения ребра — это p,
которая, вообще говоря, зависит от n, и, как на всех предшествующих лекциях,
мы, конечно, будем стараться изучать те характеристики, которые я сейчас введу,
в первую очередь с ростом n, то есть будем смотреть, как варьируется их поведение,
изменяется их поведение при n, стремящемся к бесконечности.
Ну, вроде у нас так всегда и было.
Значит, давайте через X с индексом H от G обозначим,
ну, в случае случайного графа, случайную величину.
Значит X с индексом H от G — это случайная
величина, случайная
величина, равная
количеству копий графа H в случайном графе G,
копий — то есть изоморфных копий, случайная величина,
равная количеству
копий графа H,
вот этого, абсолютно фиксированного графа, с никак не растущим количеством вершин,
в случайном графе G, у которого как раз количество вершин очень даже будет расти.
То есть, еще раз, нас интересует, действительно,
сколько раз вот этот конкретный граф H входит в растущий случайный граф G,
сколько там присутствует копий.
Это действительно очень важная характеристика с точки зрения практики,
потому что оказывается, что многие реальные сети, например, интернет,
или социальные сети, или сети биологического характера,
происхождения — они отличаются от каких-то произвольных графов тем,
что для них вот эти характеристики ведут себя некоторым специальным образом.
Например, хорошо известно,
что в интернете много треугольников — это свидетельствует о том, что очень часто мои
знакомые являются знакомыми между собой, что вполне естественно.
Вот, но и какие-то другие конкретные графы тоже очень интересно, очень интересно
рассматривать, как они входят в случайный граф и за счет этого можно как-то
характеризовать поведение этой случайной сети, этого случайного графа.
Ну, а с другой стороны, как всегда, я, в общем, говорю,
что это прекрасная математика, и сейчас мы поймем, как ведет себя вот эта вот
случайная величина в зависимости от различных свойств графа H.
Прежде чем я буду переходить собственно к вероятностным рассуждениям,
то есть к формулировке точной теоремы, которая здесь получается,
давайте я все-таки немножко еще поясню,
что такое вот это X с индексом H от G, ну, на каких-нибудь примерах.
Давайте, например, считать, что H — это треугольник,
граф на 3-х фиксированных вершинах, а G — хоть и случайный,
но вот он реализовался, и представляет собою полный граф на n вершинах.
То есть, давайте считать, что G — это K с индексом n, полный граф на n вершинах.
Тогда чему равняется X с индексом H от G?
Сколько есть треугольников в полном графе на n вершинах?
Ну, ответ, конечно, очевиден — это С из n по 3.
Можно задаться более сложным вопросом.
Пусть G — по-прежнему Kn, но H — это, скажем,
простой цикл, простой цикл
на k вершинах, где k — какое-то фиксированное число.
Значит, простой цикл на k вершинах.
А G реализовался по-прежнему как полный граф.
Ну тогда, конечно, X с индексом H от G, мы неоднократно эту величину считали,
когда занимались с вами раскрасками, короткими циклами в случайных графах,
X с индексом H от G — это есть, конечно, C из n по k.
Мы, прежде всего, фиксируем вершины для нашего цикла.
Но затем, мы же говорим об изоморфной копии, правильно?
Затем надо еще посчитать, сколькими способами цикл можно расположить на
данных k вершинах, и, как мы это не раз уже замечали,
такая вещь делается (k−1) факториал пополам способами.
То есть, вхождений конкретного цикла на k вершинах в граф на n вершинах,
полный — это вот такое вот количество, C из n по k на (k−1) факториал пополам.
Вот.
Ну, разумеется, можно посмотреть на какие-то более сложные объекты,
но, мне кажется, что в общем идея понятна.
В общем идея понятна.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
