Участник:Quarter

Распределение степеней вершин

Определение:

Распределение степеней вершин случайного графа - это функция [math]P(x)[/math], определённая на [math]\mathbb{R}[/math] как [math]P(\xi=x)[/math], то есть выражающая вероятность того, что вершина [math]\xi[/math] в графе [math]G(n, p)[/math] имеет степень [math]x[/math]

Другими словами, распределение степеней [math]P(k)[/math] графа определяется как доля узлов, имеющих степень [math]k[/math].

Пример:

Если есть в общей сложности [math]n[/math] узлов в графе и из них [math]n_k[/math] имеют степень [math]k[/math], то [math]P(k) = \frac{n_k}{n}[/math]. Другими словами, [math]P(k)[/math] равно вероятности того, что отдельно взятая вершина в [math]G(n, p)[/math] имеет степень [math]k[/math].

Случайный граф [math]G(n, p)[/math] имеет биномиальное распределение степеней вершин [math]k[/math]:

[math] \begin{equation*} P(k) = {n-1 \choose k} p^k(1-p)^{n-1-k} \end{equation*} [/math]

Действительно, если вероятность появления ребра [math]p[/math], то вероятность появления ровно [math]k[/math] рёбер у вершины равна [math]p^k(1-p)^{n-1-k}[/math](схема Бернулли). Таких наборов рёбер у одной вершины всего [math]{n-1 \choose k}[/math], откуда получаем искомое распределение.

Распределение максимальной степени вершин

Определение:

Распределение максимальной степени вершин случайного графа - это функция [math]Q(x)[/math], определённая на [math]\mathbb{R}[/math] как [math]P(\xi=x)[/math], то есть выражающая вероятность того, что максимальная степень вершины [math]\xi[/math] в графе [math]G(n, p)[/math] равна [math]x[/math]

Максимальная степень вершины равна [math]k[/math] тогда и только тогда, когда не существует вершины степенью больше [math]k[/math]. Таким образом, нужно посчитать вероятность события [math]A: \exists v: \; deg(v) = k \;\&\; !\exists v: \; deg(v) \gt x[/math].

[math]P(\exists v: \; deg(v) = k) = P(k)[/math]

[math]P(!\exists v: \; deg(v) \gt k) = \sum_{x=k+1}^{n} (1-P(x))[/math]

События независимы, поэтому получаем: [math]Q(k) = P(k) \cdot \sum_{x=k+1}^{n} (1-P(x))[/math]

[math]Q(k) = (n-k)P(k) - P(k)\sum_{x=k+1}^{n} P(x)[/math]