Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/oim/materials/spring06/steel/s13-raig.ps Дата изменения: Thu Apr 13 18:34:00 2006 Дата индексирования: Sun Dec 23 01:26:35 2007 Кодировка: koi8-r Поисковые слова: п п п п п п п п п п п п п п п п п п п п п п п

Случайные графы
А.М. Райгородский
Основные понятия. Рассмотрим множество V = {1; : : : ; n}. Будем интерпретировать его как множество вер-
шин некоторого графа. Пусть e 1 ; : : : ; e C 2
n
- ребра полного графа на V . Выберем случайное подмножество E из
множества {e 1 ; : : : ; e C 2
n } с помощью "схемы испытаний Бернулли", т.е. каждое ребро независимо от остальных
положим в E с вероятностью p # [0; 1]; соответственно, с вероятностью q = 1-p мы его туда не кладем. В резуль-
тате возникнет случайный граф G = (V; E): множество его вершин фиксировано, а множество ребер E случайно.
Понятно, что вероятность появления конкретного графа G = (V; E) есть величина P (G) = p |E| q C 2
n -|E| .
Каждый граф - это элементарное событие. Совокупность же графов B естественно называть событием: вся-
кое событие строится из элементарных, как из кирпичиков. Событие разумно, в свою очередь, интерпретировать
как свойство случайного графа: сказать, что для графа выполнено некоторое свойство, это все равно, что отнести
граф к событию, состоящему из "кирпичиков", указанным свойством обладающих. Ясно, что вероятность собы-
тия есть сумма вероятностей элементарных событий, из которых оно состоит: P (B) = #
G#B
P (G). В частности,
если
- это множество всех возможных графов на n вершинах, то P (B) =
C 2
n
#
k=0
C k
C 2
n
p k q C 2
n -k = 1: какой-то граф
непременно возникнет.
Имея данное определение случайного графа, можно судить о том, с какой степенью достоверности граф обла-
дает тем или иным свойством. Например, можно оценить вероятность связности графа или вероятность того, что
граф имеет какое-то хроматическое число, и т.д. Полезно бывает изучать различные вероятности при n # #.
Скажем, если P (B) # 1, коль скоро n ##, то свойство B исключительно достоверно. Говорят даже, что в таком
случае оно выполнено почти наверное. Важно заметить, что вероятность ребра случайного графа - величина p -
сама имеет право зависеть от n, и в этом есть глубокий смысл, который мы ниже пронаблюдаем.
Любая функция X, определенная на множестве графов, будет называться случайной величиной. Пусть X прини-
мает k различных значений y 1 ; : : : ; y k . Тогда математическим ожиданием величины X называется ее "взвешенное
среднее" MX =
k
#
i=1
y i P ({G : X(G) = y i }). Для краткости мы будем писать P (X = y i ), подразумевая последнюю
вероятность.
Задачи.
0. а) Докажите линейность математического ожидания: M(c 1 X 1 + : : : + c s X s ) = c 1 MX 1 + : : : + c s MX s для любых
случайных величин X 1 ; : : : ; X s и констант c 1 ; : : : ; c s # R. б) Докажите, что если X принимает неотрицательные
целые значения, то P (X = 0) # 1 -MX.
1. Найдите MX для случайной величины X, равной а) числу треугольников в G; б) числу циклов длины k в G;
в) числу полных подграфов на k вершинах (k - клик) в G; г) числу различных k - вершинных деревьев в G; д)
числу изолированных k - вершинных деревьев в G; е) числу вершин на древесных компонентах G; ж) числу
вершин на циклических компонентах G.
2. Докажите, что если p = o # 1
n # , то в случайном графе почти наверное нет треугольников.
3. Пусть k # 2 - константа. Докажите, что если p = o # n - k
k-1 # , то в случайном графе почти наверное нет
древесных компонент на k вершинах.
4. Докажите, что если p = o # 1
n # , то случайный граф почти наверное образует лес.
5. Докажите, что если p = o # 1
n # , то случайный граф почти наверное двудолен.
6. Определим число независимости (G) графа G как размер максимального подмножества вершин в G, которые
попарно не соединены ребрами. Пусть p = 1
2 . Докажите, что P ((G) < 2 log 2 n + 10 log 2 log 2 n) # 1 при n ##.
7. В условиях задачи 5 докажите, что хроматическое число случайного графа почти наверное больше, чем n
log 2 n +
o # n
log 2 n # .
8. Докажите, что если p > 3ln n
n , то почти наверное случайный граф связен.
9 # . Пусть p = n - , где  > 5
6 . Докажите, что
P # #S # V; |S| # # n : (G| S ) # 3 # # 1; n ##:
Здесь G| S - порожденный или индуцированный подграф графа G = (V; E), т.е. граф H = (S; F ), у которго
e = (x; y) # F тогда и только тогда, когда x; y # S и e # E.
10 # . Докажите, что если p = o # 1
n # , то случайный граф почти наверное может быть реализован как граф рассто-
яний на плоскости, а если p > 1000
n , то почти наверное выполнено обратное свойство.