Граф случайный

- вероятностная модель, предназначенная для изучения частотных характеристик различных параметров графов. Под Г. с. обычно понимается нек-рый класс графов [img: http://localhost:8080/file/010428-291.jpg] на к-ром задано распределение вероятностей. Произвольный конкретный граф Gиз [img: http://localhost:8080/file/010428-292.jpg] наз. реализацией Г. с. Всякая числовая характеристика графа (см. Графов числовые характеристики).может рассматриваться как случайная величина. Понятие Г. с. оказывается весьма полезным при моделировании сетей связи, подверженных нек-рым случайным изменениям, или логических сетей, элементы к-рых могут приходить в неисправные состояния; при рассмотрении картины фазовых превращений в статистич. физике; при изучении различных биологич. процессов; при решении задач минимизации булевых функций и др. В ряде случаев понятие Г. с. позволяет использовать аппарат теории вероятностей для получения асимптотич. решений перечислительных задач. Одной из типичных является такая конструкция Г. с., при к-рой все реализации получаются в результате применения к заданному неслучайному графу G(чаще всего полному) нек-рой процедуры уничтожения его ребер; при этом обычно предполагается, что уничтожение различных ребер - события независимые и уничтожение ребра епроисходит с вероятностью д(е). Такую конструкцию Г. с. обозначают [img: http://localhost:8080/file/010428-293.jpg] Наибольший интерес представляет изучение различных числовых характеристик связности Г. с. [img: http://localhost:8080/file/010428-294.jpg] таких, как число компонент связности, диаметр, радиус, число связности и т. п., к-рые можно интерпретировать как характеристику надежности соответствующей сети связи или логической сети. В этом случае число [img: http://localhost:8080/file/010428-295.jpg] характеризует надежность связи е, а [img: http://localhost:8080/file/010428-296.jpg] - вероятность выхода ее из строя. Если [img: http://localhost:8080/file/010429-1.jpg] - полный граф с пвершинами, [img: http://localhost:8080/file/010429-2.jpg], [img: http://localhost:8080/file/010429-3.jpg], то с вероятностью, стремящейся к 1 при [img: http://localhost:8080/file/010429-4.jpg], Г. с. [img: http://localhost:8080/file/010429-5.jpg] связен, имеет диаметр и радиус, равные 2, содержит гамильтонов цикл (см. Графа обход). Если [img: http://localhost:8080/file/010429-6.jpg] - функция числа вершин п, то вероятность связности Г. с. [img: http://localhost:8080/file/010429-7.jpg] зависит от близости величины [img: http://localhost:8080/file/010429-8.jpg] к [img: http://localhost:8080/file/010429-9.jpg]. Точнее, пусть [img: http://localhost:8080/file/010429-10.jpg] тогда [img: http://localhost:8080/file/010429-11.jpg] стремится к 1 при [img: http://localhost:8080/file/010429-12.jpg], если [img: http://localhost:8080/file/010429-13.jpg] стремится к 0, если [img: http://localhost:8080/file/010429-14.jpg] стремится к [img: http://localhost:8080/file/010429-15.jpg], если [img: http://localhost:8080/file/010429-16.jpg] (с - нек-рая константа). В последнем случае число ребер Г. с. асимптотически равно [img: http://localhost:8080/file/010429-17.jpg]. Этот же Г. с. [img: http://localhost:8080/file/010429-18.jpg] может рассматриваться как граф, получаемый из неслучайного пустого n-вершинного графа путем случайного соединения его вершин ребрами так, что любая пара вершин соединяется независимо от остальных с вероятностью [img: http://localhost:8080/file/010429-19.jpg]. Этому способу образования графа [img: http://localhost:8080/file/010429-20.jpg] можно придать динамику, если положить [img: http://localhost:8080/file/010429-21.jpg] и смотреть на tкак на время. При этом наблюдается следующая картина. В начальный момент времени t=0имеется пизолированных вершин. Затем с ростом tпоявляются нетривиальные компоненты связности, представляющие собой деревья или связные графы с одним циклом и малым числом вершин. Затем появляется одна "главная" компонента, содержащая число вершин, асимптотически равное п(при больших п). Дальнейший процесс характеризуется ростом главной компоненты и уменьшением числа малых компонент. Наконец, наступает момент, когда граф становится связным. Эту эволюцию Г. с. можно рассматривать как модель картины фазовых превращений, где роль жидкой фазы играет главная компонента, а роль разреженной фазы играют компоненты с малым числом вершин. Существует много других видов Г. с., напр. Г. с., связанные с деревьями (случайные деревья), с однозначными отображениями конечного множества в себя (случайные отображения), с подграфами единичного n-мерного куба (случайные булевы функции).