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

Дискрет. матем., 1990, том 2, выпуск 4, страницы 82–91 (Mi dm887)

Эта публикация цитируется в 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, граф состоит из компонент связности двух видов и описана структура этих компонент.

УДК: 519.2

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


 Англоязычная версия: Discrete Mathematics and Applications, 1992, 2:2, 225–234

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


© МИАН, 2024