Cтраница 2
Для проведения объективных тестовых испытаний обычно разрабатывается генератор случайных графов. На вход генератора поступают управляемые параметры. Эти параметры принимают дискретные значения. Идеальным вариантом экспериментального исследования является проведение полного факторного эксперимента. Однако для оптимизационных задач на графах использование такого подхода не представляется возможным по причине больших временных затрат. [16]
В настоящей статье нас интересует вероятность того, что случайный граф Гп лг имеет 1 -фактор. [17]
Обобщенная схема размещения может быть использована и при изучении случайных графов неоднородной структуры. Рассмотрим множество з1п т всех графов с п вершинами и Т ребрами, каждая компонента которых содержит не более одного цикла. Как обычно, припишем одинаковые вероятности элементам этого множества и рассмотрим случайный граф со значениями из sinT - Каждый граф из sin T состоит из деревьев и компонент с одним циклом, поэтому для изучения характеристик случайного графа из П т можно использовать результаты, полученные в предыдущих параграфах. [18]
Не претендуя на исчерпывающее решение задач, возникающих при изучении связности случайных графов, в этом параграфе мы изложим достаточно общую модель случайного графа, в которой естественным образом возникает обобщенная схема размещения. Рассмотрим множество всех графов Tn ( R) с п занумерованными вершинами, обладающих некоторым свойством R. Будем предполагать, что понятие связности определено для графов этого множества и что каждый граф представляет собой набор связных компонент. В дальнейшем полезно представлять, как приводимое далее формальное изложение реализуется, например, для графов случайных отображений или подстановок. Первые из этих графов состоят из компонент, представляющих собой ориентированные графы с одним циклом, а вторые состоят только из ориентированных циклов. [19]
Представленная здесь работа подтверждает плодотворность продолжающегося в настоящее время применения моделей случайных графов в физике. [20]
Параметр в - IT / п играет роль времени в эволюции случайных графов. [21]
Книга продолжает традиции книги Случайные отображения [55] и отличается от других исследований случайных графов систематическим использованием обобщенной схемы размещений, при котором многие комбинаторные задачи сводятся к задачам о суммах независимых случайных величин. Автор надеется, что глава, посвященная системам случайных линейных уравнений в G F ( 2), заинтересует широкий круг читателей. [22]
В параграфе 1.3 излагается общий подход к изучению связности и размеров компонент случайных графов различных типов. [23]
Пусть, как обычно, аг обозначает число компонент размера г в случайном графе с п вершинами. [24]
При условиях теоремы Ег б т) стремится к нулю и число циклов в случайном графе Сп т стремится по вероятности к нулю. [25]
Для задач, формулируемых в терминах графов, такой подход приводит к необходимости создания генераторов случайных графов с теми или иными свойствами. При этом на начальном этапе, при общей формулировке переборных задач и разработке универсальных методов их решения, оказывается достаточным формирование выборки случайных графов с теми или иными свойствами, подчиняющейся равномерному закону распределения вероятностей. [26]
Из доказательства теоремы 1.8.10 видно, что число ип т вершин, входящих в одноцикловые компоненты случайного графа из s n T, имеет следующее предельное распределение. [27]
Из леммы 2 вытекает, что при N % - оо и N / N - 0 предельный случайный граф Г ( /) двудольного отображения / получается из графа Г ( /) случайного отображения / ( ж) g ( / i ( x)) множества Xi в Х следующим образом. Граф Г ( /), все вершины которого принадлежат множеству Х, имеет v ( fx) компонент. Каждая компонента состоит из одного цикла и подходов к нему. [28]
Графы, состоящие из некорневых деревьев и компонент ровно с одним циклом, играют такую же роль в исследовании случайных графов как и леса из корневых деревьев в исследовании графов случайных отображений. Поэтому в последующих разделах внимание сосредоточено на таких графах, причем для их изучения используется обобщенная схема размещения частиц. [29]
Не претендуя на исчерпывающее решение задач, возникающих при изучении связности случайных графов, в этом параграфе мы изложим достаточно общую модель случайного графа, в которой естественным образом возникает обобщенная схема размещения. Рассмотрим множество всех графов Tn ( R) с п занумерованными вершинами, обладающих некоторым свойством R. Будем предполагать, что понятие связности определено для графов этого множества и что каждый граф представляет собой набор связных компонент. В дальнейшем полезно представлять, как приводимое далее формальное изложение реализуется, например, для графов случайных отображений или подстановок. Первые из этих графов состоят из компонент, представляющих собой ориентированные графы с одним циклом, а вторые состоят только из ориентированных циклов. [30]