RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 1989, том 1, выпуск 3, страницы 121–128 (Mi dm931)

О структуре случайного графа вблизи критической точки

В. Е. Бритиков


Аннотация: Пусть $\mathfrak M_{n,T}$ – множество всех графов с $n$ вершинами и $T$ ребрами, $\mathscr A_{n,T}$ – подмножество графов из $\mathfrak M_{n,T}$ любая компонента которых содержит не более одного цикла, $G_{n,T}$ – случайный граф из $\mathfrak M_{n,T}$ и $p(n,T)=\mathbf p\{G_{n,T}\in\mathscr A_{n,T}\}$. Известно, что если $n,T\to\infty$ и $\varepsilon n^{1/3}\to\infty$, где $\varepsilon=1-2T/n$, то $p(n,T)\to1$. В статье доказано, что если $\varepsilon n^{1/3}\to-\infty$, то $p(n,T)\to0$, а в промежуточном случае, когда $n,T\to\infty$, $3^{2/3}\varepsilon n^{1/3}/2\to\gamma$, $-\infty<\gamma<\infty$,
$$ p(n,T)\to p(\gamma)=\biggl(\frac2{3\pi}\biggr)^{1/2}e^{4\gamma^3/27}\sum_{k=0}^\infty\frac{\gamma^k}{k!}\Gamma\biggl(\frac{2k}3+\frac12\biggr)\cos\frac{\pi k}3, $$
где $\Gamma(y)=\int_0^\infty t^{y-1}e^{-t}\,dt$, гамма-функция, а $p(\gamma)>0$ и монотонно возрастает от нуля до единицы с ростом $\gamma$, $-\infty<\gamma<\gamma$; в частности, $p(0)=(2/3)^{1/2}=0.8165\dots$ .

УДК: 519.2

Статья поступила: 21.02.1989


 Англоязычная версия: Discrete Mathematics and Applications, 1991, 1:3, 301–309

Реферативные базы данных:


© МИАН, 2024