Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен? Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины. Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети. Прослушав этот курс, вы проникнетесь чрезвычайно красивой математической теорией и научитесь решать комбинаторные и алгоритмические задачи на случайных графах. Все эти знания позволят нам затем перейти к курсу веб-графов, в котором мы расскажем о самых современных приложениях вероятностно-графовых моделей и конструкций. Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.
Пороговая вероятность для свойства связности: формулировка теоремы
Loading...
Do curso por Moscow Institute of Physics and Technology
Случайные графы
62 ratings
Na lição
Две модели случайного графа
Случайный граф Эрдеша-Реньи: биномиальная модель и равномерная модель. Свойства случайного графа. Свойство связности. Пороговая вероятность для свойства связности. Пороговая вероятность для свойства связности. Возникновение гигантской компоненты в случайном графе.
Conheça os instrutores
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Максим Жуковскийпреподаватель
кафедра дискретной математики МФТИ
Так, давайте я, наверное, даже с этой доски уйду, потому что я ее в каком-то
смысле замарал, и перемещусь на следующую доску,
дабы начать вам рассказывать то самое,
о чем уже неоднократно возглашал: буду рассказывать о связности случайного графа.
Связность случайного графа.
[БЕЗ ЗВУКА]
[БЕЗ ЗВУКА] Еще и еще раз: то,
что я сейчас буду формулировать, имеет исключительно значимый прикладной смысл.
И вот в рамках этой нашей первой, но в каком-то смысле вводной,
лекции, я как раз на это напирать и буду.
То есть доказывать теорему мы будем уже в следующей лекции.
Ну теорема на самом деле будет даже, наверное, не одна, или одна,
но состоящая из нескольких пунктов.
Вот сейчас я попробую ее аккуратно сформулировать,
всячески проинтерпретировать, ну а потом уже речь пойдет о доказательстве.
Так, ну я хочу еще заметить, что, собственно, теорема,
которую я сейчас буду формулировать и когда-нибудь доказывать,
это теорема, собственно, классиков, то есть Эрдеша и Реньи.
Она появилась ровно тогда, когда появилась эта замечательная модель.
И та мотивировка, о которой я буду говорить,
по большому счету существовала уже вот пол века назад.
Так, ну вот, давайте считать,
что вероятность ребра случайного графа (а мы сейчас работаем,
повторяю, в первой модели) — это действительно функция от n,
это действительно функция от n.
И эта функция от n имеет, на первый взгляд, едва ли не загадочный,
но во всяком случае весьма специфический вид.
Она выглядит вот так: это c логарифм натуральный n поделить на n,
где c — это какая-то константа.
И вот от значения этой константы, как вы сейчас увидите,
очень критическим образом будет зависеть свойство связности случайного графа.
То есть окажется, что мы действительно сможем оценить вероятность и убедиться в
справедливости каких-то очень ярких результатов.
Ну давайте перечислим по пунктам, что здесь происходит.
Значит, если c > 1, строго больше 1 (повторяю,
это константа!), строго больше 1, а n стремится к бесконечности,
то есть в этом случае вероятность ребра, конечно, стремится к 0.
Но вот она стремится к 0 не абы как, а именно так, причем c > 1.
Повторяю, сейчас это будет очень значимо.
Если c > 1, то асимптотически почти наверное случайный граф связен.
Ну в каком-то смысле не то, чтобы это ожидаемый результат,
но если смотреть на то, как c соотносится с единицей, то уж во всяком случае,
если и быть когда графу связным среди всех возможностей того,
какому значению может равняться c, то уж, наверное, при c > 1,
потому что ну ясно, что чем меньше вероятность ребра случайного графа,
тем меньше вероятность того, что эти ребра склеятся во что-то связное.
Если вероятность ребра случайного графа совсем крошечная, то,
наверное, и ребер-то вовсе не будет.
Мы об этом тоже, наверное, поговорим в свое время,
но пока вот такой вот результат.
С другой стороны, результат звучит достаточно удивительно.
Ведь оказывается, что для связности не нужно,
чтобы вероятность ребра была слишком высокой.
Оказывается, даже вероятность ребра, стремящаяся к 0, при n стремящемся к
бесконечности (лишь бы она стремилась к 0 вот таким вот специфическим образом),
уже дает нам шанс — высокий шанс!
— утверждать (шанс близкий к 1) утверждать,
что случайный граф окажется связным.
Капнул на нас из тучки граф, и он будет скорее всего связным в этом случае.
Следующая ситуация.
Если c < 1, то асимптотически
почти наверное случайный граф не связен.
А вот это уже некий пафос!
Потому что ну, конечно, если мы не видим пункта 1,
а начинаем формулировку теоремы прямо с пункта 2,
то это опять допускает такой же точно комментарий: ну понятно,
да, c — маленькое, вероятность ребра стремится к 0,
то есть вообще очень маловероятно, что ребра в графе появляются.
Ну, наверное, граф развалится на какие-то отдельные бяки.
Да, удастся доказать, что он асимптотически почти наверное не связен.
Но вот в сочетании с пунктом 1, пункт 2 показывает, что свойство связности
случайного графа, оно проявляется в каком-то смысле скачкообразно.
Как физики говорят (и это очень удобный термин), имеет место
фазовый переход, резкий скачок от проявления асимптотически
почти наверное связности к проявлению асимптотически почти наверное несвязности.
Перескочили через такую ну почти невидимою границу,
через некий порог, который равен: функция логарифм n поделить на n.
Перескочили как бы вправо, c оказалось больше 1 — и граф почти
наверное связен, но перескочили как бы влево,
c < 1 — и граф асимптотически почти наверное связным не является.
Совершенно удивительный момент перехода
от одного состояния вещества, так сказать, к другому.
Это и называется фазовый переход в науке, не только в физике.
И когда физики изучают это свойство (а они изучают его и изучают очень глубоко), они,
конечно, тоже констатируют тот факт, что здесь речь идет о фазовом переходе.
Но, друзья, значит, как бы это впечатляюще не выглядело для тех,
кто еще с таким не сталкивался, возникает вопрос: а что будет в третьем пункте?
Значит, c у нас здесь, заметьте, предполагается равной константе,
поэтому есть только одна оставшаяся возможность для того,
какой может оказаться вот эта функция p(n).
Давайте напишем третий пункт теоремы.
Если c = 1,
то асимптотически почти наверное...
Ой!
Это я зарапортовался.
Ничего не будет асимптотически почти наверное!
Нет, в том-то вся и суть!
Ну и извините, да, я задумался над чем-то другим.
Конечно, речь идет не о том, что здесь что-то будет выполняться с вероятностью,
стремящейся к 1.
Нет. Выше порога — да,
асимптотически почти наверное.
Ниже — да, асимптотически почти наверное.
Но прямо на пороге, то есть когда c = 1, будет выполнено нечто иное,
а именно: вероятность того, что случайный граф в этом случае окажется связным,
она не стремится ни к 1, как это было в 1-м пункте, ни к 0,
как это было фактически во 2-м пункте (граф асимптотически почти наверное
не связен, это значит, что он связен с вероятностью, стремящейся к 0).
Нет, предел этой вероятности найден, но он не равен ни 1, ни 0,
а равен он, при n стремящемся к бесконечности, e в минус первой степени.
Ну вот так: ни больше, ни меньше.
Значит, друзья,
чтоб не замучить вас, я в этом курсе пункт 3 все-таки доказывать не буду.
Я его традиционно не доказываю,
потому что он требует выхода немножко за рамки нашей обычной техники.
Нам бы, дай бог, разобраться с пунктами 1 и 2.
Они сами по себе уже, в общем, достаточно нетривиальны.
Конечно, мы с ними разберемся, и они, собственно, показывают наиболее
содержательную с практической точки зрения картину, о чем я скоро и поговорю.
А пункт 3 — ну это потрясающая, конечно, замечательная математика,
позволяющая посчитать такой предел.
Но в контексте пункта 3, который я,
повторяю, доказывать в рамках этих лекций не стану, в контексте пункта
3 еще более впечатляющая математика стоит за следующим замечанием.
Вот давайте я сделаю такое замечание.
На самом деле, конечно, мир клином не сошелся только на функциях такого вида,
это вы прекрасно понимаете.
И даже если c = 1 (ну это константа), ну мы получаем логарифм n поделить на n.
А можно рассматривать функции вида логарифм n поделить на n,
которые не получаются при взятии c равного 1, которые очень близки к этой функции,
асимптотически близки, но все-таки от нее отличны.
Так вот, оказывается, удается доказать вот такой тонкий совершенно
факт: показать как именно на пороге происходит переход от
почти наверное связности к почти наверное несвязности.
Пусть p(n), функция вероятности ребра, задается совсем впечатляющей формулой.
Значит, мы пишем логарифм n, то есть как будто бы мы умножили числитель на
c равное 1, но на этом не успокаиваемся, а прибавляем сюда
некоторую константу γ, после чего вот эту всю дробь...
Ой!..
Весь вот этот числитель делим снова на n.
Согласитесь, что получается некоторая функция, которая, очевидно, отлична от
той функции, что у нас присутствует неявно вот в этом написанном здесь пункте 3.
Ну как?
Она ей асимптотически равна, но ведь не равна же в точности γ.
Это же не 0, понимаете?
Ну не 0, вот, то есть это какая-то другая функция p(n).
Ну, естественно, она никак не попадает ни в рамки пункта 1,
ни в рамки пункта 2, потому что, ну да, она близка к: логарифм n поделить на n.
Ее нельзя считать отличающейся там во сколько-то раз от этой функции,
она лишь на какую-то аддитивную, вот на такое слагаемое,
на аддитивную составляющую отличается от нее.
То есть это некий отдельный вид функции, который нигде в рамках пункта...
пунктов 1, 2, 3 теоремы не встречался.
Оказывается, что для этой функции тоже можно все посчитать.
Тогда, и это производит ну почти впечатление катарсиса,
хоть я ничего и не доказал, тогда вероятность того,
что случайный граф связен, стремится
к e в степени (−e) в степени (−γ).
Но только, пожалуйста, не падайте.
Это производит некоторое впечатление на неподготовленного слушателя,
но вот так вот, вот так жизнь здесь устроена.
Но что попишешь?
Так вот жизнь устроена, да.
Вот.
Что это означает?
Вот смотрите, пусть γ равняется 0, ну как в пункте 3.
В точности.
Подставим сюда γ, равное 0.
e в минус нулевой — это 1.
Получилось e в минус первой в точности.
То есть да, действительно,
вот это утверждение является более общим фактом по отношению к пункту 3.
3 — это частный случай вот этого утверждения при γ, равном 0.
Вот. С другой стороны, смотрите: конечно,
сколь бы большим ни было вот это число γ,
сколь бы большим это число ни было, все равно в пункт 1 мы не попадаем.
Пункт 1 — это более сильное условие.
Мы не добавляем какую-то огромную константу к функции логарифм,
а мы умножаем функцию логарифм на некоторую константу, строго большую 1.
Естественно, это быстрее растущий числитель, нежели при любом конкретном γ,
сколь бы большим оно ни было.
Тем не менее, если мы вот это число γ в нашем утверждении пытаемся растить,
делать все большим и большим, ну устремим, если угодно,
к плюс бесконечности, если мы γ устремим к плюс бесконечности,
у нас e в степени (−γ) отправится благополучно в 0.
Но тогда e в минус нулевой — это просто 1.
То есть получается,
что переход к пункту 1 осуществляется в каком-то смысле даже раньше.
Нам не нужно вот настолько сильно перескочить через порог, нам достаточно
добавить вот здесь, ну, что-нибудь растущее, какую-нибудь не константу,
а функцию, которая бы сама стремилась к бесконечности.
И тогда в пределе мы получим тот самый 0.
Ту самую, извините, 1, которая и заявлена в пункте 1.
Граф асимптотически почти наверное окажется связан.
С другой стороны, если мы, наоборот, начнем уменьшать константу γ,
получая в пределе минус бесконечность, мы опять же не попадем в точности в пункт 2,
то есть мы не сможем добиться того, что, даже при очень маленьком γ, вероятность
ребра окажется во сколько-нибудь раз меньше, нежели логарифм n поделить на n.
Нет, она будет по-прежнему ей асимптотически равна.
Но тем не менее, при γ, стремящемся к минус бесконечности,
e в степени (−γ) уходит на плюс бесконечность,
а e в степени (−e) в степени (−γ) благополучно отправляется в 0,
опять же тот самый, который анонсирован в рамках пункта 2.
А именно, пункт 2 утверждает,
что случайный граф связен с предельной вероятностью 0.
То есть мы показываем, на самом деле, что происходит на пороге.
Вот порог — это логарифм n поделить на n.
И чтобы выскочить с него, достаточно прибавить что-то очень медленно растущее,
а чтобы соскочить с него, упасть в несвязность, достаточно, наоборот,
вычесть что-то очень медленно растущее.
Ну вот при любой константе мы имеем все-таки такую предельную вероятность,
которая находится в интервале от 0 до 1.
Вот такой совершенно удивительный результат.
Повторяю, пункты 3 и замечания я не доказываю,
а пункты 1 и 2 я рано или поздно докажу.
Но прежде чем я это сделаю, давайте я все-таки дам содержательную интерпретацию
вот этой вот теореме, чтобы вы понимали, насколько крутой прикладной смысл
эта теорема на самом деле в себе несет, какой крутой прикладной смысл она имеет.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
