Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен? Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины. Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети. Прослушав этот курс, вы проникнетесь чрезвычайно красивой математической теорией и научитесь решать комбинаторные и алгоритмические задачи на случайных графах. Все эти знания позволят нам затем перейти к курсу веб-графов, в котором мы расскажем о самых современных приложениях вероятностно-графовых моделей и конструкций. Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.
Доказательство теоремы
Loading...
來自 Moscow Institute of Physics and Technology 的課程
Случайные графы
65 個評分
從本節課中
Хроматическое число случайного графа
Оценки хроматического числа случайного графа G(n,p) при различных p=p(n).
與講師見面
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Максим Жуковскийпреподаватель
кафедра дискретной математики МФТИ
Но доказательство его совершенно стандартно,
доказательство этого результата фактически мы рассказывали на прошлой лекции,
только на прошлой лекции мы разбирали случай, когда p = не 1 / 2,
а какой-то там загадочной величине n в степени θ − 1,
и тогда там логарифм брался тоже по какому-то другому основанию, было там,
помните, логарифм n / p какая-то там целая часть, 3 еще в числителе.
Ну это все, ладно, чего я, собственно, болтаю, давайте, действительно,
воспроизведем доказательство.
Так, вероятность того, что α(G),
давайте я даже напишу < строго, чем 2log двоичный n — это будет только
более сильное утверждение, то есть, я сейчас стремлюсь доказать, что вероятность
даже вот этого события стремится к 1, коль скоро n неограниченно возрастает.
Ну из этого, конечно, будет следовать то, что я написал.
Значит, вероятность того, что α(G) < чем 2 двоичных логарифма n,
это, как и на прошлой лекции, вероятность того,
что независимые множества вот такого размера в случайном графе отсутствуют.
Ну, я вот сейчас задумался, я было собирался вот так написать,
но, понимаете, вот это число нецелое.
И если я сейчас хочу сказать, что у меня отсутствуют независимые
множества в точности такого размера, то это будет не очень хорошо.
Ну давайте я нарисую здесь целую часть, так будет точно понятнее,
и уж во всяком случае по-прежнему правильно, потому что целая часть в свою
очередь не превосходит своего аргумента, то есть удвоенного двоичного логарифма.
Значит нам надо доказать, что вот эта вероятность стремится к 1.
Ну, давайте обозначим временно вот эту штучку x,
как на прошлой лекции, тогда у нас получится вероятность того,
что Y с индексом x от G = 0, где, вспоминаете, что такое Yx(G)?
Значит, Yx(G) — это количество независимых множеств размера
x в случайном графе G, ну я, конечно, напишу это сейчас.
Значит, Yx(G) — это количество
независимых множеств в случайном графе G.
Математическое ожидание Y с индексом x мы благополучно считали на прошлой лекции,
поэтому я могу его радостно написать.
Значит, оно считалось вот так: C из n по x на 1 − p в степени C из x по 2.
Я могу только вкратце напомнить, что вот это вот за счет линейности
— количество просто тех множеств, каждое из которых мы тестируем.
1 − p — это вероятность отсутствия ребра, но p у нас равняется 1 / 2 сейчас.
Я просто так написал, чтоб вы вспомнили, что у нас было на прошлой лекции.
А C из x по 2 — это количество тех ребер, которые должны отсутствовать,
коль скоро мы зафиксировали конкретное x-элементное множество и тестируем
его на независимость.
Вот, ну давайте перепишем так,
как это будет соответствовать текущей ситуации, то есть, сюда напишем 1 / 2.
1 / 2 в степени C из x по 2 — это то же самое,
что 2 в степени −C из x по 2, просто так перерисовал.
И что я хочу доказать?
А я хочу доказать, что вот эта величина при текущем выборе параметра x,
то есть целая часть 2log двоичных n, вот эта величина стремится к 0 при n,
стремящемся к бесконечности, потому что я смогу применить неравенство Маркова.
Ну, всему свое время.
Значит, оцениваем стандартно, как n в степени x / на x
факториал × 2 в степени −x × (x − 1) / 2.
И товарищи, которые хорошо помнят прошлую лекцию,
они скажут: а вы же пренебрегли вот этим факториалом в знаменателе.
Но на той лекции пренебрег, а сейчас не хочу, сейчас он мне поможет,
потому что я хочу вот именно такое неравенство получить, как здесь написано,
и вот мне этот x факториал сейчас будет исключительно полезен.
Так, ну давайте напишем 2 в степени
x на log двоичный n − x квадрат / 2 + x / 2.
Собственно вот этот паразитический + x / 2 мне и нужно будет загасить,
так сказать, с помощью факториала, который стоит в знаменателе.
Давайте разделим на факториал стало быть, то есть,
им пренебрегать не будем пока я просто написал точное равенство.
Ну и давайте вместо x честно подставлять целую часть от удвоенного
двоичного логарифма.
Так, смотрите, давайте я вот здесь наверное это напишу сейчас аккуратненько.
Смотрите, целая часть от удвоенного двоичного логарифма n,
конечно, как я уже неоднократно говорил,
не превосходит своего аргумента, но с другой стороны,
она же ≥ того же самого аргумента без 1.
То есть, целая часть лежит в пределах от арумента уменьшенного на 1 до самого
этого аргумента.
И я этим сейчас аккуратненько воспользуюсь.
Вот здесь x идет со знаком +,
поэтому я буду пользоваться неравенством оценкой сверху.
Значит, у меня получится 2 в степени 2log двоичный в квадрате n.
А вот здесь он идет со знаком −, поэтому я воспользуюсь нижней оценкой,
я скажу, что логарифм ≥, нежели логарифм − 1.
И со знаком «−» продолжу в правильную сторону неравенство, получится ≤.
Так, ну конечно, я размахнулся, у меня вот здесь места
сейчас не хватит на это вычитание, ну да ладно, ничего страшного.
Давайте как бы нам это лучше сделать...
Нет, мне это не нравится, давайте я сейчас вот так вот это аккуратненько
сотру и сюда перейду, а то у меня места не хватит.
Так, 2 в степени — еще раз подставляю оценку — 2log двоичный
в квадрате n — это я пока оценил x — дальше с минусом
у меня идет 1 / 2 × 2 log двоичный n − 1 в квадрате.
Ну и с плюсом, собственно,
идет опять удвоенный двоичный логарифм, который мы делим пополам.
Вот такая вот штука.
Ну вы видите сейчас, что у меня здесь места просто никак бы не хватило,
поэтому я вовремя спохватился и написал понятную запись, а то было бы некрасиво.
Так, теперь давайте раскрывать скобки вот в этой замечательной формуле.
Что такое 2 логарифм двоичный n − 1 в квадрате?
Ну во-первых, надо в квадрат возвести вот
эту величину — будет 4log в квадрате n пополам.
Пишем.
А, виноват, забыл еще поделить на x факториал, это очень важно.
Так, получится 2 в степени 2log двоичный
в квадрате n, и здесь, как мы выяснили, вычитается, ой,
какая удача, тот же самый удвоенный двоичный логарифм в квадрате.
Такая вот удивительная вещь: вычитается-то он же.
Ну смотрите, с минусом идет удвоенное произведение, оно делится пополам,
то есть, в итоге с плюсом идет у меня, а что у меня идет с плюсом?
Логарифм двоичный n.
И еще раз он идет с плюсом.
У меня получается 2log двоичный n,
ну и еще вот эта вот −1 / 2.
Ну −1 / 2, она вообще никакой роли не играет,
давайте я напишу ≤ и не буду таскать ее за собой, потому что −1 / 2 это только <.
Вот, замечательно.
Ну и, конечно, все надо поделить на x факториал.
Наконец можно радостно сделать «шлеп»- «шлеп», я очень люблю этот момент,
когда все сокращается, как в тетрисе, вот, они так провалились.
И у нас получилось выражение: 2 в степени 2 двоичных
логарифма n поделить на x факториал.
Ну так, друзья, x-то факториал растет гораздо быстрее,
чем 2 в степени x, но тут стоит примерно 2 в степени x,
а тут стоит примерно x в степени x.
Ну я не знаю, можно воспользоваться, например,
неравенством x факториал ≥ x / e в степени x, уж такое неравенство
легко доказать просто по индукции — сделайте это как несложное упражнение,
и тогда у вас получится какая-то вот такая вот оценка: 2
в степени 2 log двоичный n × e в степени x,
то есть, в степени целая часть от 2log двоичный n,
и все это поделить на целая часть от 2log двоичный
n в степени та же самая целая часть от 2log двоичный n.
Вот это все уже какое-то техническое занудство,
которое особенного интереса-то не представляет.
Тут написана экспонента, видите, в знаменателе стоят константы,
а тут растущая функция возводится в такую же степень,
в которую здесь возводились константы.
Видите, как мне пригодился этот x факториал.
Понятно, что с большим запасом это стремится к 0,
коль скоро n неограниченно возрастает.
И все, значит, мы применяем неравенство Маркова.
Вероятность того, что α(G) <,
чем x = вероятности того, что Yx(G)
= 0 = 1 − вероятность того,
что Yx(G) ≥ 1, ну и это ≥ 1
− математическое ожидание x,
про которое мы только что выяснили, что оно стремится к 0.
Значит, эта разность стремится к 1 при n, стремящемся к бесконечности,
и мы действительно доказали,
что асимптотически почти наверное число независимости маленькое.
Замечательно!
Но теперь, все-таки, по поводу кликового числа, то есть, вот этой величины ω(G).
Почему на самом деле для нее все то же самое?
Ну так, дело в том, что,
если Yx будет означать не количество независимых множеств размера x,
а количество товарищей клик полных подграфов на x вершинах,
так у него будет в точности такое же математическое ожидание при p = 1 / 2.
То есть, конечно, оно будет вот таким: C из n по x × p в степени C из x по 2,
но при p = 1 / 2 математическое ожидание абсолютно такое же,
и дальше читаем прямо по тексту — получаем в точности
те же самые неравенства Маркова и опять-таки стремление к 1.
То есть, асимптотически почти наверное ω(G) ровно по тем же причинам не
превосходит x, по которым его не превосходила только что величина α(G).
Вот такой вот замечательный совершенно результат получился у нас с вами.
