|
Дискретная математика, 1990, том 2, выпуск 4, страницы 82–91
(Mi dm887)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
О строении случайных ориентированных графов с помеченными ребрами
С. П. Черкашин
Аннотация:
В работе И. Н. Коваленко [1] изучается вероятностная структура случайного неориентированного графа из $m$ вершин со случайным числом ребер, у которого вершины $i_1$ и $i_2$ соединяются с вероятностью $p(i_1,i_2)=p_m(i_1,i_2)$. Показано, что при $m\to\infty$ и при выполнении ряда условий с вероятностью, стремящейся к 1, граф состоит из одной компоненты связности и некоторого количества изолированных вершин, распределение числа которых сходится к распределению Пуассона. В работе
И. Н. Коваленко [2] аналогичные результаты получены при изучении ориентированных графов. В настоящей работе рассматриваются ориентированные графы с $m$ вершинами и $n$ помеченными ребрами, при этом ребро с фиксированной меткой соединяет вершины $i_1$, $i_2$ с вероятностью $p(i_1,i_2)=p_m(i_1,i_2)$. Допускаются петли и параллельные ребра. Показано, что при $m\to\infty$, $n\to\infty$ и при выполнении ряда условий с вероятностью, стремящейся к 1, граф состоит из компонент связности двух
видов и описана структура этих компонент.
Статья поступила: 28.09.1989
Образец цитирования:
С. П. Черкашин, “О строении случайных ориентированных графов с помеченными ребрами”, Дискрет. матем., 2:4 (1990), 82–91; Discrete Math. Appl., 2:2 (1992), 225–234
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm887 https://www.mathnet.ru/rus/dm/v2/i4/p82
|
Статистика просмотров: |
Страница аннотации: | 283 | PDF полного текста: | 111 | Первая страница: | 1 |
|