Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен? Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины. Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети. Прослушав этот курс, вы проникнетесь чрезвычайно красивой математической теорией и научитесь решать комбинаторные и алгоритмические задачи на случайных графах. Все эти знания позволят нам затем перейти к курсу веб-графов, в котором мы расскажем о самых современных приложениях вероятностно-графовых моделей и конструкций. Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.
Нижняя оценка вероятности связности: формулировка теоремы
Loading...
From the course by Moscow Institute of Physics and Technology
Случайные графы
62 ratings
From the lesson
Две модели случайного графа
Случайный граф Эрдеша-Реньи: биномиальная модель и равномерная модель. Свойства случайного графа. Свойство связности. Пороговая вероятность для свойства связности. Пороговая вероятность для свойства связности. Возникновение гигантской компоненты в случайном графе.
Meet the Instructors
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Максим Жуковскийпреподаватель
кафедра дискретной математики МФТИ
Давайте с этой целью сформулируем теорему «штрих», которая в каком-то смысле,
она, конечно, не является следствием теоремы, которую мы докажем,
а она является следствием более аккуратных выкладок, что ли, в этой теореме.
Ну можно будет легко конкретизировать доказательство теоремы,
когда оно появится, так, чтобы получилась именно эта теорема штрих.
Давайте рассмотрим только случай пункта 1 и предположим,
что c даже не единицы больше, а не меньше, чем 3, ну так вот, для определённости.
Значит, пусть p (n) = c lgn / n и c больше либо равняется 3.
То есть мы как бы усилили пункт 1.
Мы дополнительно предположили, что c ещё больше,
нежели это было в пункте 1 исходной теоремы.
Ну ясно, что в этом случае граф асимптотически почти наверное связен,
но мы скажем, насколько вероятна эта связность,
не просто стремится к единице, а дадим явную количественную оценку,
и это нам позволит сделать как раз замечательные практические выводы.
Тогда вероятность того, что случайный граф связен,
не меньше, чем 1 − 1 / n,
но здесь надо ещё предположить что-то про n.
Давайте я добавлю, коль скоро, коль скоро n,
ну скажем, больше либо равняется 100.
Для наших практических нужд это предположение совсем не ограничительное,
наверняка я его переборщил, то есть можно было предположить гораздо меньше,
но уж при n, больше либо равном 100, я точно могу гарантировать,
что вероятность связности оценивается снизу как 1 − 1 / n.
То есть мы можем прямо явно сказать, как стремится к единице вероятность
связности случайного графа в этом режиме, в этой ситуации.
Вот. Ну давайте в справедливость этой теоремы
поверим, ту мы докажем,
а пока я проинтерпретирую это на практическом примере, как это работает.
Вот давайте, например, возьмём n, равное 2000, возьмём n,
равное 2000, и рассмотрим следующую практическую совершенно ситуацию.
Вот у нас есть некоторое количество компьютеров,
ну или, если хотите, серверов, Ну в общем, компьютеров, машин.
Значит, один компьютер, второй, они тоже занумерованы, как вершины нашего
случайного графа, третий, и так далее, компьютер с номером 2000.
И эти компьютеры раскиданы как угодно, что там, по нашей стране, по всему миру,
по всей Земле.
И вот между этими компьютерами, считается,
что это важные какие-то информационные центры, налажена система связи.
Ну имеется в виду телефонных спутниковых линий,
которые позволяют передавать информацию с каждого отдельно взятого
компьютера на каждый из оставшихся 1999 компьютеров.
То есть есть и вот такая телефонная линия, которая позволяет передавать информацию
с компьютера номер 1 на компьютер номер 2 и обратно, есть такая телефонная линия,
которая связывает 1 и 2000, такая, такая, такая,
такая, короче говоря, образуется полный граф вот таких вот телекоммуникаций,
возможностей связи между каждыми двумя компьютерами в нашей огромной,
огромной сети, раскиданной по всему миру.
Ну как водится, вы ж понимаете, на практике это очень естественная вещь,
как водится, связи между компьютерами, вот эти вот самые телекоммуникации,
телефонные линии, ну они подвержены каким-то помехам, и понятно,
что с определённой вероятностью, конечно, зависящей от того,
насколько хорошо построена вот эта вот телефонная линия, насколько силен,
скажем, передатчик, приёмник, и так далее.
В зависимости от этого есть какая-то вероятность, которая, ну к сожалению,
отвечает за то, что сообщение не будет передано.
Или будет передано настолько искажённым, что всё, смысл потеряется.
Ну давайте считать, что вероятность разрыва связи равняется какому-то числу q.
Причём она не зависит от того, с какими двумя компьютерами мы имеем дело,
то есть разрывается связь между первыми двумя с вероятностью q,
между вторым и третьим с вероятностью q,
между вторым и двухтысячным тоже с вероятностью q, то есть, если хотите,
q — это вероятность исчезновения ребра вот такого вот полного графа.
Ну и давайте ещё предположим,
что сами рёбра взаимно независимо пропадают.
Ну такое тоже довольно естественное предположение, мы просто предполагаем,
что помеха в телефонной линии, которая соединяла компьютеры с номерами 1 и 2,
и помеха там в какой-нибудь телефонной линии между 3 и 2000,
они никак друг на друга не влияют, это довольно естественное предположение.
То есть q — это вероятность уничтожения отдельной связи,
уничтожения отдельной связи,
ну а если угодно,
p — это вероятность её сохранения.
Тогда действительно мы получаем те самые обозначения,
с которыми работали до сих пор.
То есть q = 1 − p, потому что связь, ясно, либо сохраняется,
либо уничтожается в результате помехи, никакого третьего не дано.
То есть мы имеем дело с той самой монеткой абстрактной, которую мы бросали,
когда строили наш случайный граф.
И взаимная независимость изничтожения рёбер это то же самое,
конечно, что взаимная независимость, наоборот, сохранения им жизни.
То есть, если угодно, у нас получается тот самый случайный граф,
который мы только что определили.
Вот это был полный граф на 2000 вершинах,
а из него под действием помех случайным образом может
получиться какой угодно граф, имеющий те же самые 2000 вершин,
но какое-то, вообще говоря, меньшее количество рёбер.
То есть это тот самый случайный граф, я, может быть, не говорил, но его принято вот
так обозначать, тот самый случайный граф, граф R (iii) G (n, p), который мы
с вами изучаем, где p, повторяю, это 1 − q, а q, соответственно, 1 − p.
Но в чём же пафос, скажете вы.
Хе. Так я же ещё не применил теорему штрих.
Давайте возьмём в точности c, равное 3, вот прямо в точности равное 3, например.
Можно, конечно, варьировать, в зависимости от этого там оценка будет как-то
улучшаться, ну пускай c = 3, по крайней мере,
для него теорема точно верна и результат получится наиболее впечатляющим.
Тогда смотрите, чему равняется p, вот тут впервые становится понятно,
почему так важна зависимость от n указывать вот в определении вероятности p.
Что такое p от 2000, это 3 ln (2000) / 2000.
Это вероятность сохранения жизни связи в случае вот этой случайной помехи.
Ну если вы возьмёте калькулятор и посчитаете,
чему равняется 3 ln (2000) / 2000, я, честно говоря, традиционно забываю,
но будет что-то примерно равное, насколько я помню, 0,02.
Ну не судите меня слишком строго, если я там обсчитался,
посмотрите на сотовом телефоне, не знаю, я думаю, что будет что-то типа 0,02.
То есть вероятность помехи, победы помехи, так сказать, над нашей связью,
победы противника над нашей безопасностью, ну или каких-то просто случайных помех,
вот эта вероятность q, она примерно, стало быть, равна 0,98.
То есть вот этот наш невидимый противник, то ли настоящий,
который чего-то думает там и хочет козни устраивать, то ли просто помехи,
которые возникают из-за того, что канал связи недостаточно хорошо нарушен,
вот каждое ребро, каждую телекоммуникацию, каждую телефонную
линию он уничтожает с вероятностью, почти равной 1, и заметьте,
что если бы я здесь взял не 2000 для примера, а 10000,
то эта вероятность была бы ещё ближе к 1 и результат бы, смотрите какой
результат получился впечатляющий, а результат был бы ещё более впечатляющим.
Смотрите, мы же знаем, что вероятность связности случайного графа не меньше,
чем 1 − 1 / n, то есть вот при такой вероятности разрыва каждой отдельной связи
независимо от остальных, вероятность того, что случайный граф останется связным,
останется связным, останется связным,
эта вероятность не меньше, чем 1 − 1 / 2000,
то есть это есть что-то такое, если я не обсчитался, правда же?
То есть вероятность уничтожения отдельной связи это 0,98, почти 1.
Но вероятность сохранения связности это ещё ближе к 1,
это вообще пренебрежимо мало отличается от единицы.
Мы можем быть практически уверены, что разрешив помехам возникать вот с
такой высокой вероятностью, мы всё-таки на выходе получим связный граф.
Ну а что значит мы получим связный граф, это значит, что из любого
компьютера в любой из оставшихся можно будет направить сообщение, да, конечно,
не напрямую, да, конечно, по какой-то, может быть, очень сложной цепочке,
но это всегда можно будет сделать, потому что граф-то остался связным.
Всегда или не всегда, но вот во стольких случаях,
то есть 99,95 процентов случаев, это очень крутой результат.
Ну а свет-то, он же идёт со скоростью 300 000 км в секунду, то есть очень быстро,
поэтому даже если компьютеры раскиданы по нашему земному шарику, уж как-нибудь,
пусть по длинной цепочке, но он дойдёт и донесёт сообщение
достаточно быстро, всё, знаете, не на Марс письма писать, всё гораздо ближе.
Вот. Поэтому это, конечно, удивительный,
совершенно замечательный результат, и будет круто, если мы научимся получать
такие результаты, поймём технику, которая позволяет их получать, и так далее.
Что я ещё хочу здесь сказать.
Сразу, покуда я не перейду к некоторому интересному продолжению,
продолжение следует, спокойно.
Значит, прежде, чем я перейду к продолжению,
ну я скажу, что, конечно, есть масса практических задач,
когда в качестве исходного графа берётся неполный граф.
Понятно, например, что вот эти вот пункты, которые здесь нарисованы,
это могут быть не компьютеры, а какие-нибудь населённые пункты,
между которыми проложены дороги, и вот эти дороги могут уничтожаться с какой-то
вероятностью, например, в результате просто пожизненного износа.
Они изнашиваются, изнашиваются, изнашиваются, превращаются в непроезжие
грунтовки, и в этом случае, как бы вам сказать, коммуникация,
она осуществляется ведь тогда не со скоростью света, правда, то есть тут надо
уже перемещаться как-то на своих двоих ли на автомобилях, и здесь очень важно,
уничтожилась дорога или не уничтожилась, ну хоть связность бы сохранить, да?
Но, конечно, трудно себе представить, что если у вас есть 2000 населённых пунктов,
то они прямо вот попарно связаны отдельными дорогами,
такого обычно не бывает.
Поэтому в такой ситуации рассматривают более сложные задачи, задачи, когда
в качестве исходного графа рассматривается не полный граф, а какой-то,
и у него взаимно независимо уничтожаются или, если угодно, проводятся рёбра.
Это более сложная задача, для неё тоже есть результаты.
Но это, конечно, предмет уже гораздо более позднего обсуждения,
сейчас давайте разбираться вот с такого рода фактами,
дай Бог с ними-то разобраться.
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.
