Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен? Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины. Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети. Прослушав этот курс, вы проникнетесь чрезвычайно красивой математической теорией и научитесь решать комбинаторные и алгоритмические задачи на случайных графах. Все эти знания позволят нам затем перейти к курсу веб-графов, в котором мы расскажем о самых современных приложениях вероятностно-графовых моделей и конструкций. Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.
Задача о древесных компонентах случайного графа
Loading...
En provenance du cours de Moscow Institute of Physics and Technology
Случайные графы
62 notes
À partir de la leçon
Хроматическое число случайного графа
Оценки хроматического числа случайного графа G(n,p) при различных p=p(n).
Rencontrer les enseignants
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Максим Жуковскийпреподаватель
кафедра дискретной математики МФТИ
Так, давайте поразбираемся ещё с тем, как устроены компоненты связности случайного
графа, когда вероятность ребра маленькая, то есть рассмотрим классический случайный
граф Эрдёша – Реньи в предположении, что p(n) это o(1 / n),
ну или что то же самое… Давайте я вот так напишу,
равносильно тому, что p * n стремится к нулю при n стремящемся к бесконечности.
Мы с вами, конечно, знаем из лекционного материала, что в этом случае почти,
наверное, все компоненты связности случайного графа суть деревья.
Это вот важный момент, который мы отразили на лекции, что, с одной стороны,
вроде как в этом режиме, то есть при такой вероятности ребра случайный граф
распадается на крошечные компоненты, это бездоказательный материал первой лекции.
Теорема о гигантской компоненте связности, что в этом случае её как раз нет,
и всё распадается на феодализм, но вот на текущей лекции, к которой мы,
собственно, делаем семинар, мы разобрались с тем, что этот феодализм,
он на самом деле не абы как устроен, а все компоненты связности — это деревья.
Но мы же не доказывали теорему о том,
что феодализм даёт логарифмическое количество вершин.
Вот в этой ситуации нетрудно доказать,
что размер каждой древесной компоненты маленький.
Но тут, конечно, очень важно, что p (n) — это это o маленькое от одной n-ной, то
есть мы не работаем в случае p равняется с поделить на n с c меньшим единицы,
это важно, поэтому мы находимся, конечно, в привилегированной ситуации сейчас.
Итак, давайте докажем следующее утверждение.
Вероятность того, что существует древесная компонента,
ну то есть компонента, представляющая собой дерево… Древесная
компонента с не менее,
чем c логарифм n вершинами.
Что вот эта вероятность стремится к нулю при n стремящемся к бесконечности,
а c — это произвольная наперёд фиксированная константа большая нуля.
Мы задаёмся константой c больше нуля, может быть,
даже очень маленькой, и всё равно можем утверждать, что с вероятностью,
которая стремится к нулю, найдётся-таки древесная компонента с большим,
вот в этом смысле большим, количеством вершин.
Мы сейчас действительно докажем, что вот в этом предположении асимптотически почти,
наверное, каждая древесная компонента случайного графа крошечная поскольку все
компоненты деревья, мы это доказали на лекции,
то по сути мы докажем утверждение замечательной теоремы
об отсутствии гигантской компоненты, по крайней мере, вот в этой ситуации.
Это довольно интересно.
Ну ничего тут такого сложного нет.
Что значит существует древесная компонента?
Ну, прежде всего, надо перебрать, конечно, варианты,
сколько вершин может быть у этой древесной компоненты, то есть вот эта вероятность,
ну она точно не превосходит суммы по всем k.
Давайте я подсмотрю сюда, чтобы у меня не было ошибок.
Больше либо равным c логарифм n.
k — это количество вершин в той самой древесной компоненте,
которая могла бы возникнуть в случайном графе.
И понятно, что если мы считаем только те древесные компоненты, у которых не меньше
чем c логарифм n вершин, то и k у нас в суммировании не меньше чем c логарифм n.
Ну а дальше надо просто посчитать или оценить, вернее, вероятность того,
что существует древесная компонента с ровно k вершинами.
Вероятность того, что существует древесная компонента,
древесная компонента с k вершинами.
Ну, опять же, как это можно посчитать?
Да более или менее традиционно.
У нас же граф на n вершинах?
А древесные компоненты мы ищем на k вершинах.
То есть, прежде всего, надо выбрать какие-то k вершин из n возможных и потом
на этих k вершинах произвольным способом зафиксировать одно из возможных деревьев.
Значит, тогда у нас получится, что это всё не превосходит
суммы по k больше либо равному c логарифм n, C из n по k,
k в степени (k − 2), как раз формула Келли, выражающая
количество способов зафиксировать дерево на данных k вершинах, да?
И дальше надо умножить эту штуку на вероятность того,
что вот наше конкретное дерево, совершенно определённое,
что вот это совершенно конкретное дерево присутствует в случайном графе,
и не просто присутствует, а ещё и является древесной компонентой.
То есть это целая компонента связности.
Значит, p в (k − 1) степени — это вероятность того, что k минус одно
ребро вот этого конкретного k вершинного дерева таки попало в случайный граф.
А дальше надо написать 1 − p в степени,
которая равна количеству заведомо отсутствующих рёбер.
Ну давайте подумаем, какие рёбра заведомо отсутствуют?
Во-первых, отсутствуют те рёбра, которые отсутствуют в дереве.
Если древесная компонента представляет собой ровно вот это дерево,
то k минус одно ребро присутствует,
а все остальные рёбра полного графа там, конечно, отсутствуют.
Компоненты — это ровно вот это дерево, никаких других рёбер нету.
Ну и, кроме того, надо ещё заметить, что нету, естественно, никаких рёбер,
которые бы вели из этой компоненты куда-то наружу.
Можно как-нибудь где-нибудь нарисовать вот здесь картинку.
То есть вот эта компонента, в ней всего k вершин, а вот большая сарделька,
состоящая из n вершин — это множество всех вершин нашего графа.
И если вот это конкретное дерево, давайте здесь рогатульку такую условную нарисую,
вот если это конкретное дерево образует именно компоненту связности в
случайном графе, это означает, что никакого вот такого мостика быть не может.
Но сколько всего таких мостиков?
k вариантов — выбрать левый конец, n − k вариантов — выбрать правый конец,
то есть k * (n − k).
Вот эти все рёбра должны отсутствовать, которые ведут из компоненты наружу.
Если они присутствуют, хотя бы одно, то, значит, мы рассмотрели не всю компоненту,
а можно к ней ещё что-то добавить.
Ну вот отсутствие этих рёбер, оно происходит с такой вероятностью.
Ну на самом деле мы старались-то зря, то есть мы посчитали всё аккуратно,
но нам хватит грубой оценки,
а именно я возьму и сейчас вот эту вот штуку всю оценю сверху единицей.
Прошу прощения.
Значит, я скажу, что это строго меньше чем сумма по k больше либо
равному c логарифм n, C из n по k,
k в степени (k − 2), и просто p в степени (k − 1).
А дальше давайте c-шку оценим традиционным способом,
то есть как n в степени k поделить на k факториал.
Это меньше либо равно сумма по k больше,
либо равном c логарифм n, n в степени k / k факториал,
* k в степени (k − 2) * p в (k − 1) степени.
k факториал стоит в знаменателе.
Давайте воспользуемся неравенством очевидным,
k факториал больше либо равняется k / e в степени k.
Ну не то, что она очевидная, но, скажем так,
общеизвестная и очень легко получается с помощью математической индукции.
Значит, с помощью математической индукции оно сразу может быть получено легко.
Так, пишем дальше меньше либо равно сумма по k не меньшем c логарифм n.
Так, пишем n в степени k / k в степени k,
* e в степени k * k в степени (k − 2) * p в (k − 1) степени.
Подставили просто вместо k факториала его оценку величиной k поделить на e в k-той.
Вот оно k в k-той в знаменателе, а из знаменателя знаменатель экспонента ушла в
числитель e в степени k находится в числителе.
Так, ну это очень мило, потому что кое-что сокращается.
Давайте n вынесем за знак суммирования, это сейчас будет удобно, сейчас увидите.
Здесь k больше либо равно c логарифм n по-прежнему,
здесь у нас будет… Так, наверное, e я тоже вытащу.
Сейчас я соображу.
Да, e я тоже вытащу за знак суммирования.
Тогда у меня останется n в (k − 1), да?
e в (k − 1).
Так, а k в k-той сократится?
Так, и p в (k − 1).
Ух ты, как здорово!
А k в k-той сократится с k в (k − 2) и в знаменателе останется просто k²,
правильно?
k², да, вроде бы совершенно правильно, отлично.
Так, ну и что я теперь хочу сделать?
Так, ааа… Так, мы сейчас это всё очень тупо оценим.
Потрясающе!
Потрясающе, потрясающе, потрясающе!
Смотрите.
Давайте я это перепишу, чтобы было понятнее.
Так, вот у меня есть ne, вот у меня есть
сумма по k больше либо равному
c логарифм n, ne p в (k − 1), ну и всё это делится на k².
А теперь смотрите.
Наш режим каков?
Режим таков, что n умноженное на p стремится к нулю,
ну значит, nep тоже стремится к нулю, разумеется.
То есть начиная с некоторого n маленького, начиная с какого-то количества вершин Вот
это произведение меньше единицы, а k у нас больше либо равняется
c * логарифм n и оно стоит в показателе числа, меньшего единицы.
Ну тогда вот эта вся штучка точно может быть оценена,
внимание, сверху, потому что k оценивается снизу, но здесь стоит число меньше 1.
Оценена сверху как (nep) в степени c * логарифм n − 1.
То есть мы получаем вот так: (ne) * на (nep) в степени (c * логарифм n − 1),
а дальше стоит уже сумма по k больше либо
равному (c * логарифм n) величин единицы поделить на k в квадрате.
Ну, как известно, ряд-то состоящий из величин 1 / k² сходится, и даже не важно,
что здесь суммирование ведется от какого-то растущего нижнего предела.
В общем-то можно оценить эту сумму и суммой просто по k
от единицы до бесконечности вот таких вот величин.
Некоторые наверное знают, что эта сумма равняется π²/6 загадочным образом,
но про это я, конечно, сейчас говорить не буду.
В любом случае, вот эта штука ограничена явно некоторой константой.
Поэтому мы можем написать вот так: О большое от
ne * на (nep)
в степени (c * логарифм n − 1).
Ну и осталось, наверное, загнать вот это ne сюда внутрь.
Я думаю, что мы так и напишем.
Так...
сейчас, секундочку...
я соображу...
Значит, вот эта штука у нас стремится к нулю,
и она возводится в степень (c * логарифм n), а здесь еще стоит n, да?
Давайте я спишу, наверное, со шпаргалки, что у меня в этом месте написано.
Ну во-первых: да, смотрю в шпаргалку как, знаете, смотрит в книгу и видит фигу.
Ясно совершенно, что вот это e — это же константа,
поэтому ее спокойно можно не писать под знаком О большого.
Это я, конечно, сделал зря.
Вот я смотрю в шпаргалку, а у меня в шпаргалке e нет.
Думаю — какой ужас!
Как же мне теперь быть?
В шпаргалке ошибка!
Ну нет, конечно.
О большое — оно всегда понимается с точностью до константы,
поэтому от этого e избавиться не составляет никакого труда.
Его что пиши, что не пиши.
Суть от этого не поменяется.
Вот.
Ну а n нужно как-то сюда будет сейчас загнать.
Так...
Сейчас я перепишу то, что у меня написано в шпаргалке, а потом прокомментирую.
Значит, пишется вот так: (e в степени 1/c
* npe),
и все это по-прежнему в степени (c * логарифм n − 1), под знаком О большого.
Вот давайте попробуем понять, что произошло.
Произошла очень простая вещь.
Смотрите: е в степени 1/c...
е в степени 1/c, если ее возвести в степень (c * логарифм n),
смотрите, с сократится, да?
Останется e в степени логарифм n.
Но e в степени логарифм n, товарищи, это в точности то самое n,
которое здесь написано.
То есть я просто взял и так исхитрился: я вместо сомножителя n
написал e в степени 1/c в степени c * логарифм n.
И опять вот это вычитание единички при возведении e в
1/c в соответствующую степень — оно все благополучно уходит под знак О большого.
То есть наличие вот этой −1 при возведении e в степени 1/c вот в такую
степень никак не играет роли.
А играет роль только вот это выражение, c * логарифм n, которое нам n и дает.
Замечательно, всё.
То есть мы убедились в том, что это равенство справедливо,
а тогда что у нас получается?
Да все совершенно понятно.
Вот это вот произведение стремится к нулю.
np же у нас стремится к нулю?
Значит, будучи умножено на какую-либо константу, оно дает функцию,
все еще стремящуюся к нулю.
Неважно, насколько маленькое это c,
если оно фиксировано — то все вот это выражение стремится к нулю.
И оно возводится еще в растущую степень.
Конечно, это с огромным запасом отправляется в ноль и то,
что мы утверждали, мы доказали.
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2018 Coursera Inc. Tous droits réservés.
