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

Дискрет. матем., 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)$ содержит одну гигантскую компоненту связности и изолированные вершины, число которых распределено по закону Пуассона.

УДК: 519.2

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


 Англоязычная версия: Discrete Mathematics and Applications, 1995, 5:6, 515–523

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


© МИАН, 2024