Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен? Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины. Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети. Прослушав этот курс, вы проникнетесь чрезвычайно красивой математической теорией и научитесь решать комбинаторные и алгоритмические задачи на случайных графах. Все эти знания позволят нам затем перейти к курсу веб-графов, в котором мы расскажем о самых современных приложениях вероятностно-графовых моделей и конструкций. Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.
Завершение доказательства
Loading...
From the course by Moscow Institute of Physics and Technology
Случайные графы
65 ratings
From the lesson
Алгоритмы на случайном графе
Жадный алгоритм раскраски. Жадное хроматическое число, жадное число независимости и жадное кликовое число. Теорема о жадном хроматическом числе и жадном числе независимости случайного графа.
Meet the Instructors
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Максим Жуковскийпреподаватель
кафедра дискретной математики МФТИ
Так, ну мы вступаем с вами в завершающую стадию.
Прямо вот на финишную прямую, можно сказать, выходим.
Давайте я еще раз напишу, что у нас вероятность интересующего нас события,
про которую мы хотим сказать, что она стремится к нулю,
оценивается суммой по всем a(1)...
a(m), каждая из которых не превосходит (1 −
δ) на log двоичный n, Σ по всем C(1)...
C(m) таким, что для любых i и j C(i) и C(j) не пересекаются,
и для любого i C(i) имеет мощность a(i), а суммируются вероятности тех событий,
которые мы только что очень компактненько оценили.
Поэтому можем спокойно эту компактную оценку и написать.
e в степени − [n в степени (1 + δ) поделить на 8 логарифмов двоичных n].
Вот это то, чем мы завершили предыдущую серию исписанных досок, я бы так сказал.
Вот. Ну давайте считать,
что наши чиселки a(i) пока что зафиксированные, и вот для любой такой
фиксации попробуем оценить величину вот этой вот внутренней кратной суммы.
Суммы по всем способам выбрать множества C(1)...
C(m) так, чтобы они не пересекались и имели мощности,
равные нашим фиксированным числам a(i), соответственно.
Ну радость состоит в том, что экспонента, которая написана под знаком суммирования,
она вообще никак не зависит от переменных суммирования.
То есть мы вполне можем ее вытащить за знак суммирования.
Суммироваться будут единицы, Ну то есть сумма будет равна просто количеству
способов зафиксировать множества, которые под знаком суммы написаны.
Что вот эта вот сумма, это просто количество способов выбрать C(1)...
C(m) так, чтобы они не пересекались и имели такие мощности.
Ну давайте грубо оценим.
Нам этого вполне хватит.
Все равно катарсис наступит.
Давайте грубо оценивать.
Меньше эту сумму я переписываю, тут деваться некуда, a(1)...
a(m) таким, что для любого i a(i) ≤ (1 − δ) log двоичный n.
С этой суммой мы ничего пока поделать не можем.
Переписываем e в степени − [n в степени (1 + δ)
поделить на 8 двоичных логарифмов n], и дальше надо какую-то
грубую оценку написать для количества способов выбрать такие множества.
Ну давайте, смотрите.
C из n по a(1), это, конечно, количество способов зафиксировать множество C(1).
Это даже не оценка, это просто точное количество.
Ну давайте напишем C из n по a(2) — это количество способов зафиксировать
множество A(2), ой, извините — множество C(2), имеющее мощность a(2).
Ну вы мне скажете: «А как же так?
Они же должны не пересекаться, правильно?
Что же я здесь n пишу?» Строго говоря, я должен написать n − a(1),
но я же говорю, что я буду грубо оценивать.
Я грубо оцениваю.
Я плюю на то, что эти множества не пересекаются,
и при подсчете их количества как бы заново каждый раз выбираю множество.
Мне это никак не повредит для итоговой оценки.
Ну и так далее.
Последнее множество тоже выбирается уж никак не больше,
чем C из n по a(m) способами.
Понятно, что меньше.
Последняя-то вообще там почти фиксируется, но нет вот...
Можно написать такое грубое произведение C-шек.
Ну давайте заметим в скобках, что C из a по b тривиальным образом меньше,
чем a в степени b, мы с вами на протяжении этих лекций не раз таким, даже очень
грубым неравенством пользовались, и продолжим нашу грубую деятельность.
Заметим, кстати, что вот эта экспонента, она ведь и от a тоже никак не зависит.
Давайте-ка ее выкинем наружу от всего суммирования.
То есть у нас получится e в степени − [n в степени (1
+ δ) поделенное на 8 двоичных логарифмов n] — все это в показателе экспоненты.
Дальше мы грубо, да — напишем сумму, конечно, извините,
по a(1), ..., a(m) таким,
что для любого i a(i) ≤ (1 − δ) на log двоичный n,
а внутри суммы напишем вот эти оценки.
То есть будет n в степени a(1) +...
+ a(m).
Успеваете, товарищи?
Не кокнул?
Ну просто тупо оцениваем первую C-шку как n в степени a(1), пользуясь вот этим
неравенством, вторую — как n в степени a(2), последнюю — как n в степени a(m).
Перемножаем, получаем n в степени сумма a(1), ..., a(m).
Ну мы ж с вами не раз говорили, что сумма вот этих чисел не превосходит n пополам.
Наверное не нужно это заново получать.
Это известный факт.
Значит мы можем все оценить дальше вот так вот:
e в степени − [n в степени (1 + δ) на 8 двоичных логарифмов n] умножить
на n в степени n пополам, мы его вынесли за знак суммирования, потому
что мы огрубили оценку и она перестала зависеть от параметров a(1), ..., a(m).
А здесь стоит сумма по всем способам выбрать числа a(1),
..., a(m) так, чтобы для каждого i a(i) не превосходило
(1 − δ) на log двоичное n, а суммируются тупо единицы.
Хе, ну так что значит просуммировать единицы по всем способам
выбрать эти числа?
Это просто надо посчитать количество способов, опять-таки,
выбрать вот эти числа.
Ну давайте я грубо это опять оценю.
Вот так значит.
Первые два сомножителя оставлю — n в степени (1 + δ) 8
двоичных логарифмов n, n в степени n пополам.
А количество слагаемых оценю так.
Ну понятно, что каждое a(i) меньше, чем логарифм n.
Фух, ну с большим запасом.
Ну оно правда может от нуля начинаться...
Нет, ну ноль как же — это ж все-таки независимое множество.
Значит оно начинается от единицы.
То есть каждое отдельно взятое a(i) выбирается уж точно меньше,
чем log двоичное n-способами.
А всего их n штук.
Ну значит количество способов зафиксировать их все.
Это log двоичный n в степени m.
Каждая выбирается не более чем столькими способами, даже менее чем столькими,
ну а все они в совокупности, это m-тая степень от этого числа.
Так, ну это, конечно, грандиозно.
Давайте вспомним, что m — это скажем величина
целая часть от n два (1 − δ) на
log двоичный n, но тупо m меньше, чем n.
Продолжаем неравенство.
Давайте я вот здесь звездочку поставлю, и звездочка будет равна...
Я просто совсем огрубил оценку.
m меньше, чем n.
Мне даже этого хватит.
Сейчас я все загоню под одну общую экспоненту.
Первая — она так и останется n в степени (1 + δ) на 8 двоичных логарифмов n.
Дальше у меня прибавится за счет вот этого n в степени n пополам.
Прибавится n пополам.
Логарифм натуральный n и прибавится, за счет моей грубой оценки,
n на логарифм натуральный от, извините, двоичного логарифма n.
Я просто все эти выражения загнал под одну общую экспоненту.
Значит e в степени — вот эта странная штуковина,
это как раз есть логарифм двоичный n, возведенный в n-ную степень,
которая служит оценкой для m в данном конкретном случае.
То есть здесь вроде бы все очень грубо.
Но вот в этом месте все было достаточно тонко,
и ровно ради этого места мы так аккуратно выбирали параметры.
А здесь все очень-очень грубо оценивается, и вы, конечно,
удивляетесь наверное как же так, ну вообще — просто тяп-ляп.
Я совершенно не напрягаюсь, оценивая эти C-шки, количество a(i) и так далее.
Ну вот — так вот можно.
В этом месте так можно.
Ну а теперь наступает аналитический катарсис,
потому что посмотрите что произошло.
У нас δ, это некоторая константа, которая строго больше нуля.
Мы ее заранее зафиксировали.
Выбрали просто фиксированное число δ.
То есть вот здесь написано n в степени одна целая,
и дальше там, после запятой хоть что-нибудь.
Ну, скажем, n в степени одна целая одна милионная,
или n в степени одна целая одна десятая, или n в степени одна целая,
там, пятнадцать квадрилионных, или еще что-нибудь.
Но вот это число, которое стоит в показателе n, оно строго больше единицы.
Эта фиксированная константа (1 + δ) строго больше единицы.
Даже если мы такую штуковину, обведенную в кружочек,
делим на логарифм двоичный n, я об этом говорил кстати,
мы все равно не сможем компенсировать, забить вот этим логарифмом δ-вую степень.
Можно, например, сказать так.
Если n больше, либо равняется n(0), то заведомо n в степени (1
+ δ) поделить на 8 двоичных логарифмов n,
больше либо равняется, ну скажем n в степени (1 + δ/2).
Потому что, как хорошо известно из курса анализа,
логарифм растет медленнее любой положительной степени числа n.
Даже если δ, это одна квадрилионная, или что-нибудь в таком духе,
логарифм ее компенсировать, забить, не сможет.
Поэтому мы, начиная с некоторого n сумеем вот эту всю дробь оценить как опять
же n в степени один плюс что-то позитивное, что-то положительное.
Вот. И эта штуковина идет со знаком минус,
заметьте, в показателе нашей экспоненты,
а со знаком плюс идет n просто в первой степени, ну, правда,
помноженное на какой-то логарифм, который, по тем же самым соображениям,
никакого позитивного вклада в степень n на самом деле не дает.
То есть совершенно понятно, что вот эта вот вещь, вот это выражение,
которое у нас идет со знаком минус, с ростом n асимптотически,
преобладает над вот этой величиной.
Ну и точно так же оно преобладает над вот этой величиной,
потому что здесь n умножается и вовсе не на логарифм даже,
а на повторный логарифм n, там с точностью до какой-то константы.
То есть это вообще еле-еле отлипает от n, это тоже еле отлипает от n,
а эта величина отлипает содержательно и она идет со знаком минус,
поэтому понятно, что при больших n, при n, стремящимся к бесконечности,
весь вот этот вот показатель экспоненты стремится к минус бесконечности,
а вся эта экспонента стремится к нулю.
И это ровно то, чего мы хотели доказать.
Это и есть завершение доказательства нашей теоремы.
Видите, вот эта вот отрицательная штука растет быстрее к минус бесконечности,
чем все положительные добавки.
Они — ничтожно маленькие по сравнению с ней.
То есть получаем стремление к нулю, причем с большим запасом, и все отлично.
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.
© 2019 Coursera Inc. All rights reserved.
