ГРАФ СЛУЧАЙНЫЙ это:

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

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

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

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


тогда стремится к 1 при , если стремится к 0, если стремится к , если ( с - нек-рая константа). В последнем случае число ребер Г. с. асимптотически равно .

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

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

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


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Смотреть что такое "ГРАФ СЛУЧАЙНЫЙ" в других словарях:

  • Случайный граф — Пусть   некоторое множество графов, на котором задана вероятностная мера. Тогда тождественное отображение называется случайным графом. Примером случайного графа, встречающегося в природе, может служить перколяционный кластер. См. также… …   Википедия

  • Ростопчин, граф Андрей Федорович — библиофил, писатель библиограф, тайный советник; младший сын графа Ф. В. Ростопчина и жены его графини Екатерины Петровны, урожденной Протасовой; родился 13 го октября 1813 года в Москве; рождение его, по словам его сестры Н. Ф. Нарышкиной,… …   Большая биографическая энциклопедия

  • Регулярный граф — граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Степень регулярности является инвариантом графа и обозначается . Для нерегулярных графов не определено. Регулярные графы представляют особую… …   Википедия

  • Бирон, граф Эрнст Иоганн — герцог курляндский и семигальский и регент Российской империи; род. 13 (23) ноября 1690 г., ум. 18 (28) декабря 1772 г., В письмах Эрнста Иоганна еще в 1721 22 гг. фамилия его пишется Biron или von Biron. По преданию, первоначальная форма ее… …   Большая биографическая энциклопедия

  • Блудов, граф Дмитрий Николаевич — президент Академии наук, председатель Государственного Совета; род. 5 апреля 1785 г. в родовом имении Романовке (Владимирской губернии, Шуйского уезда), ум. в Петербурге 19 февраля 1864 г. Ко времени рождения Димитрия Николаевича род Блудовых был …   Большая биографическая энциклопедия

  • Социальный граф — На данной анимации показаны в каких отношениях состоят разные социальные объекты. Пользователь Ева находится в дружеских отношениях с пользователями Адам и Кейт, при этом Адам и Кейт не являются друзьями друг другу, но у них есть общий друг Ева.… …   Википедия

  • Толстой, граф Алексей Константинович — известный поэт и драматург. Родился 24 августа 1817 г. в Петербурге. Мать его, красавица Анна Алексеевна Перовская, воспитанница гр. А. К. Разумовского, вышла в 1816 г. замуж за пожилого вдовца гр. Константина Петровича Т. (брата известного… …   Большая биографическая энциклопедия

  • Блудов Дмитрий Николаевич — граф, государственный деятель, род. 5 апр. 1785 г. в Шуйском у. Влад. г., в своем родовом имении, лишился отца в младенчестве, воспитался под надзором матери, переехал с нею в Москву, где в 1800 г. поступил на службу в архив иностранных дел, но… …   Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона

  • Толстой Алексей Константинович — (граф) известный поэт и драматург. Родился 24 августа 1817 г. в Петербурге. Мать его, красавица Анна Алексеевна Перовская, воспитанница гр. А. К. Разумовского, вышла в 1816 г. замуж за пожилого вдовца гр. Константина Петровича Т. (брата… …   Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона

  • Пушкин, Александр Сергеевич — — родился 26 мая 1799 г. в Москве, на Немецкой улице в доме Скворцова; умер 29 января 1837 г. в Петербурге. Со стороны отца Пушкин принадлежал к старинному дворянскому роду, происходившему, по сказанию родословных, от выходца "из… …   Большая биографическая энциклопедия

Книги

Другие книги по запросу «ГРАФ СЛУЧАЙНЫЙ» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»