Добрый день, друзья! Ну, мы с вами уже довольно много всего изучили: связность случайного графа, которая, в общем, имеет даже и прикладное значение, очень много поговорили о раскрасках, о хроматическом числе и связанных с ним характеристиках. С этой темы, конечно, пора слезать, и вот последняя в рамках этого курса, на мой взгляд, действительно очень важная в том числе и с точки зрения приложений тема — это тема о количестве подграфов заданного типа в случайном графе. Ну, сейчас я поясню, о чем идет речь. Это вещь действительно очень полезная. Нужно понимать, сколько графов данного вида встречается в случайном графе. То есть, на вас падает случайный граф и вы хотите понять, сколько в нем, например, треугольников. Или сколько в нем деревьев на 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) факториал пополам. Вот. Ну, разумеется, можно посмотреть на какие-то более сложные объекты, но, мне кажется, что в общем идея понятна. В общем идея понятна.
