|
Дискретная математика, 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$ .
Статья поступила: 21.02.1989
Образец цитирования:
В. Е. Бритиков, “О структуре случайного графа вблизи критической точки”, Дискрет. матем., 1:3 (1989), 121–128; Discrete Math. Appl., 1:3 (1991), 301–309
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm931 https://www.mathnet.ru/rus/dm/v1/i3/p121
|
Статистика просмотров: |
Страница аннотации: | 328 | PDF полного текста: | 121 | Первая страница: | 3 |
|