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

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

Число компонент в случайном двудольном графе

И. Б. Калугин


Аннотация: Пусть $G$ – случайный граф, с равными вероятностями принимающий любое значение из множества всех двудольных графов, имеющих $n$ занумерованных белых вершин, $m$ занумерованных черных вершин и $T$ ребер. Изучается поведение величины $\kappa$ – числа компонент графа $G$. В частности, установлено, что при $T\to\infty$, $0<\alpha_0\leqslant T/n$, $T/m\leqslant\alpha_1<\infty$, $T^2/nm\to c\in(0,1)$ случайная величина $\kappa-n-m+T$ имеет распределение Пуассона с параметром $\Lambda=-\frac12\bigl(\ln(1-c)+c\bigr)$.

УДК: 519.2

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


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

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


© МИАН, 2024