Добрый день, друзья!
Ну, мы с вами уже довольно много всего изучили: связность случайного графа,
которая, в общем, имеет даже и прикладное значение, очень много поговорили о
раскрасках, о хроматическом числе и связанных с ним характеристиках.
С этой темы, конечно, пора слезать, и вот последняя в рамках этого курса,
на мой взгляд, действительно очень важная в том числе и с точки зрения приложений
тема — это тема о количестве подграфов заданного типа в случайном графе.
Ну, сейчас я поясню, о чем идет речь.
Это вещь действительно очень полезная.
Нужно понимать, сколько графов данного вида встречается в случайном графе.
То есть, на вас падает случайный граф и вы хотите понять, сколько в нем,
например, треугольников.
Или сколько в нем деревьев на 17-ти вершинах.
Ну, давайте введем соответствующие обозначения.
Значит, тема будет — количество вхождений конкретного графа в случайный граф.
Давайте конкретный граф обозначим буквой H.
Значит, H — это некоторый фиксированный граф,
некоторый фиксированный граф.
Как я уже сказал, это может быть треугольник, это может быть дерево,
это может быть какой-нибудь цикл на 17-ти вершинах, что хотите, ну,
в общем, это некоторый фиксированный раз и навсегда граф.
Вот, а буквой G мы будем, как обычно, обозначать случайный граф.
То есть, у нас, как всегда, есть случайный граф,
у которого множество вершин V, вполне себе определенное,
оно состоит из n элементов и может представляться как отрезок натурального
ряда от 1 до n, вот, и у него есть случайное множество ребер.
Давайте я запишу, действительно,
что множество вершин — это множество чисел от 1 до n.
Ну и, как водится, у случайного графа есть вероятность возникновения ребра — это p,
которая, вообще говоря, зависит от n, и, как на всех предшествующих лекциях,
мы, конечно, будем стараться изучать те характеристики, которые я сейчас введу,
в первую очередь с ростом n, то есть будем смотреть, как варьируется их поведение,
изменяется их поведение при n, стремящемся к бесконечности.
Ну, вроде у нас так всегда и было.
Значит, давайте через X с индексом H от G обозначим,
ну, в случае случайного графа, случайную величину.
Значит X с индексом H от G — это случайная
величина, случайная
величина, равная
количеству копий графа H в случайном графе G,
копий — то есть изоморфных копий, случайная величина,
равная количеству
копий графа H,
вот этого, абсолютно фиксированного графа, с никак не растущим количеством вершин,
в случайном графе G, у которого как раз количество вершин очень даже будет расти.
То есть, еще раз, нас интересует, действительно,
сколько раз вот этот конкретный граф H входит в растущий случайный граф G,
сколько там присутствует копий.
Это действительно очень важная характеристика с точки зрения практики,
потому что оказывается, что многие реальные сети, например, интернет,
или социальные сети, или сети биологического характера,
происхождения — они отличаются от каких-то произвольных графов тем,
что для них вот эти характеристики ведут себя некоторым специальным образом.
Например, хорошо известно,
что в интернете много треугольников — это свидетельствует о том, что очень часто мои
знакомые являются знакомыми между собой, что вполне естественно.
Вот, но и какие-то другие конкретные графы тоже очень интересно, очень интересно
рассматривать, как они входят в случайный граф и за счет этого можно как-то
характеризовать поведение этой случайной сети, этого случайного графа.
Ну, а с другой стороны, как всегда, я, в общем, говорю,
что это прекрасная математика, и сейчас мы поймем, как ведет себя вот эта вот
случайная величина в зависимости от различных свойств графа H.
Прежде чем я буду переходить собственно к вероятностным рассуждениям,
то есть к формулировке точной теоремы, которая здесь получается,
давайте я все-таки немножко еще поясню,
что такое вот это X с индексом H от G, ну, на каких-нибудь примерах.
Давайте, например, считать, что H — это треугольник,
граф на 3-х фиксированных вершинах, а G — хоть и случайный,
но вот он реализовался, и представляет собою полный граф на n вершинах.
То есть, давайте считать, что G — это K с индексом n, полный граф на n вершинах.
Тогда чему равняется X с индексом H от G?
Сколько есть треугольников в полном графе на n вершинах?
Ну, ответ, конечно, очевиден — это С из n по 3.
Можно задаться более сложным вопросом.
Пусть G — по-прежнему Kn, но H — это, скажем,
простой цикл, простой цикл
на k вершинах, где k — какое-то фиксированное число.
Значит, простой цикл на k вершинах.
А G реализовался по-прежнему как полный граф.
Ну тогда, конечно, X с индексом H от G, мы неоднократно эту величину считали,
когда занимались с вами раскрасками, короткими циклами в случайных графах,
X с индексом H от G — это есть, конечно, C из n по k.
Мы, прежде всего, фиксируем вершины для нашего цикла.
Но затем, мы же говорим об изоморфной копии, правильно?
Затем надо еще посчитать, сколькими способами цикл можно расположить на
данных k вершинах, и, как мы это не раз уже замечали,
такая вещь делается (k−1) факториал пополам способами.
То есть, вхождений конкретного цикла на k вершинах в граф на n вершинах,
полный — это вот такое вот количество, C из n по k на (k−1) факториал пополам.
Вот.
Ну, разумеется, можно посмотреть на какие-то более сложные объекты,
но, мне кажется, что в общем идея понятна.
В общем идея понятна.
Андрей Райгородскийпрофессор, доктор физико-математических наук
Максим Жуковскийпреподаватель
