Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен? Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины. Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети. Прослушав этот курс, вы проникнетесь чрезвычайно красивой математической теорией и научитесь решать комбинаторные и алгоритмические задачи на случайных графах. Все эти знания позволят нам затем перейти к курсу веб-графов, в котором мы расскажем о самых современных приложениях вероятностно-графовых моделей и конструкций. Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.
Оценка суммы
Loading...
Del curso dictado por Moscow Institute of Physics and Technology
Случайные графы
63 calificaciones
De la lección
Малые подграфы в случайном графе
Распределение малых подрафов в случайном графе: пороговые вероятности и Пуассоновская предельная теорема на пороге.
Conoce a los instructores
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Максим Жуковскийпреподаватель
кафедра дискретной математики МФТИ
Ну что, выходим на финишную прямую.
Давайте расписывать нашу двойную сумму так, как я, собственно, обещал.
Значит, сначала мы суммируем по всем t от 1 до k, это сколько у нас общих вершин.
Ну дальше, наверное, удобно все-таки нарисовать очередную картину,
вот у нас тут t общих вершин, тут k, тут k.
Нам нужно посчитать каким-то образом, сколько существует вот этих самых
способов зафиксировать 2 копии графа H с конкретно t общими вершинами.
Ну смотрите, все на самом деле просто: надо взять C из n по k — это
количество способов выбрать вершины для первой копии.
А затем надо подумать, сколькими способами можно выбрать вершины для второй копии.
Ну, во-первых, надо выбрать t общих.
Это делается C из k по t способами, выбираются те t общих,
по которым они пересекаются.
Дальше, когда эти t общих выбраны, нам надо взять n − k вершин,
которые не попали в фиксированную первую копию,
и добавить к уже зафиксированной части второй копии (зафиксировано t вершин),
вот видите, зафиксировано t вершин.
А всего во второй копии должно быть k вершин.
Ну значит, надо добавить k − t, вот у нас t вершин выбраны, еще k −
t вершин из n − k мы выбираем, и вот это уже в итоге получается то, чего нам нужно.
Так, ну это еще не все, потому что мы таким образом лишь зафиксировали вершины
для наших двух пересекающихся копий, но надо еще зафиксировать ребра, правильно?
То есть надо выбрать, как именно расположена копия графа H на
первом множестве, которое мы вот здесь вот выбирали одним из стольких способов,
и затем еще зафиксировать, как именно выбираются ребра на второй части.
Ну, понимаете, товарищи, нам-то нужно сейчас доказать, что все вот это
суммирование, будучи там на что-то поделенным (сейчас я напомню на что),
стремится к нулю при n, стремящемся к бесконечности.
Ну и очередная радость аналитическая состоит в том,
что нам вовсе необязательно знать, чему равняется это количество способов.
Мы обозначим его как-нибудь B от (k,
l) — по аналогии с тем, как мы вводили обозначение A от (k, l).
Значит, это просто, повторяю, B от (k, l) — это просто количество
способов на уже фиксированных 2k − t вершинах, видите, здесь 2k − t вершин.
Вот на этих фиксированных 2k − t вершинах как-то еще там расположить копии графа H.
Все равно это величина, которая от n никак зависеть не будет, это величина,
которая зависит только от k и от l.
Вот.
Ну и все, а теперь надо умножить на нашу верхнюю оценку вероятности,
это p в степени 2l − lt поделить на k,
lt поделить на k, вот такая вот штука у нас получилась.
Правильно?
Вроде правильно.
lt поделить на k.
Да, да-да-да-да, именно такая штука у нас и получилась, конечно, конечно, конечно...
Замечательно, но это вот верхняя оценка для двойного суммирования,
это верхняя оценка для двойного суммирования, а нам хочется доказать,
что ведь не она стремится к нулю, а дробь стремится к нулю,
если мы всю вот эту вот верхнюю оценку поделим на
величину C из n по k в квадрате на p в степени 2l.
Ну это ж замечательно, друзья,
мы с вами сегодня уже не раз писали соответствующие асимптотики.
Во-первых, вот это благополучно шлёп-шлёп, тут никаких 2l не остается,
а остается просто p в степени −lt поделить на k.
Дальше, какие асимптотики мы писали?
Ну давайте я перепишу это вот так: я напишу,
что это сумма по t от 1 до k, а вот здесь,
под знаком суммирования, буду писать соответствующие дроби.
Во-первых, видно, что...
ой, как же я не заметил сразу.
Вот эти еще шлёп-шлёп, то есть вот этот квадрат сокращается вот с этим C из n по
k, тут даже никаких асимптотик знать не надо, просто сокращается и все.
Так, чудесно, чудесно, так, так, так, так, так, так, так, так...
Так, так, так...
Ну давайте напишем, ладно.
C из k по t на B от (k, l) — это все фигня,
это все константы, они ни на что не влияют вообще.
Сейчас мы этим воспользуемся, не будем их переписывать дальше.
Так, здесь у нас остается C из n − k по k − t на p в
степени −lt, деленное на k.
А в знаменателе каждого из слагаемых благополучно выжило только C из n по k.
И вот нам нужно доказать, что такая сумма стремится к нулю.
Хе! Но я повторяю, вот эти вот штуковины,
это константы: что C из k по t там, что C из k по 1, что C из k по k.
Ну, как хотите, я могу оценить, например, это как 2 в степени k.
Понятно, что C из k по t меньше, чем 2 в степени k при абсолютно любом t.
Это какая-то тривиальная оценка, вытекающая из того,
что сумма всех биномиальных коэффициентов — это уж в точности 2 в степени k.
Ну значит, каждый из них не превосходит 2 в степени k.
Но даже 2 в степени k — это константа, это фиксированная величина,
которая на стремление к нулю никакого влияния не оказывает вовсе.
Поэтому на вот это вот произведение мы благополучно можем,
как бы вам это сказать поприличней, это мы его можем забыть.
Да, мы его можем забыть, я вот все время как-то пытаюсь неприличные слова
произносить на лекциях, это нехорошо.
Вот, значит, мы можем его вообще не рассматривать никак,
оно не влияет на скорость стремления к нулю никоим образом.
Более того, смотрите, товарищи,
у нас ведь здесь фиксированное число слагаемых, всего k штучек.
Если мы докажем, что каждое из этих слагаемых, то есть, по сути,
вот эта величина, если мы докажем, что вот эта величина стремится к 0 при n,
стремящемся к бесконечности вне зависимости от того, чему равняется t,
то понятное дело, за счет фиксированности числа слагаемых,
мы тем самым получим, что и вся сумма стремится к нулю тоже.
Если бы вот это k могло от n зависеть, ну да,
там с ростом n могло бы набежать какое-то количество слагаемых,
и мы с вами в таких ситуациях как-то тоже побывали за время этого курса.
Но нет, все гораздо проще.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
