|
Дискретная математика, 1995, том 7, выпуск 4, страницы 86–94
(Mi dm609)
|
|
|
|
Число компонент в случайном двудольном графе
А. И. Салтыков
Аннотация:
Рассматривается двудольный граф $G(n_1,n_2,T)$ с $n_1$ вершинами в первой доле и $n_2$ вершинами во второй доле, полученный в результате $T$ независимых испытаний, в каждом из которых проводится ребро, соединяющее две вершины, выбранные равновероятно независимо одна от другой из разных долей. Пусть $n_1\ge n_2$, $\alpha=n_2/n_1$, $n=n_1+n_2$. Доказано, что если $n\to\infty$ и $(1+\alpha)T=n\ln n+xn+o(n)$, где $x$ — фиксированное число, то с вероятностью, стремящейся к единице, граф $G(n_1,n_2,T)$ содержит одну гигантскую компоненту связности и изолированные вершины, число которых распределено по закону Пуассона.
Статья поступила: 15.11.1994
Образец цитирования:
А. И. Салтыков, “Число компонент в случайном двудольном графе”, Дискрет. матем., 7:4 (1995), 86–94; Discrete Math. Appl., 5:6 (1995), 515–523
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm609 https://www.mathnet.ru/rus/dm/v7/i4/p86
|
Статистика просмотров: |
Страница аннотации: | 404 | PDF полного текста: | 185 | Первая страница: | 2 |
|