Cтраница 1
Обобщенная схема размещения может быть использована и при изучении случайных графов неоднородной структуры. Рассмотрим множество з1п т всех графов с п вершинами и Т ребрами, каждая компонента которых содержит не более одного цикла. Как обычно, припишем одинаковые вероятности элементам этого множества и рассмотрим случайный граф со значениями из sinT - Каждый граф из sin T состоит из деревьев и компонент с одним циклом, поэтому для изучения характеристик случайного графа из П т можно использовать результаты, полученные в предыдущих параграфах. [1]
B обобщенной схеме размещения частиц через вероятности, связанные с суммами независимых случайных величин. [2]
Параграф 1.2 посвящен описанию обобщенной схемы размещения частиц, которую можно рассматривать как обобщение полиномиальных испытаний. Успешные применения обобщенной схемы ограничиваются в основном равновероятными случаями, известно лишь несколько случаев, где неравновероятная схема имеет естественную комбинаторную интерпретацию. [3]
Мы не видим возможности применения обобщенной схемы размещения в исследованиях неравновероятных графов, в книге приводятся некоторые результаты для таких графов, полученные с использованием метода моментов. Статистические приложения случайных графов, отклоняющихся от равновероятных, вызывают необходимость развития регулярных методов исследования таких случайных структур. [4]
В разделе 1.3 было показано, что обобщенная схема размещения, введенная в разделе 1.2, может быть использована при изучении широкого круга задач, связанных с компонентами случайных графов. В примере 1.3.1 было показано, что обобщенная схема размещения применима и при изучении случайных подстановок. [5]
В [55] при изучении случайных подстановок была использована обобщенная схема размещения. [6]
Эта теорема доказана в [29] с использованием подхода, опирающегося на обобщенную схему размещения. [7]
Приведем теперь несколько примеров комбинаторных задач, изучение которых сводится к изучению обобщенной схемы размещения частиц. [8]
Книга продолжает традиции книги Случайные отображения [55] и отличается от других исследований случайных графов систематическим использованием обобщенной схемы размещений, при котором многие комбинаторные задачи сводятся к задачам о суммах независимых случайных величин. Автор надеется, что глава, посвященная системам случайных линейных уравнений в G F ( 2), заинтересует широкий круг читателей. [9]
Не претендуя на исчерпывающее решение задач, возникающих при изучении связности случайных графов, в этом параграфе мы изложим достаточно общую модель случайного графа, в которой естественным образом возникает обобщенная схема размещения. Рассмотрим множество всех графов Tn ( R) с п занумерованными вершинами, обладающих некоторым свойством R. Будем предполагать, что понятие связности определено для графов этого множества и что каждый граф представляет собой набор связных компонент. В дальнейшем полезно представлять, как приводимое далее формальное изложение реализуется, например, для графов случайных отображений или подстановок. Первые из этих графов состоят из компонент, представляющих собой ориентированные графы с одним циклом, а вторые состоят только из ориентированных циклов. [10]
Исследования множеств SnjR подстановок с ограничениями на длины циклов дают пример плодотворной конкуренции различных аналитических методов асимптотического анализа таких, как метод перевала, применение теорем тауберова типа, подход, использующий обобщенную схему размещения. [11]
Книга состоит из пяти глав. В главе 1 описана обобщенная схема размещения и приведены ее применения к случайному лесу из некорневых деревьев, к случайному графу, состоящему из компонент, содержащих ровно один цикл, и к случайному графу, представляющему собой смесь деревьев и компонент с одним циклом. В главе 2 эти результаты применяются при изучении эволюции случайного графа. Случайные подстановки рассматриваются в главе 4, а глава 5 содержит некоторые сведения об уравнениях вида X е, где X и е - неизвестная и тождественная подстановки, d - целое неотрицательное число. [12]
Однако подход, основанный на применении обобщенной схемы размещения, при котором некоторые задачи для равновероятных графов сводятся к задачам о суммах независимых одинаково распределенных величин, неприменим к неравновероятным графам. Для таких графов известно не много результатов, поскольку пока нет эффективных методов их исследования. [13]
В разделе 1.3 было показано, что обобщенная схема размещения, введенная в разделе 1.2, может быть использована при изучении широкого круга задач, связанных с компонентами случайных графов. В примере 1.3.1 было показано, что обобщенная схема размещения применима и при изучении случайных подстановок. [14]
Обозначим Т число ребер в лесе из n N - Легко видеть, что Т - п - N. Следуя общему подходу, используемому при применении обобщенной схемы размещения, рассмотрим множество n 7V, состоящее из наборов N упорядоченных деревьев, и зададим на нем равномерное распределение. [15]