Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен? Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины. Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети. Прослушав этот курс, вы проникнетесь чрезвычайно красивой математической теорией и научитесь решать комбинаторные и алгоритмические задачи на случайных графах. Все эти знания позволят нам затем перейти к курсу веб-графов, в котором мы расскажем о самых современных приложениях вероятностно-графовых моделей и конструкций. Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.
Задача о количестве 4-циклов в случайном двудольном графе
Loading...
来自 Moscow Institute of Physics and Technology 的课程
Случайные графы
65 个评分
从本节课中
Вероятностный метод
Хроматическое число, число независимости и кликовое число. Обхват графа. Теорема о существовании графа с большим обхватом и большим хроматическим числом.
与讲师见面
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Максим Жуковскийпреподаватель
кафедра дискретной математики МФТИ
Так, товарищи, ну давайте позаймемся третьей нашей темой,
попробуем разобраться со средним и дисперсией числа
циклов некоторого типа в случайном подграфе двудольного графа.
Ну это звучит, может быть, как-то устрашающе.
На самом деле все просто.
Давайте рассмотрим то, что мы обозначаем G (n, n, p).
То есть у нас есть полный двудольный граф с одинаковыми долями размера n и
n соответственно, и мы каждое его ребро оставляем с вероятностью p,
независимо от всех остальных.
Я надеюсь, что этой моделью мы уже достаточно много пользовались на
протяжении семинаров, поэтому как-то она должна была усвоиться.
Вот.
Ну и давайте обозначим X от случайного такого двудольного
графа — количество 4-циклов,
ну то есть простых циклов длины 4 в таком графе.
Ну давайте я нарисую картинку, чтоб было более, может быть,
понятно как в ней жизнь устроена.
Вот одна доля.
Как обычно, мы ее рисуем верхней.
Вот другая доля.
Ее мы располагаем соответственно снизу.
Здесь n вершин.
Здесь n вершин.
Вот как в принципе может возникнуть цикл длины 4 в полном графе?
Не в случайном подграфе пока что, а в полном двудольном графе,
который построен на этих долях?
Ну на самом деле совершенно понятно — вот он этот цикл, пример такого цикла.
То есть нам достаточно выбрать какие-то 2 вершины сверху и какие-то 2 вершины снизу.
И вот они вместе порождают в полном графе цикл длины 4.
Конечно, если мы возьмем сверху, например, 1 вершину, а снизу 3, никакого цикла
длины 4 не возникнет, возникнет просто вот такое вот деревце, да, лапка такая.
Вот. А если мы возьмем вообще 4 вершины внутри
одной доли, то это будет пустое свободное от ребер, как говорят,
независимое, да, множество.
Вот. Поэтому если мы желаем посчитать в
случайном графе количество 4-циклов,
то нам на самом деле нужно перебрать все возможные пары
вершин из верхней доли и все возможные пары вершин из нижней доли,
и для каждой пары таких пар, для каждых 2-х таких пар (одна сверху,
другая снизу) для каждых 2-х таких пар посмотреть: а в случайном графе,
а в случайном графе они по-прежнему образуют цикл или нет?
Ну я думаю, что я могу уже не разжевывать линейность-то математического ожидания,
но мне придется это сделать, потому что затем я дисперсию буду считать,
а для дисперсии мне все равно потребуются какие-то обозначения.
Вот давайте я подсмотрю в шпаргалку, как здесь предлагалось ввести эти обозначения.
Ну, например, так: значит,
A — это множество всех таких,
всех таких четверок,
что ли (четверок вершин имеется в виду),
2 из которых лежат сверху и 2 из которых лежат снизу, то есть те и только те,
которые способны породить цикл длины 4.
Множество всех таких четверок (ну давайте я все-таки не буду это фиксировать на
доске, 2 из которых лежат сверху, а 2 лежат снизу.
Так, замечательно.
Тогда математическое ожидание X за счет линейности — это сумма по всем,
ну скажем, v, принадлежащим A (v — это вот как раз конкретная четверка,
которая состоит из 2-х пар), так, сумма по всем v,
принадлежащим A математических ожиданий X с индексом v (ну X с
индексом v — это стандартный индикатор, который указывает на то,
в случайном-то графе, вот на этой конкретной четверке, которую мы обозначили
v маленькое, образовался цикл длины 4 или не образовался.
Ну понятно, что это есть просто p в четвертой степени, это вероятность того,
что все 4 ребра (вот эти вот: 1, 2, 3, 4) выжили,
остались на месте и, стало быть, в случайном графе по-прежнему образуют цикл.
Но p в четвертой — это каждое из математических ожиданий.
И надо умножить на количество способов зафиксировать такую четверку,
то есть на C из n по 2 в квадрате.
C из n по 2 — это количество способов выбрать пару в верхней доле,
и C из n по 2 же — это количество способов выбрать пару в нижней доле.
Поскольку четверка состоит из 2-х независящих друг от друга пар,
то количество четверок таких у нас получается в точности C из n по 2 в
квадрате, конечно.
И матожидание тривиальным образом найдено,
но для того чтобы найти дисперсию, тут ну чуть-чуть надо еще подумать.
Значит, смотрите: что такое дисперсия X?
Ну, как обычно, давайте я еще разок распишу.
Это есть, конечно, второй момент, то есть математическое ожидание квадрата,
минус квадрат математического ожидания.
Так.
Ну как это можно расписать получше?
Сейчас я подгляжу в шпаргалку свою, чтобы у меня все соответствовало.
Да, товарищи, будем соответствовать шпаргалке?
Ну а чего бы нет?
Так, ну математическое ожидание в квадрате-то мы нашли.
Это большой трудности уже не составляет вычесть.
Вот квадрат такой штуковины мы вычтем.
Поэтому давайте я напишу, конечно.
MX квадрат минус p в восьмой на C из n по 2 в четвертой (это я
просто в квадрат возвел).
Это вообще не составляет труда.
И теперь мне нужно второй момент посчитать.
Ну а второй момент традиционно считается вот так.
Мы с этим уже сталкивались неоднократно.
Давайте как-то все-таки зафиксируем мы это счастье.
Надо понимать, что это всегда так и происходит.
Значит, надо честно возвести вот эту вот сумму по v из A в квадрат,
по v из A, Xv-тых честно возвести в квадрат.
Там отдельно будут слагаемые X с индексом v в квадрате,
а отдельно будут всевозможные произведения X с индексом, там, скажем,
v1, X с индексом v2, где v1 не равняется v2.
Но те величины, которые пойдут с квадратами,
это же индикаторы в квадрате, они совпадают просто с самими собой,
то есть Xv в квадрате — это то же самое, что Xv.
Короче говоря, получится математическое ожидание X,
которое мы благополучно уже нашли, ну и плюс вот эта
вот сумма по v1 не равняется v2
матожиданий Xv1, Xv2.
Вот совершенно стандартная вещь.
Мне не хочется уже ее мучительно повторять в подробностях.
Вроде совершенно понятно.
Значит вот еще раз: эта штука она возникает из суммирования
полных квадратов, потому что квадраты совпадают со своими же первыми степенями.
А это все, что осталось.
И двойку я, как обычно, не рисую, потому что подразумеваю, что вот эти пары v1, v2,
по которым идет суммирование, они не совпадающие.
v1 и v...
Они, извините, упорядоченные, то есть здесь есть v1, v2,
то есть и v2, v1 отдельно.
Поэтому я двойку не дорисовываю.
Ну это традиционно.
Это вещь стандартная.
Так, замечательно!
Вот эту штуку мы знаем а матожидание Xv1, Xv2 нам нужно найти.
Но что такое матожидание Xv1, Xv2?
Это вероятность того, что оба цикла (один на четверке вершин v1,
другой на четверке вершин v2) присутствуют в нашем случайном графе.
Но смотрите если одна четверка
v1 устроена так, как я здесь нарисовал,
а другая четверка относительно нее расположена вообще вот так.
Ну то есть и в верхней доле соответствующая пара не пересекается,
и в нижней доле соответствующие пары не пересекаются,
то, конечно, суммарное количество ребер, которые должны
в этом случае присутствовать в случайном графе, равняется восьмерке.
И вот эти четыре должны присутствовать, и вот эти четыре должны присутствовать.
Ну можно нарисовать другую ситуацию.
Давайте, скажем, вот так.
Вот так я нарисую,
смотрите: вот одна четверка — это v1,
а другая четверка вот такая, например.
То есть в верхней доле пара, отвечающая второй четверке,
пересекается с парой, которая отвечает первой четверке,
но пересекается только по одному элементу, тогда все равно — вот здесь
4 ребра и здесь вот на этом цикле, конечно же, тоже 4 ребра.
То есть ничего не изменилось.
Опять 8 ребер обязаны присутствовать, коль скоро мы хотим,
чтобы вот это произведение индикаторов благополучно равнялось единичке.
Ну, я надеюсь, вы понимате, да, что если я вот эту вершину тоже склею вот с этой, то
есть у меня в нижней доле пары тоже начнут пересекаться ровно по одному элементу,
то у меня и в этом случае будет...
А сколько у меня будет ребер, если у меня вот эти вот?..
Давайте нет, давайте нарисуем, давайте нарисуем,
вот у меня вот такая ситуация: вот одна четверка, а вот вторая четвертка.
Вот они теперь так зацепляются.
Давайте посмотрим, сколько здесь ребер.
Вот в этом цикле, да, ребра, а вот в этом цикле ребра.
И вообще-то, вообще-то у меня сколько ребер получилось?
Раз, два, три, четыре, пять, шесть, семь.
А-а!
Видите, вот ситуация уже немножко другая!
То есть, если четверки зацепляются по
одной вершине в верхней доле или точно так же по одной вершине в
нижней доле, то у них, конечно, суммарно восемь ребер должно присутствовать.
Но если у меня четверки пересекаются вот так, как здесь нарисовано, то есть и пара,
расположенная в верхней доле, с парой, расположенной в верхней доле,
пересекается ровно по одному элементу, и то же самое происходит с парами,
расположенными в нижней доле, то тут уже получается семь ребер.
Тут уже получается семь ребер.
Видите, есть как бы разные ситуации...
есть как бы разные ситуации.
Так, ну давайте посмотрим, какая еще бывает ситуация.
Значит, если у меня в верхней доле есть пара,
пара непересекающихся пар,
а в нижней доле пары вообще совпадают, то есть вот это вот у меня
одна четверка, а вот это вот у меня — другая четверка.
То в этом случае сколько у меня получается ребер, которые должны присутствовать в
случайном графе, коль скоро я хочу, чтобы оба цикла присутствовали?
Ну вот давайте смотреть.
Раз, два, три, четыре (это для первой четверки),
и еще вот здесь вот надо вот так вот дорисовать, да?
Сколько получается?
А-а, у нас получается снова восемь: раз, два,
три, четыре, пять, шесть, семь, восемь.
Значит, вот в такой ситуации снова получается восемь.
Ну и последний интересный случай — это когда в верхней доле у нас три вершины,
а в нижней доле у нас две вершины.
То есть, вот одна четверка, а вот другая четверка.
И в этом случае ребра, которые должны присутствовать,
коль скоро мы желаем сохранить оба цикла, вот один цикл,
вот другой цикл, и у нас получается: раз, два, три...
сейчас, запутался...
раз, два, три, четрые, пять, шесть.
То есть вот здесь вот шесть ребер, вот здесь по-прежнему восемь,
вот здесь семь, здесь восемь и здесь восемь.
Ну и я думаю совершенно понятно, как после этого доводить до окончательного ответа.
Может быть вы позволите мне уже не выписывать там все соответствующие
биномиальные коэффициенты.
Но смысл очень простой: надо отдельно посчитать сколько
существует тех ситуаций, в которых у нас возникает восемь ребер.
Для каждой из таких ситуаций вероятность сохранения
обоих соответствующих циклов (это p в восьмой),
и вот величину p в восьмой, давайте я вот так вот здесь перепишу,
p в восьмой надо просто умножить на именно вот это количество ситуаций.
Ну вот так вот я сейчас условно не буду аккуратно досчитывать, например,
вот таких вот ситуаций, их сколько получается?
Можно C из n по 2 способами выбрать как вот эти, так и вот эти вершины,
то есть у нас возникает (C из n по 2) в квадрате, соответственно,
следующие две можно выбирать (C из n −
2 по 2) в квадрате способами + (надо посмотреть
сколько существует вот таких ситуаций), ну, легко посчитать сколько плюс,
сколько существует таких ситуаций, ну, то есть, я вот так напишу: +...
Дальше будет p в седьмой, и для p в седьмой надо будет посчитать,
сколько существует способов выбрать две четверки,
расположенные друг относительно друга, как я нарисовал вот на этой картинке.
Ну и в конце добавить p в шестой на количество, соответственно,
вот этих ситуаций.
То есть, здесь вот количество легко считается комбинаторно,
ну и p в шестой тоже легко комбинаторно считается.
У вас, соответственно,
там на Coursera все вот эти вот числа будут аккуратно выложены, а моя задача,
конечно, выполнена, потому что я вам объяснил, откуда эти числа получаются.
