НОВОСТИ    БИБЛИОТЕКА    ЭНЦИКЛОПЕДИЯ    БИОГРАФИИ    КАРТА САЙТА    ССЫЛКИ    О ПРОЕКТЕ  

ГРАФ СЛУЧАЙНЫЙ

ГРАФ СЛУЧАЙНЫЙ - вероятностная модель, предназначенная для изучения частотных характеристик различных параметров графов. Под Г. с. обычно понимается нек-рый класс графов γ = {G}, на к-ром задано распределение вероятностей. Произвольный конкретный граф G из γ наз. реализацией Г. с. Всякая числовая характеристика графа (см. Графов числовые характеристики) может рассматриваться как случайная величина. Понятие Г. с. оказывается весьма полезным при моделировании сетей связи, подверженных нек-рым случайным изменениям, или логических сетей, элементы к-рых могут приходить в неисправные состояния; при рассмотрении картины фазовых превращений в статистич. физике; при изучении различных биологич. процессов; при решении задач минимизации булевых функций и др. В ряде случаев понятие Г. с. позволяет использовать аппарат теории вероятностей для полуяения асимптотич. решений перечислительных задач.

Одной из типичных является такая конструкция Г. с, при к-рой все реализации получаются в результате применения к заданному неслучайному графу G (чаще всего полному) нек-рой процедуры уничтожения его ребер; при этом обычно предполагается, что уничтожение различных ребер - события независимые и уничтожение ребра е происходит с вероятностью q(e). Такую конструкцию Г. с. обозначают γG({q(е)}). Наибольший интерес представляет изучение различных числовых характеристик связности Г. с. γG({q(e)}) таких, как число компонент связности, диаметр, радиус, число связности и т. п., к-рые можно интерпретировать как характеристику надежности соответствующей сети связи или логической сети. В этом случае число 1 - q(e) характеризует надежность связи е, а q(e) - вероятность выхода ее из строя.

Если G - полный граф с n вершинами, q(e) ≡ q, 0 < q < 1, то с вероятностью, стремящейся к 1 при n → ∞, Г. с. γG({q(е)}) связен, имеет диаметр и радиус, равные 2, содержит гамильтонов цикл (см. Графа обход). Если q(e) - функция числа вершин n, то вероятность связности Г. с. γn(q) = γG({q(е)}) зависит от близости величины 1 - q(e) к ln n / n. Точнее, пусть

xn = n(1 - q(e)) - ln n;

тогда γn(q) стремится к 1 при n → ∞, если limn→∞ хn = ∞; стремится к 0, если limn→∞ хn = 0; стремится к е-e-c, если limn→∞ хn = с (с - нек-рая константа). В последнем случае число ребер Г. с. асимптотически равно (n ln n)/2.

Этот же Г. с. γn(q) может рассматриваться как граф, получаемый из неслучайного пустого n-вершинного графа путем случайного соединения его вершин ребрами так, что любая пара вершин соединяется независимо от остальных с вероятностью p = l - q. Этому способу образования графа γn(q) можно придать динамику, если положить q = e-t, t > 0, и смотреть на t как на время. При этом наблюдается следующая картина. В начальный момент времени t = 0 имеется n изолированных вершин. Затем с ростом t появляются нетривиальные компоненты связности, представляющие собой деревья или связные графы с одним циклом и малым числом вершин. Затем появляется одна «главная» компонента, содержащая число вершин, асимптотически равное n (при больших n). Дальнейший процесс характеризуется ростом главной компоненты и уменьшением числа малых компонент. Наконец, наступает момент, когда граф становится связным. Эту эволюцию Г. с. можно рассматривать как модель картины фазовых превращений, где роль жидкой фазы играет главная компонента, а роль разреженной фазы играют компоненты с малым числом вершин.

Существует много других видов Г. с, напр. Г. с, связанные с деревьями (случайные деревья), с однозначными отображениями конечного множества в себя (случайные отображения), с подграфами единичного n-мерного куба (случайные булевы функции).

Лит.: [1] Мур Э. Ф., Шеннон К. Э., «Кибернетический сборник», 1960, в. 1, с. 109-48; [2] Степанов В. Е., в кн.: Вопросы кибернетики. Труды семинара по комбинаторной математике, М., 1973, с. 164-85; [3] Дискретная математика и математические вопросы кибернетики, т. 1, М., 1974; [4] Сапоженко А. А., «Проблемы кибернетики», 1975, в. 30, С. 227-61.

А. А. Сапоженко.


Источники:

  1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.











© MATHEMLIB.RU, 2001-2021
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'Математическая библиотека'
Рейтинг@Mail.ru