|
Труды по дискретной математике, 2000, том 3, страницы 29–36
(Mi tdm35)
|
|
|
|
О вероятности вложимости случайного мультиграфа с раскрашенными ребрами в двудольный граф
В. А. Ватутин
Аннотация:
Рассматривается динамическая процедура построения случайного графа, описываемая следующим образом. В начальный момент времени имеется множество вершин $V=\{1,2,\dots,N\}$, служащее основой при построении случайного мультиграфа $M=M(2N,m)$, который получается в результате проведения $m$ последовательных двухэтапных независимых испытаний. При каждом испытании на первом этапе из множества $V$ выбираются (независимо от результатов предшествующих испытаний) два ребра по схеме равновероятного выбора с возвращением, а на втором этапе каждому ребру независимо от остальных приписывается тип: с вероятностью 1/2 – нулевой
и с вероятностью 1/2 – первый. В работе получена оценка сверху для вероятности события
$$
B(2N,m)=
\left\{\begin{matrix}
\text{существует такая раскраска вершин множества~$V$}\\
\text{в белый и черный цвета, что количество вершин}\\
\text{каждого цвета равно$N$ и при этом каждое ребро}\\
\text{нулевого типа соединяет вершины одного цвета,}\\
\text{а~каждое ребро первого типа соединяет вершины}\\
\text{разных цветов } \hfill
\end{matrix}\right\}.
$$
Образец цитирования:
В. А. Ватутин, “О вероятности вложимости случайного мультиграфа с раскрашенными ребрами в двудольный граф”, Тр. по дискр. матем., 3, Физматлит, М., 2000, 29–36
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/tdm35 https://www.mathnet.ru/rus/tdm/v3/p29
|
Статистика просмотров: |
Страница аннотации: | 197 | PDF полного текста: | 65 |
|